第6問

円周上に

n

個のランプ

L_0,\ldots,L_{n-1}

があり、

n>1

、

L_{n+k}=L_k

とする。ステップ

s_i

では、

L_{i-1}

が点灯していれば

L_i

を反転し、そうでなければ何もしない。初めは全ランプが点灯している。(a) ある正整数

M(n)

が存在し、

M(n)

回後に全点灯へ戻ることを示せ。(b)

n=2^k

なら

M(n)=n^2-1

とできることを示せ。(c)

n=2^k+1

なら

M(n)=n^2-n+1

とできることを示せ。

ステップ 3/5: 一般の復帰を示す

ざっくり言うと

全点灯軌道上の可逆性だけで (a) が得られ、全状態での可逆性は不要。

T^r(u)=u\text{ for some }r>0,\quad u=(1,\ldots,1)

詳しい解説

全て 1 のベクトルから始まる軌道に漸化式を逆向きに適用する。同じ部分和計算で各周の軌道上の前状態を一意に復元できるので、軌道は過渡でなく周期である。状態数は有限だから正の r で u に戻り、M(n)=nr に必要な部分周を加えればよい。