The Heaviest of Eight

  • Easy
  • Measuring and weighing
  • Tests: Counting eliminations rather than weighings

The puzzle

Eight stones all weigh different amounts. A balance compares two at a time.

How many comparisons are needed to find the heaviest, and why can it not be done in fewer?

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

Each comparison tells you one stone is not the heaviest.

Hint 2

How many stones must be eliminated before one is left?

Show the answer Hide the answer

Seven — one fewer than the number of stones, and no scheme can do better.

How to get there

Every comparison eliminates exactly one stone from contention: the lighter of the two can never be the heaviest. To be certain, seven of the eight must be eliminated, so at least seven comparisons are needed.

Seven also suffice - a knockout tournament uses exactly seven: four first-round matches, two semi-finals and a final.

The bound and the construction agree, so seven is exact. Note how much harder the runner-up is: the second heaviest needs two more comparisons, among the three stones that lost to the champion, for a total of nine.

The technique worth keeping

Count what each step can eliminate at best, then divide the work by it. A lower bound built from eliminations plus a construction that meets it is a complete answer rather than a good strategy.