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 7 of 8: Count the flips and moves
Detailed analysis
In each later block of three laps, every cell is stopped twice. The first stop sees one value and flips it, while the second sees the other value and flips it back, so every cell returns to its previous number. The two stops at a cell consist of one move of length 1 and one of length 2, whose total is .