パズルの国のアリス

スイッチを切り替えるスイッチ(解答)

坂井 公(筑波大学) 題字・イラスト:斉藤重之

 そのとき隣に信号を送る番になっているスイッチを信号係と呼ぶことにしよう。

 まず,全部がオフになることがないことの証明だが,これはちょっと考えれば当たり前なので,バカにするなと読者からお叱りを受けそうで心配だ。最初は全部がオンだったのだから,全部オフになることがあるとすれば,その直前の状態は,1つを除いて全部オフということになっている。ところが,この最後のスイッチがオフになるためには,その上流の信号係から切り替えの信号が来なければならないが,信号係はオフなのでそんなことはありえない。

 次に全部がオンという初期状態に戻らないことがあるかどうかだが,スイッチの数を増やしながら少し実験してみると,例外なく初期状態に戻るので,予想は容易につく。さて,その証明だが,実はこの種のことを示す手法を2012年6月号の「アイスクリームケーキの怪」でも用いている。つまり,状態の有限性と状態遷移の可逆性だ。

 スイッチに1から順の番号を時計回りに振ることにする。そのとき信号係の番号と各スイッチのオン・オフの状況を,装置全体の状態と考えると,考えうる状態は全部で有限種類しかない(正確には,スイッチの個数がnであれば,2n×n種類の状態がある)。

 現在の状態からはもちろん次の状態がわかる。たとえば,今,信号係はi 番のスイッチでそれがオンであったとしよう。次の状態では,信号係はi +1番になり(この番号はnを法として考える,つまりinなら1番に戻る),そのスイッチの状態はオン・オフが反転することがわかる。しかし,現在の状態からは,その直前の状態がどうであったかもわかるのだ。すなわち,直前の状態では,信号係はもちろんi -1であり,それがオフであれば,i 番のスイッチはそのときもオンであったが,i -1番がオンであれば,i 番のスイッチはそのときはオフであった。

 したがって,状態遷移は逆にたどることも可能であり,ある状態に至る直前の状態はただ1つしかない。状態全体は有限種類しかないので,どの状態から始めてもやがてある状態が再現することになる。

 初めてそれが起こる時点を考えると,それがそもそもの初期状態でないと,その状態になる直前の状態がすでに2回出現していたことになり,「初めて起こる」という前提と矛盾するというわけだ。

 実際に,装置の動きをシミュレートしてみるとなかなか面白い。全スイッチがオフの場合は,その状態がいつまでも続くだけだが,それ以外の場合は,途中で実に様々なパターンが現れる。n=2,3,4の場合,スイッチが全オフではない状態から始めると,それらの状態がすべて出現したあとで初期状態に戻る。つまり状態全体が2分類され,「全オフ」と「オンあり」でそれぞれループを形成する。一方n=5,6の場合は,状態全体は,それぞれループを形成する4グループに分割される。nの値によりこれらの構造がどうなっているかを調べるのも面白いかもしれない。

参考にした本
Mathematical Puzzles:A Connoisseur's Collection(2004)
Mathematical Mind-Benders(2007) P. Winkler著

問題はこちらです