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 2 of 8: Record the elementary bypass rules
Detailed analysis
If a cell is bypassed, the rooster must have jumped from the preceding cell, whose value was 1 and was changed to 0. Consequently no cell is bypassed in two consecutive laps: after being bypassed, the relevant preceding value has changed, and the next local passage must stop there. A direct inspection also shows that a cell preceded by 01 is bypassed in that lap.