MathLabs

第4题

设 n≥3n\ge 3 为整数。圆周上有 nn 个格子，每个格子赋值为 0 或 1，一只公鸡位于其中一个格子。反复进行如下操作：若公鸡位于赋值 0 的格子，就把该数改为 1，并逆时针移动到下一个格子；若公鸡位于赋值 1 的格子，就把该数改为 0，并逆时针跳过一个格子移动到下下个格子。证明经过充分多次操作后，每当公鸡位于格子 CC，它恰好绕圆周三周并再次停在 CC，且每个格子的数都与这三周开始之前的数相同。
第 2/8 步：记录跳过的基本规则
上一步下一步
a bypass is preceded by 1 and changes that predecessor to 0\text{a bypass is preceded by }1\text{ and changes that predecessor to }0
详细分析

若一个格子被跳过，公鸡必定从它前面的格子跳来；前一格原为 1，并在操作后变为 0。因此同一格子不可能在连续两圈中都被跳过：被跳过后，相关的前一格已经改变，下一次局部经过时必会在此停止。直接检查还可知，紧接在 01 后面的格子在该圈会被跳过。