(a) Folklore, (b) Heard from Mudit Goel in 1996 at U C Berkeley.

An individual weight may be (a) not used, (b) placed in the left pan, or (c) placed in the right pan. With n weights, there are 3^{n} such combinations. One of these combinations corresponds to "no weight was used". The remaining combinations can be divided into pairs where weights used in the left pan are swapped with weights used in the right pan. So with n weights, modulo left-right symmetry, the total number of combinations is (3^{n} - 1) / 2. Each combination measures some total weight. Whether these total weights are unique or not depends on the choice of individual weights. It turns out that by choosing weights as powers of 3, the (3^{n} - 1) / 2 combinations correspond to total weights which are all unique. For example, by using weights 1, 3, 9 and 27, there are (3^{4} - 1) / 2 = 40 combinations, each of which measures a unique weight in the range [1, 40]. Why are these total weights unique? Hint: You may prove this either by induction or by noting that every integer has a unique representation in base 3 even if we use digits {-1, 0, 1} instead of {0, 1, 2}.

For part (b), we can exploit the knowledge that the antique weight is an integer and use weights 3, 6, 18 and 54 (each number is twice a power of three). If the weight of the antique lies between two even numbers, it must be odd — we can infer this without actually measuring its weight.

© Copyright 2008—2017, Gurmeet Manku.

Send me email or a
Sarahah message!