Problem 4
Let be an integer. There are cells on a circle, each assigned either 0 or 1, and a rooster occupies one cell. Repeatedly, if the rooster is on a cell assigned 0, it changes that number to 1 and moves to the next cell counterclockwise; if it is on a cell assigned 1, it changes that number to 0 and moves to the cell after next counterclockwise. Prove that after sufficiently many operations, whenever the rooster is on a cell , it goes around the circle exactly three times and stops again at , while every cell has the same number as it had immediately before those three laps.
Step 4 of 8: Find an initial three-lap pattern
Detailed analysis
Some position is stopped in infinitely many laps, because there are finitely many positions. Each time the rooster stops at , the local transition changes whether it stops or bypasses the next position. Hence the next position is stopped and bypassed infinitely often. Choose a lap where it is stopped and the following lap where it is bypassed; by the preceding rule it is stopped again on the next lap. Thus one position has two stops and one bypass in three consecutive laps.