Sorting Five With Seven Weighings

  • Hard
  • Measuring and weighing
  • Tests: Bounding a problem by counting outcomes

The puzzle

Five stones all weigh different amounts. A balance compares two at a time and says which is heavier.

How many comparisons are needed in the worst case to put all five in order? Show that six cannot be 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

Count the possible answers: five stones can be in 5! = 120 orders.

Hint 2

Each comparison has two outcomes, so n comparisons distinguish at most 2^n cases.

Show the answer Hide the answer

Seven. Six comparisons distinguish at most 64 orders and there are 120, so six is impossible; a careful seven-comparison scheme exists.

How to get there

There are 5! = 120 possible orderings and each comparison answers yes or no, so after n comparisons at most 2^n orderings can have been told apart. 2^6 = 64, which is less than 120, so six comparisons cannot always work.

2^7 = 128, which is at least 120 - so seven is not ruled out, and a scheme does exist: sort two pairs (2 comparisons), compare the pair winners (1), then insert the remaining stone and the smaller winner by binary insertion (4). Seven in all.

The bound and the scheme agreeing is what makes seven the answer rather than merely an upper limit. They do not always agree - for five elements they do, but the information bound for twelve elements is 29 while the true answer is 30.

The technique worth keeping

Compare the number of possible answers with the number of outcomes a procedure can produce. If cases exceed outcomes the procedure is impossible, and when a construction meets the bound you have proved optimality rather than guessed it.