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).
Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.Sign up to join this community
It seems to me that there's a simpler solution than the one accepted above.
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.
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.
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.
Group all coins in pairs, weighing one against the other - 34 weighings. Make one group of the heavier ones, and one group of the lighter ones. You know that the heaviest is necessarily in the first group, and the lightest is necessarily in the second group.
taking the 34 "heavier" coins, you make 17 weighings, giving you again 2 groups
discard the lighter ones from step 2, and using 9 weighings you will find 8 coins that are at least heavier than one coin
discard the lighter ones from step 3, and using 4 weighings, you will find 4 coins that are at least heavier than one coin
discard the lighter ones from step 4, and using 2 weighings you will find 2 coins that are at least heavier than one coin
one last weighting and you know which one is the heaviest of the 68 coins
repeat Step 2-6 on the "lighter" group from step 1, but this time always choosing the lighter coins and discarding the heavier ones instead
This makes a total of:
34 (step 1) + 2*17 (2) + 2*9 (3) + 2*4 (4) + 2*2 (5) + 2*1 (6) = 100