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 alternately, i.e., his choices would be ..., left, right, left, .... Prove that he will eventually return to his home.
Problem 1128
Official solution
After walking for a long time, he must walk along a certain road 6 times and in the direction at least 3 times. When he reaches the junction along this direction, he must choose the same direction twice. Both times, tracing backwards, we conclude that both times the trails are the same. Since first one traces back to his home, we conclude that the second time, the trails also go back to his home. Thus the boy must return to his home.