Suppose that the integer values  of the weights of a two-pan balance scale are written in nondecreasing order as .  Let , where .  The necessary and sufficient condition for exact measurement of any integer weight X in the range  is

,  ,

or equivalently,                                                                                                                         (1)

,  .

Proof.  To demonstrate the sufficiency, i.e., that the satisfaction of (1) implies every integer weight X in the range  can be weighed exactly, we proceed by induction.  Assuming that the scale is not defective, it balances when nothing at all is placed on it.  So the trivial weight  can be weighed exactly. 

For , the induction hypothesis asserts that all integer weights X in the range  are weighable.  If so, we want to show that all X in the range

                                                                                                                         (2)

are weighable.  However, it follows from (2) and (1) that

                                                         .                                                              (3)

Inequality (3) will be verified momentarily, but the important point is that  is a new unknown weight that falls within the induction range: Think of X on one pan and  on the other as  on a single pan.  So  can be weighed exactly, from which it follows that the weight of X can be expressed in terms of the ’s.  This proves that all integer weights X in the range (2) can be weighed.

To confirm (3), suppose for a contradiction that it isn’t true.  The first possibility is that , which implies , and this violates (2).  The other possibility is that .  In this inequality use (1) to replace  by  to get , which implies  or .  Again, this violates (2).

Therefore all integer weights X in the range  can be weighed, completing the induction proof of the sufficiency of condition (1).

            To prove that condition (1) is necessary if every integer weight in the range  is to be weighed, we need only find one weight that cannot be weighed if (1) is ever violated.  In the chain of inequalities

                                                                                           (4)

suppose that  is any instance where (1) is violated.  The collection of weights denoted by B will be referred to, below.  We will show that the weight  can never be weighed by actually trying to do it and seeing what happens.

Place X on the left-hand pan of the scale.  No weight  from B may be placed along with X because  implies that the left pan will always outweigh the right pan.

Next, suppose that every weight except one,  from B, is placed on the right-hand pan.  In that case, the weight of the right pan, , is lighter than X.  If leaving just a single weight from B off the right pan means that we cannot weigh X, it follows that we must place every weight from B on the right pan. 

To keep the right pan as light as possible, suppose that we place only those weights from B on the right pan, and begin placing the remaining weights  along with X on the left pan.  Now the scale will not balance because

 the total weight of B.

In other words, with just the weights from B on the right-hand pan and every remaining weight on the left-hand pan along with X, the right pan will remain heavier.

So if (1) is violated, we have found a weight  that cannot be weighed.  This completes the proof that (1) is both sufficient and necessary for the exact measurement of all integer weights X in the range .

Exercises

1. In the basis step of the induction proof, above, a “trivial” weight X was shown to be measurable without using any of the  at all.  Which nontrivial X can always be weighed if (1) holds?
2. Suppose, as in (4), above, that  is an instance where (1) is violated.  Show that the weight  cannot be weighed.

3. It stands to reason that the more that  exceeds  the greater the range of values that cannot be weighed.  Identify such values explicitly.
    

4. Show how (3) above leads to the simple algorithm, secreted in the applet of Part 1, for weighing an unknown weight X in the range .  Suppose that an “elementary computational step” consists of placing (removing) a single weight.  What is the computational complexity of this algorithm?  Is there a faster method?

5. For fixed N, what choice of weights  maximizes the range ?  Show that in this case there is unique placement of weights that measures X.
    

6. Suppose that three of your original set of six balancing weights are missing, and that the remaining three weigh 1, 8, and 70 grams, respectively.  If weights cost 10 cents per gram and you are willing to spend up to $20, which three weights should you purchase to maximize the range?