MathLabs

第4問

n≥3n\ge 3 を満たす整数 n をとる。円周上に nn 個のマスがあり、それぞれに 0 または 1 が割り当てられ、1 羽の雄鶏がそのうちの 1 マスにいる。雄鶏が 0 のマスにいればその数を 1 に変えて反時計回りの次のマスへ進み、1 のマスにいればその数を 0 に変えて反時計回りに 1 マス飛ばした次のマスへ進む、という操作を繰り返す。十分多く操作した後では、雄鶏がマス CC にいるとき必ず円周をちょうど 3 周して再び CC で止まり、その 3 周の直前と直後で各マスの数が同じであることを証明せよ。
ステップ 8/8: 3周後の帰還を結論する
3n3n
詳しい解説

すべての nn 個のマスの寄与を合計すると、以後の各3周ブロックで雄鶏は合計 3n3n マス進む。これはちょうど3周なので、そのブロックをマス CC から始めれば再び CC で停止する。第7段階により各マスの数も元に戻っており、十分後に要求された主張が成り立つ。