第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

とできることを示せ。

ステップ 2/5: 1 周の線形写像

ざっくり言うと

無限に見える過程は有限線形力学系である。

T(x_0,\ldots,x_{n-1})=(y_0,\ldots,y_{n-1})

詳しい解説

この漸化式は 2^n 個の二進状態からなる有限ベクトル空間上の線形写像 T を定める。元の過程は座標更新を周期的に行い、n ステップ写像が T である。