Welcome to our community

Be a part of something great, join today!

In the Puzzle Toad web site I found the problem and solution displayed below. I am unable to follow the proof. Can anyone offer an explanation ?

Carl

New member
Jun 6, 2017
2
1591811875322.png
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,676
It would be easier to understand that proof if the second sentence was made more explicit:

Then go through the edges of $E$ one by one in order, starting with the shortest edge $\color{red}e_1$ and finishing with the longest edge $\color{red}e_m$ ... .​
At the $k$th stage of this procedure, when you come to the edge $e_k = (u,v)$, the walkers currently at its endpoints $u$ and $v$ change place by walking along $e_k$. If they have not previously moved then that will be the first leg of their walk. But if one or both of them have already moved during a previous stage of the procedure, they will have moved along edges shorter than $e_k$. When the procedure ends (with the walkers at the endpoints of $e_m$ changing places), each walker will have travelled along some increasingly long sequence of edges.

At stage $k$ of the procedure, two walkers travel along the edge $e_k$. So the total number of edges travelled during the whole procedure is $2m$. The number of walkers is $n$. So the mean number of edges travelled by a walker is $2m/n$, and therefore at least one of the travellers must have walked along $2m/n$ or more edges.

As the Puzzle Toad site mentions, it is indeed a beautiful proof.
 

Carl

New member
Jun 6, 2017
2
Thank you so much. Now I understand the proof. It is beautiful.