MathLabs

第4問

n≥3n\ge 3 を満たす整数 n をとる。円周上に nn 個のマスがあり、それぞれに 0 または 1 が割り当てられ、1 羽の雄鶏がそのうちの 1 マスにいる。雄鶏が 0 のマスにいればその数を 1 に変えて反時計回りの次のマスへ進み、1 のマスにいればその数を 0 に変えて反時計回りに 1 マス飛ばした次のマスへ進む、という操作を繰り返す。十分多く操作した後では、雄鶏がマス CC にいるとき必ず円周をちょうど 3 周して再び CC で止まり、その 3 周の直前と直後で各マスの数が同じであることを証明せよ。
ステップ 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 に変わっている。したがって同じマスが連続する2周で通過されることはない。通過された後は関係する直前の値が変化するため、次の局所的な通過ではそこで停止する。また直接調べると、01 に続くマスはその周で通過される。