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 3 of 8: A stop cannot persist for three laps
Detailed analysis
Suppose a cell is stopped in two consecutive laps. Inspect the value immediately before it when the second stop occurs. If that predecessor is 0, or if the local predecessor pattern is 11, the next lap bypasses the cell. If the predecessor pattern is a maximal block of alternating 10s, the same conclusion follows by following that block for two laps. The only exception is the alternating configuration ; in that configuration the three-lap conclusion can be checked directly, so it is already a terminal cycle.