パズルの国のアリス

スイッチを切り替えるスイッチ(問題)

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

 鏡の国の白の騎士がまた,面白い装置を発明したらしいという噂が流れてきた。好奇心のかたまりのアリスが,早速白の騎士の工房に駆けつけてみると,既にハンプティ・ダンプティや赤白の王室の面々も集まって,かまびすしいことこの上ない。発明品が何なのかとのぞきこんでみると,たくさんのスイッチが輪になってつながっているだけのように見える装置だ。

 「何かのタイマーですか?」とそばにいたハンプティ・ダンプティに聞くと「まあ,そうとも言えるな」と例によって考え深げな応答のあと,「……だが,それ以上だ。なんと,時間が来ると隣のスイッチを切り替えるというスイッチだからな」。

 「???」アリスがキョトンとしていると,実演が始まった。確かにハンプティの言うとおりで,最初は全部のスイッチがオンになっていたのだが,自分の番が来たときにオンになっていたスイッチは,時計回り方向の隣のスイッチに信号を送り,そのスイッチのオン・オフを切り替えるらしい。順繰りに番が来るようにタイマーがセットされていて,あるスイッチの次に番が来るのは時計回りにその隣にあるスイッチだ。自分の番のときオフであれば,そのスイッチは何もしないで次の番のスイッチに移る。

 装置はひたすらに,ただ各スイッチのオン・オフを繰り返していたが,全部のスイッチがオンという最初の状態に戻ったとき,集まっていた見物衆から拍手と喝采が上がった。

 「ほら,どうだ。すごいじゃないか」とハンプティから同意を求められても,アリスは大きかった期待に比例する脱力感で声が出なかったが,読者は,脱力していないで問題を考えていただきたい。

 まず,ウォーミングアップとして,この装置では(スイッチが2つ以上つながっていれば)すべてのスイッチがオフになることはないことを証明していただきたい。次に,この奇妙な装置は,輪になってつながったスイッチの数が何個であろうと,全部がオンという最初の状態に必ず戻るかどうかを考えていただこう。最初の状態に戻らない場合があるだろうか?

解答はこちらです