Puzzle: You have a balance and need to weigh objects. The weight of each object will be between 1 and 40 pounds inclusive and will be a round number. What’s the fewest number of weights that you need to be able to balance any of these objects?
(If you think you have the answer, see the Answer before you see the Hint. The answer is just the number of weights, not what they are.)
Hint: Your weights don’t all need to go on the same side of the balance.
Solution: You need weights of 1, 3, 9, and 27 pounds (powers of three). If you want to weigh an object of, say 32 pounds, then on one side of the balance you put the object to be weighed along with the 1 and 3 pound weight. On the other side you put the 9 and 27 pound weight. Both sides add up to the same weight and the balance is horizontal, confirming that the object was 32 pounds.
If your best answer was 6 weights, using the binary scheme of 1, 2, 4, 8, 16, and 32 pounds, then your solution was able to weigh objects up to 63 pounds. This is more than was required (40 pounds), so you know that your solution is not optimal.
Update 9/21/2007: Ken Belcher came up with a clever way to use four weights to weigh items up to 81 pounds. You double the weights above so that you have 2, 6, 18, and 54 pound weights. You then use the above scheme if your test object has an even weight. If it has an odd weight, you test the two even weights around it to show that it's greater than one and less than the other. Since test objects always have weights that are round numbers, you know it must be the odd number between the two even ones.