- #1
Carl1
- 4
- 0
MHB Can You Explain the Puzzle Toad Proof?
- Thread starter Carl1
- Start date
-
- Tags
- Explanation Proof Puzzle Web
Click For Summary
The discussion focuses on clarifying a proof involving a procedure where walkers traverse edges in a specific order, starting from the shortest to the longest. It emphasizes that at each stage, two walkers exchange positions along an edge, contributing to the total distance traveled. The total number of edges traversed is noted as 2m, where m is the number of edges, and with n walkers, the average distance traveled per walker is calculated as 2m/n. This leads to the conclusion that at least one walker must have traveled a distance of 2m/n or more edges. The proof is acknowledged for its elegance and clarity, enhancing understanding of the concept.
- #2
Opalg
Gold Member
MHB
- 2,778
- 13
It would be easier to understand that proof if the second sentence was made more explicit:
At stage $k$ of the procedure, two walkers travel along the edge $e_k$. So the total number of edges traveled during the whole procedure is $2m$. The number of walkers is $n$. So the mean number of edges traveled 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.
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$[/color] ... .
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 traveled 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 traveled during the whole procedure is $2m$. The number of walkers is $n$. So the mean number of edges traveled 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.
- #3
Carl1
- 4
- 0
Thank you so much. Now I understand the proof. It is beautiful.