Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Measuring Weights

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.

Previous Puzzle: Bigger or Smaller

Alice writes two distinct real numbers between 0 and 1 on two chits of paper. Bob selects one of the chits randomly to inspect it. He then has to declare whether the number he sees is the bigger or smaller of the two. Is there any way he can expect to be correct more than half the times Alice plays this game with him?

Next Puzzle: Working Computer

A room has n computers, less than half of which are damaged, others are good. It is possible to query a computer about the status of any computer. A damaged computer could give wrong answers. The goal is to discover a good computer in as few queries as possible.

17 Aug 2011
© Copyright 2008—2017, Gurmeet Manku.