第4题

设

n\ge 3

为整数。圆周上有

n

个格子，每个格子赋值为 0 或 1，一只公鸡位于其中一个格子。反复进行如下操作：若公鸡位于赋值 0 的格子，就把该数改为 1，并逆时针移动到下一个格子；若公鸡位于赋值 1 的格子，就把该数改为 0，并逆时针跳过一个格子移动到下下个格子。证明经过充分多次操作后，每当公鸡位于格子

C

，它恰好绕圆周三周并再次停在

C

，且每个格子的数都与这三周开始之前的数相同。

第 1/8 步：定义圈与局部访问

0,1,\ldots,n-1\text{ cyclically; one lap has total advance }n

详细分析

将格子循环编号为 $0,1,\ldots,n-1$ 。公鸡每绕圆周一圈记为一圈；若它在该圈中对某格子操作，就称该格子在此圈停止，否则称其被跳过。每次移动一格或两格，所以任意连续两个格子中至少有一个会被停止。