MathLabs

Problem 4

Let n≥3n\ge 3 be an integer. There are nn 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 CC, it goes around the circle exactly three times and stops again at CC, while every cell has the same number as it had immediately before those three laps.
Step 1 of 8: Encode laps and local visits
Previous stepNext step
0,1,…,n−1 cyclically; one lap has total advance n0,1,\ldots,n-1\text{ cyclically; one lap has total advance }n
Detailed analysis

Number the cells 0,1,…,n−10,1,\ldots,n-1 cyclically. Divide the infinite motion into laps, each time the rooster completes one circuit, and call a cell stopped in a lap if the rooster acts on it during that lap; otherwise call it bypassed. A move advances by one or two cells, so the rooster stops at at least one of every two consecutive cells.