第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

とできることを示せ。

ステップ 1/5: ランプを符号化する

ざっくり言うと

順次更新なので各ランプは更新済みの前のランプに依存する。

x_i\in\mathbb F_2

詳しい解説

$L_i$ が点灯なら $x_i$ は 1、消灯なら 0 とする。反転は二元体で 1 を加えること。1 周の後の値は $y_0=x_0+x_{n-1}$ 、 $i$ は 1 から $n-1$ までとして $y_i=x_i+y_{i-1}$ を満たす。