# Pigeonhole Principle Problem

#### Carl

##### New member
The following problem and solution (Problem 7 - African Rally) is presented in "the Art of Mathematics" by Bela Bollobas:

Its solution is

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

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
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
Very clearly explained. Thank you.