https://spherical-harmonics.hateblo.jp/entry/Toritsu/2008/Rikei

2024.09.15記

[3] $N$ 個の数列 $\{a_n^{(1)}\}$ ，…， $\{a_n^{(N)}\}$ はいずれも各項が $1$ か $-1$ のいずれかであり，次を満たすとする．
$a_{n+1}^{(k)} =\left\{\begin{array}{ll} a_n^{(k+1)} & (a_n^{(k)}=1\mbox{のとき}) \\ a_n^{(k-1)} & (a_n^{(k)}=-1\mbox{のとき}) \end{array}\right.$
$(k=1，2，…，N)$ ， $(n=1，2，…)$
ただし， $a_n^{(0)}=a_n^{(N)}$ ， $a_n^{(N+1)}=a_n^{(1)}$ と定める． $m$ を $N$ 未満の自然数とするとき，以下の問いに答えなさい．

(1) $a_1^{(1)}=a_1^{(2)}=…=a_1^{(m)}=1$ ならば， $a_m^{(1)}=1$ であることを示しなさい．

(2) $a_1^{(1)}=a_1^{(2)}=…=a_1^{(m)}=1$ かつ $a_1^{(m+1)}=-1$ ならば， $a_{m+1}^{(1)}=-1$ であることを示しなさい．

(3) 自然数 $n$ に対して， $a_n^{(1)}$ ， $a_n^{(1)}$ ，…， $a_n^{(N)}$ のうちで $1$ であるものの個数を $b_n$ とするとき， $b_{n+1}=b_n$ であることを示しなさい．

本問のテーマ

周期境界条件のルール184（エレメンタリー・）セル・オートマトン（自然渋滞モデル）

2024.09.15記
$n$ は時刻， $k$ は位置を表している．周期境界条件 $a_n^{(0)}=a_n^{(N)}$ ， $a_n^{(N+1)}=a_n^{(1)}$ は $N$ 個の升目が環状になっていると考えれば良い．

一般のセル・オートマトンは， $-1,1$ ではなく $0,1$ で表現する．このとき遷移ルールは

時刻 $n$ の状態（ $a_n^{(k-1)}a_n^{(k)}a_n^{(k+1)}$ ）	111	110	101	100	011	010	001	000
時刻 $n+1$ の状態（ $a_{n+1}^{(k)}$ ）	1	0	1	1	1	0	0	0

となり，このルールを，時刻 $n+1$ の状態 $10111000$ を2進数とみたときの自然数 $184$ を用いて「ルール184」と呼ぶ．

このルールにおいて「0は車がいない状態」，「1は車がいる状態」を表す．そして

ルール1：ある升目に車がいて，次の升目に車がいる場合，その車は動かないので車はいる

ルール2：ある升目に車がいて，次の升目に車がない場合，その車は動いてその升目に車はいなくなる

ルール3：ある升目に車がいなくて，前の升目に車がいる場合，前の升目の車は動いて、その升目に移動してくるので車はいる

ルール4：ある升目に車がいなくて，前の升目に車がない場合，その升目に来る車はないので車はいないままである

というルールであるから，車の自然渋滞モデルとして用いられる．

ルール184 - Wikipedia

[大人の解答]
本問は，周期境界条件のルール184セル・オートマトン（自然渋滞モデル）であり，「 $-1$ は車がいない状態」，「 $1$ は車がいる状態」を表す．

この渋滞のモデルでは時間が1進む毎に渋滞の先頭が解消し，2番目以降は動かないという仕組みになっている．

(1) 第1マスの車は渋滞の先頭から $m$ 番目以降であるから，この車が動くには少なくとも時間が $m$ 以上進まなければならないので，時間が $m-1$ 進んだ時点では動いていないので時刻 $m$ において第1マスには車がいることになり， $a_m^{(1)}=1$ である．

(2) この渋滞のモデルにおいて車が連なっている場合，車がいない場所は1マスずつ後方に移動するので、 $m$ 台以上の車が連なっている渋滞において時間が $m$ 進むと、車がいない場所は丁度 $m$ マス後方に移動するので時刻 $1$ における第 $m+1$ マスの車がいない場所は時刻 $1+m=m+1$ における第 $(m+1)-m=1$ マスに移動しており，よって $a_{m+1}^{(1)}=-1$ である．

(3) 全体の車の台数 $b_n$ は時刻によらないので $b_{n+1}=b_n$ である．

[解答]
(1) $a_1^{(1)}=a_1^{(2)}=…=a_1^{(m)}=1$ より
$a_2^{(1)}=…=a_2^{(m-1)}=1$ ，
$a_3^{(1)}=…=a_3^{(m-2)}=1$ ，
…，
$a_{m-1}^{(1)}=a_{m-1}^{(2}=1$
と逐次的に成立し，よって
$a_m^{(1)}=1$
となる．

(2) $a_1^{(1)}=a_1^{(2)}=…=a_1^{(m)}=1$ かつ $a_1^{(m+1)}=-1$ より
$a_2^{(1)}=…=a_2^{(m-1)}=1$ かつ $a_2^{(m)}=-1$ ，
$a_3^{(1)}=…=a_3^{(m-2)}=1$ かつ $a_3^{(m-1)}=-1$ ，
…，
$a_{m-1}^{(1)}=a_{m-1}^{(2}=1$ かつ $a_{m-1}^{(3)}=-1$ ，
$a_m^{(1)}=1$ かつ $a_{m}^{(2)}=-1$
と逐次的に成立し，よって
$a_{m+1}^{(1)}=-1$
となる．

(3) $a_n^{(k)}$ が $1$ から $-1$ に変化するのは $a_n^{(k+1)}=-1$ のときであり，このとき $a_n^{(k+1)}$ は $-1$ から $1$ に変化するので， $1$ の個数は変化しない．

また， $a_n^{(k)}$ が $-1$ から $1$ に変化するのは $a_n^{(k-1)}=1$ のときであり，このとき $a_n^{(k-1)}$ は $1$ から $-1$ に変化するので， $1$ の個数は変化しない．

よって $a_n^{(1)}$ ， $a_n^{(1)}$ ，…， $a_n^{(N)}$ のうちで $1$ であるものの個数は $n$ によらず一定となり， $b_{n+1}=b_n$ が成立する．

要するに， $a^{(1)}a^{(2)}a^{(3)}\cdots a^{(N)}[a^{(1)}]$ に登場する $10$ を $01$ （ $-1$ を $0$ とした）に書き換えると次の時刻の状態になるのだから，1の数は変わらないということ．