第4問

n\ge 3

を満たす整数 n をとる。円周上に

n

個のマスがあり、それぞれに 0 または 1 が割り当てられ、1 羽の雄鶏がそのうちの 1 マスにいる。雄鶏が 0 のマスにいればその数を 1 に変えて反時計回りの次のマスへ進み、1 のマスにいればその数を 0 に変えて反時計回りに 1 マス飛ばした次のマスへ進む、という操作を繰り返す。十分多く操作した後では、雄鶏がマス

C

にいるとき必ず円周をちょうど 3 周して再び

C

で止まり、その 3 周の直前と直後で各マスの数が同じであることを証明せよ。

ステップ 7/8: 反転回数と移動距離を数える

前のステップ次のステップ

1+2=3

詳しい解説

以後の各3周ブロックでは、すべてのマスで2回停止する。1回目は一方の値を見て反転し、2回目はもう一方の値を見て反転し直すので、各マスは直前の数に戻る。1マスでの2回の停止は長さ1の移動と長さ2の移動からなり、その合計は $1+2=3$ である。