第4题

设

n\ge 3

为整数。圆周上有

n

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

C

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

C

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

第 3/8 步：停止不能持续三圈

1010\ldots10

详细分析

设某格子在连续两圈中都停止。考察第二次停止时它前面的数。若前一格为 0，或前面的局部模式为 11，则下一圈会跳过该格子。若前面的模式是极大的交替 10 块，跟踪该块两圈也得到同样结论。唯一例外是交替配置 $1010\ldots10$ ；在此配置中可直接验证三圈结论，因此它本身已经是终端周期。