Both Ends at Once

  • Hard
  • Measuring and weighing
  • Tests: Pairing before comparing

The puzzle

Ten parcels have ten different weights. A balance compares two parcels and names the heavier.

Find the heaviest parcel and the lightest parcel. The naive approach - find the heaviest in nine comparisons, then the lightest in eight more - costs 17. Thirteen is enough.

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

Compare the parcels in pairs first, before comparing anything to a running champion.

Hint 2

A parcel that lost its pairing cannot be the heaviest, and one that won cannot be the lightest.

Show the answer Hide the answer

Thirteen. Five comparisons to pair them off, then four to find the heaviest among the five winners and four to find the lightest among the five losers.

How to get there

Split the ten parcels into five pairs and compare each pair: 5 comparisons. Every parcel is now labelled winner or loser.

The heaviest parcel must be a winner - it never loses to anything - so search only the five winners, which takes 4 comparisons. The lightest must be a loser, so search the five losers: 4 more.

5 + 4 + 4 = 13. The general count is 3n/2 - 2, here 15 - 2 = 13, and it beats the naive 2n - 3 = 17 because the pairing round halves both search spaces at once instead of serving only one of them.

The technique worth keeping

One comparison can serve two goals if it is placed before either search begins. Pairing is the standard opening for simultaneous max-and-min problems, and the saving grows linearly with n.