The Best and the Second Best

  • Hard
  • Measuring and weighing
  • Tests: Reusing information from a knockout

The puzzle

Eight stones all weigh different amounts. A two-pan balance compares exactly two stones at a time and tells you which is heavier.

Find both the heaviest and the second heaviest. Nine comparisons suffice - and fourteen, the obvious count, is far too many.

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

Run a knockout tournament. How many matches does it take to crown a winner among eight?

Hint 2

The second heaviest must have lost - but only ever to the winner.

Show the answer Hide the answer

Nine: seven matches to find the heaviest, then two more among the three stones that lost directly to it.

How to get there

A knockout tournament with eight stones has four first-round matches, two semi-finals and a final: 7 matches, each eliminating one stone, which is the minimum to find a single winner.

The second heaviest cannot have lost to anyone but the champion - if it had, that stone would be heavier than it. In an eight-stone bracket the champion beat exactly three stones: one in each round. So the runner-up is one of those three.

Finding the heaviest of three takes two more comparisons. Total 7 + 2 = 9. The general formula is n - 1 + ceil(log2 n) - 1, which for n = 8 is 7 + 3 - 1 = 9, and it is known to be optimal.

The technique worth keeping

A tournament records more than its winner: it records who lost to whom. Before running fresh comparisons, ask which candidates the existing results have already eliminated - here five of the seven losers are ruled out for free.