Lesson 2

If there are \(n=2\) stones, then the minimum number of comparisons is one. Indeed, by comparing the two stones, the expert reveals the heaviest one among the stones. On the other hand, at least one comparison is needed in any case.

What is the minimum number of comparisons for \(n=3\) stones? It is intuitively clear that one comparison is not enough in this case: if the expert compares some two stones, then the court knows nothing about the remaining stone. At the same time, the expert can convince the court by three comparisons. To do this, she just compares all three pairs: 1 versus 2, 2 versus 3, and 1 versus 3.

Can the expert use two comparisons only? It is not difficult to come up with a strategy: the expert first compares the heaviest stone to some of the remaining two stones, she then compares the heaviest stone to the only remaining stone. This way, the court sees clearly that the supposedly heaviest stone is indeed heavier than all other stones. It is straightforward to generalize this strategy to an arbitrary number \(n\) of stones: by comparing the heaviest stone to each of the remaining \((n-1)\) stones, the expert reveals the heaviest stone to the court.

Can you prove that no strategy with less than \(n-1\) comparisons can convince the court?