11 - Problem G: Solution

Summary

For brevity we shall often omit the word ‘grams’ in this discussion. Suppose that we can weigh the amounts 1, 2, … , 7 with the weights a1, … , ak, where we may assume that 1 ≤ a1 ≤ · · · ≤ ak. We must have a1 = 1, else we cannot weigh one gram of the chemical. If a2 ≥ 3 then we cannot weigh two grams; thus a2 is 1 or 2.Nowa1 = 1 and a2 = 2 is probably (but not certainly) a better choice than a1 = a2 = 1, for the first choice allows us to weigh 1, 2 and 3 grams, whereas the second choice only gives us 1 and 2 grams. Thus we shall try for a solution with a2 = 2. We can now weigh 1, 2 and 3 grams using only a1 and a2. If we take a3 = 4, we can then weigh 1, 2, 3, 4, 4 + 1, 4 + 2, 4 + 3 grams and we are done. Thus if N = 7 then one possible set of weights is 1, 2, 4. Is this the smallest number of weights and, if it is, is this the only possible set of three weights?

Suppose that the weights a1, … , ak allow us to weigh each of the amounts 1, 2, … , 7. Then the amounts that we can weigh are the numbers ϵ1a1 +· · ·+ϵkak, where each ϵj is 0 or 1, and not all are 0. This allows us to weigh at most 2k − 1 different positive amounts, so we need 2k − 1 ≥ 7. Thus k ≥ 3, so that we shall always need at least three weights. Now suppose that a1, a2, a3 is any set of weights which allows us to weigh each amount 1, 2, … , 7. We may assume that a1 ≤ a2 ≤ a3, and a1 = 1. The possible amounts we can weigh are ϵ1a1 + ϵ2a2 + ϵ3a3, where each ϵj is 0 or 1, and with these we can weigh at most seven different positive weights.