You have 68 coins of different weights. Using only a balance scale and the coins themselves, find the heaviest and lightest of the coins with only 100 comparisons.
This puzzle is adapted from The Mathematical circles (Russian Experience).
Answer
It seems to me that there's a simpler solution than the one accepted above.
Step 1:
Weigh in pairs, as above. 34 weighings. Now we have 34 "light" coins and 34 "heavy" ones, and we want the lightest of the light and the heaviest of the heavy.
Step 2:
Go through the light coins in order. Pick one; that's your lightest so far. Take another, compare it against lightest-so-far. Take another, compare against lightest-so-far. With $n$ coins you need $n-1$ weighings to find the lightest, so this takes you 33 weighings.
Step 3:
Same for the heavy coins. Another 33 weighings. Done.
The point here is that
the "balanced binary tree" structure is very useful when you want more information besides a single winner, but when all you need is a single winner "any tree will do", including the trivial one I've used above.
No comments:
Post a Comment