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 6 of 8: Obtain the pattern everywhere
Detailed analysis
Starting from the position supplied by Step 4 and repeatedly applying Step 5 around the circle, every position eventually has the pattern in a common block of three consecutive laps. The no-consecutive-bypasses rule then forces the pattern to persist one lap later: the bypass in the old block is followed by a stop, and the two stops force the remaining entry. Induction gives this pattern for every later block of three laps and every cell.