第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

とできることを示せ。

ステップ 4/5: 2 の冪の場合

ざっくり言うと

F_2 上のフロベニウス二乗が 2 の冪で漸化式を縮約する。

n=2^k\Longrightarrow M(n)=n^2-1

詳しい解説

n が 2 の冪なら F_2 上の部分和漸化式を繰り返し二乗する。端点間の二項係数は対で消え、座標更新語は u 上で n^2-1 回後に恒等へ縮約する。従って指定値が有効である。