MHB What is the Pigeonhole Principle Problem in the African Rally?

  • Thread starter Thread starter Carl1
  • Start date Start date
  • Tags Tags
    Principle
AI Thread Summary
The discussion revolves around the Pigeonhole Principle as applied to the African Rally problem from "The Art of Mathematics" by Bela Bollobas. The problem posits that starting from any town, a driver will eventually run out of fuel before completing the circuit. By defining towns using indices, the solution illustrates that if one continues to identify towns that cannot be reached, a repetition of towns must occur due to limited fuel, contradicting the assumption of sufficient fuel for a full circuit. This contradiction highlights the implications of the Pigeonhole Principle in this context. The explanation is noted as clear and helpful for understanding the problem.
Carl1
Messages
4
Reaction score
0
The following problem and solution (Problem 7 - African Rally) is presented in "the Art of Mathematics" by Bela Bollobas:

1594752295082.png


Its solution is
1594752840734.png

I am fine until I get to the sentence that starts
1594753032982.png
...

and then I'm lost in trying to understand the use of the i and j indices. Any help would be appreciated.
 
Physics news on Phys.org
The idea is this. We are supposing that no matter which town you start from, you cannot drive round the entire circuit without running out of fuel at some stage. So starting from town $k_i$, let town $k_{i+1}$ be the first town on the circuit that cannot be reached. (In terms of Bollobas's notation, this means that $S[k_i,k_{i+1})<0$.) Now start at town $k_{i+1}$ and let town $k_{i+2}$ be the first town that you cannot reach from there. If you continue this process, you must eventually (pigeonhole principle!) come to a town that has already appeared in this sequence. So during that journey you will have completed a number ($m$) of complete circuits, in stages each of which involve running out of fuel. But that contradicts the fact that there is sufficient fuel to allow for a full circuit to be completed.
 
Very clearly explained. Thank you.
 
Back
Top