We will now apply immediately the lower bound that will just prove

this whole the heaviest stone possible.

So recall that in this puzzle when given n stones of different weights.

And the expert would like to convince us that some particular stone is

the heaviest stone.

So she knows the weights of all the stones.

And what she is going to do is to use a pan balance to

repeatedly compare some pairs of stones.

And each time when she compares, the pan balance actually justifies that

some of the stones in this case, this one, is heavier than that one.

Right? So the question is,

what is the minimum number of comparisons?

Let's now first, try to prove some upper bound on the number of comparisons needed.

Let's just, in a sense, let's just design some productal form for

justifying the top particular stone is the heaviest one.

So, one way of doing this in n-1 comparisons is for

example, compare the heaviest stone with all the other n-1 stones.

So indeed, if the expert takes the heaviest stone and

repeatedly compares it to the first remaining stone, and to the second one,

and to the third one, and finally there's n minus first one.

Then after all this n-1 comparisons,

everybody is going to be convinced that this one is indeed the heaviest.

Because the pan balance will reveal that this one is heavier than that one,

that one and so on.

Okay so, in n-1 comparisons we will

convince everybody that particular stone is the heaviest one.

Moreover we can actually, if we order all the stones by their weight,

in advanced before making any comparison.

Then in n-1 comparisons,

we can even reveal the full order of stones, of their weight I mean.

Because if we, for example, assume that we have in stones and

order it such that there is the first one is the lightest one and

the next one goes immediately after that one and so on and so on.

Let's just denote for completeness their weight my w1,

w2 and so on, wn and assumes that they are ordered like this.

w1 is smaller than w2, which in turn is smaller than w3 and

so on which is smaller than wn.

Then we are going to compare it with first three lines.

This will reveal that the first one is indeed lighter than the second one.

Then we are going to compare the second one and the third one, okay?

This will ensure that the third one is heavier than the second one and so on.

So in n-1 comparisons we will actually reveal the full order of these n stones.

And in particular we will prove that the last one is the heaviest one.

So in n-1 comparisons we definitely can convince everybody

that the given stone is the heaviest one.

But still the question is whether this is the optimal number of comparisons.

Namely, can we somehow show that in any other such convincing product roles,

the number of comparisons is at least n-1.

And surprisingly we will show this now using our lower bound for

the number of connected components.

And for this we need a graph and the graph is going to be constructed as follows.

Let's introduce a node for 88 stones.

So it is going to be a graph on the nodes.

And we will join two nodes by an match if there

was a comparison involving these two stones.

So first of all now that we are not even interested in the result of this

comparison, we just reflect the fact that this two stones were compared.

This gives us a graph.

And now the simple but crucial observation is that

if there are less than n-1 edges in this graph,

then the number of connected components in this graph is at least two.

But this actually means that the court or

everybody still knows nothing about the relative comparison

between this part of the stones and that part of the stones.

Mainly, if the situation looks as follows.

So we have some number of stones.

Let me draw them where it is not.

Then what some number of comparisons involving these stones,

and still we have two connected components.

Then the claim is that we still can not be sure in which of these two parts

the heaviest stone, to which of these two parts the heaviest stone belongs.

Just because we haven't yet

compared any stone from the left part with any stone from the right part.

So we know nothing about the relative order of these two parts.

But to make it a little bit more formal, so

assume that the heaviest stone belongs to this component, and

this is this one, okay, this ball vertex.

And then we can actually change the weight of all

the stones in the left part just by adding some huge number to the weight.

If we add the same amount to these three stones, then these two comparisons,

the results of these two comparisons do not change, right?

But, at the same time,

it will mean that the heaviest stone now belongs to this component.

So this is a formal proof, but intuitively it is not so

difficult to see that if there are two groups of stones such

that we never compare with any stone from here to any stone from here.

Then we still don't know where is the heaviest stone, it might be in this part,

it might be in this part.

Which finally proves using our lower bounds for

connected components that n-1 comparisons are,

first of all, required to convince everybody.

And thus we know over the n-1 comparisons there are also enough for

convincing everybody that this particular stone is the heaviest one.