Welcome to our community

Be a part of something great, join today!

Pigeonhole Principle Problem

Carl

New member
Jun 6, 2017
4
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.
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,707
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.
 

Carl

New member
Jun 6, 2017
4
Very clearly explained. Thank you.