A boy lives in a small island in which there are three roads at every junction. He starts from his home and walks along the roads. At each junction he would choose to turn to the road on his right or left alternatively, i.e., his choices would be . . ., left, right, left,... Prove that he will eventually return to his home.
Problem
Source: SMO 2015 open, 2nd round
Tags: graph theory, Sequences
08.04.2018 09:57
Let $G=(V,E)$ be the graph of this island(each junction is a vertex and each road is an edge).Let $|V|=n$ then $|E|=\frac{3n}{2}$. Let us construct triples $A_1,A_2,\dots$ with $A_i=\{a_i,b_i,c_i \}$ as following: 1-$a_i \in V$ for all $i$, and is the vertex that boy reaches in step $i$. 2-$b_i \in E$ for all $i$, and its the edge that boy has used to reach $a_i$. 3-$c_i \in \{L,R\}$ for all $i$, showing the direction he choose to reach $a_i$(left or right) Obviously,if for some $i$,we know $A_i$,then we can construct $A_{i-1},A_{i-2},\dots A_1$ uniquely. Every $A_i$ can take one of the $3n^2$ possible values($n$ possibility for $a_i$,$\frac{3n}{2}$ possibility for $b_i$ and 2 possibility for $c_i$),so by PHP,there exists $i<j$ such that $A_i=A_j$ so obviously $A_{j-i+1} =A_1$ and we are done.
08.04.2018 22:38
i don't think u need to calculate number of vertices and edges. all you need to say is that there are a finite number of $A_i$
12.06.2020 19:58
One could also say that no cycles are possible, i.e there is not a closed path in the graph that the boy can enter (meaning his home is not a vertex in the path) without getting himself out in a finite number of steps. Indeed, if he enters at vertex V, he will leave either the second time he reaches V, or the second time he reaches the next vertex in the closed path (depends on if the lenght of the path is odd or even). Basically, we exploit the fact that he arrives at V from two different directions. Of course if there are no closed paths he will visit every vertex again and again