Lesson 12

With the theorem we have just proved we can finally solve the Heaviest Stone Problem. We have discussed already that it is not that difficult for the expert to convince the court with \(n-1\) comparisons: for example, she might compare the heaviest stone with all other \(n-1\) stones. To prove that this is optimal, we need to prove the following universal statement: any strategy with less than \(n-1\) comparisons does not reveal the heaviest stone. This can be done as follows. Consider a strategy and associate with it the following graph: nodes are stones, two stones are joined by an edge if they were compared by the expert. Note that we are not even interested in the results of comparisons performed. Now, if there were less than \(n-1\) comparisons, then the graph contains at least two connected components. But this means that the court is still not sure about the heaviest stone! Indeed, after all the comparisons, the heaviest stone may belong to any of the connected components.