A problem from the Leningrad Mathematical Olympiad: You have 32 stones, each of a different weight. How can you find the two heaviest in 35 weighings with an equal-arm balance?
|
SelectClick for Answer> |
Think of the stones as tennis players and put them through a singles tournament. There are no upsets: In each match (weighing), the better (heavier) player always wins and goes on to the next round. With 32 players, this will produce a tournament with five rounds, comprising 16, 8, 4, 2, and 1 matches, successively, enough to produce 31 losers and identify the best (heaviest) stone.
Now, the second-heaviest stone must have “lost” to the heaviest at some point in the tournament (since that was the only “player” strong enough to beat it). So take the five players beaten by the heaviest stone and put them through a little tournament of their own. Four matches will be enough to find the strongest of these five, and that must be the second-heaviest stone overall.
(Via Ross Honsberger’s Mathematical Delights, 2004.)
|