Puzzle: (a) Customers at a grocer's shop always want an integral number pounds of wheat, between 1 pound and 40 pounds. The grocer prefers to measure wheat in exactly one weighing with a beam balance. What is the least number of weights he needs? (b) Customers come to a pawn shop with antiques. An antique always weighs an integral number of pounds, somewhere between 1 pound and 80 pounds. The owner of the pawn shop is free to do as many weighings as necessary to ascertain the unknown integral weight by using a beam balance. What is the least number of weights he needs?
Source: (a) Folklore, (b) Heard from Mudit Goel in 1996 at U C Berkeley.
Solution: 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 3n 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 (3n - 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 (3n - 1) / 2 combinations correspond to total weights which are all unique. For example, by using weights 1, 3, 9 and 27, there are (34 - 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.
