第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

とできることを示せ。

ステップ 5/5: 2 の冪より 1 大きい場合

ざっくり言うと

座標を一つ増やすと相殺回数がちょうど n-2 変わる。

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

詳しい解説

同じ漸化式で巡回座標が一つ増えるため端点が一度重なる。反復二乗計算では全 1 状態に対してちょうど n^2-n+1 回が残り、その後すべてのビットが再び 1 になる。第二の評価が示された。