パズルの国のアリス

回転テーブルとスイッチ(解答)

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

 最初の問題の場合,各スイッチは区別がつくので,n個のスイッチがあるとして,それに1からnまでの番号を振っておこう。重複がないようにスイッチ状態を順次作り出していく手順はいろいろと考えうるが,比較的簡単でシステマティックなやり方の1つは次のようなものだ。

 奇数回目の操作では常にスイッチ1を押す。奇数の2倍回目の操作ではスイッチ2を押す。奇数の4倍回目の操作ではスイッチ3を押す。……以下同様に奇数の2n倍回目の操作ではスイッチn+1を押す。最初の状態からみて,オンオフが入れ替わっているスイッチを1,同じ状態のスイッチを0で表し,右から順に並べた2進数でスイッチ全体の状態を表現するなら,たとえば,スイッチ数nが4の場合,操作回数が増えるにつれて状態は左下の表のように変化する。

201601-a-img この表には,全スイッチ状態がもれなく現れ,同じものはない。そのことはすぐに見て取れるし,一般のnについて証明したければ,nに関する数学的帰納法で簡単にできる。したがって,最初のスイッチ状態がどうであろうと15回以内(一般には2n−1回以内)の操作で全てのスイッチがオンになる。たとえば,最初の状態では,2番のスイッチだけがオンで1,3,4番がオフだったとすれば,電灯をつけるには1,3,4番のスイッチを反転させればよい。その状態1101には9回目の操作でたどり着く。

 表の「回数」を「状態」で表現した2進数は,グレイコードと呼ばれ,計数器などに使う技術として米国で特許がとられたことで有名だ。グレイコードは,隣り合う2つの数を表現する2進数の間に1ビットの違いしかないという特徴があり,それが上の問題の解の構成に使えたゆえんである。パズル玩具に詳しい読者は,ハノイの塔やチャイニーズリングの解法とも密接な関係があることをご存知だろう。

 次の問題は,相対的にしか各スイッチの区別がつかなくなるので厄介だ。だが,スイッチ数が2の場合は,少し考えれば,うまいやり方を思いつくだろう。最初から電灯がついていないならば,両スイッチのうち,少なくとも片方はオフだ。そこで,ヤマネたちは両スイッチを同時に押す(この操作を「P」と呼ぶ)。もし両方ともオフなら,そこで電灯がつくはずだ。つかなかったとしたら,スイッチは一方がオフでもう一方がオンだ。テーブルが回転してもその状況は変わらない。そこで次にはどちらか片方のスイッチを押す(この操作を「S」と呼ぶ)。そのスイッチがオフだったなら,電灯がつくはずだ。そうでなくとも,今度は両スイッチともにオフになる。したがって,次に両ボタンを同時に押せば電灯は点灯する。つまり「PSP」という操作により,3回以内で目的は達成される。

 では,スイッチが4つの場合はどうだろうか? 一気に解決するのはかなり大変そうなので,順次考えていこう。最初に全部のスイッチを押してみる(この操作を「全」と表現する)。もし全部がオンならば,最初から電灯がともっているし,全部がオフならばこの時点でつく。つまり,ここで電灯がつかなければオンオフが交じっていることになる。オンとオフが奇数個の場合は後に回し,2ー2に分かれている場合を先に考えよう。オンを0,オフを1で表現すると,この場合,時計回りに0011と0101となっている2通りが考えられる(もちろん,これらが順繰りに回転していることもあり得るのだが,帽子屋たちの邪魔が入ることが前提なので,それらを区別しても意味がない)。そこで次には対面にある2つのスイッチだけを押してみよう(この操作を「対」と表現する)。すると,0101は0000か1111に変わる。0000に変わった場合,そこで電灯がつくし,1111ならもう一度全スイッチを押してやればいい。こうして「全対全」という操作により,最初の状態が0000,1111,0101の場合は電灯がともる。0011は駄目だが,その場合はそのあとも状態が変わらず0011のままだ。そこで,次には隣同士の2つのスイッチを選んで押してみよう(この操作を「隣」と表現する)。するとどこの2つを選ぶかによるが,0011は0000,1111,0101のいずれかに変わる。したがって,このあとに「全対全」という操作をやると,どこかで電灯がつくことになる。つまり,スイッチのうち偶数個がオンの場合,「全対全隣全対全」という操作により,7回以内に目的に達する。奇数個がオンの場合は駄目だが,これらの操作後もオンが奇数個という状況は変わることがない。そこで,次に1個のスイッチを押してみよう(この操作を「単」と表現する)。するとオンのスイッチ数は偶数個に変わる。したがって,そのあとに「全対全隣全対全」という操作を行えば電灯はともる。結局,「全対全隣全対全単全対全隣全対全」という操作により,最初のスイッチの状態がどうであれ,(たかだか15回で)点灯させることができる。

 これをさらにスイッチ数nが2や4以外の場合に一般化するという問題は難しい。しかし,実はnが2のベキ2kの形をしているなら可能であり,たとえば,n=8=23の場合,確実に点灯させる手段はある。その方法では,最悪の場合28−1=255回の操作が必要になりあまり現実的とはいえないような印象を受けるが,スイッチが8個もあると,最初から点灯している場合を除いた28−1通りのパターンを試すことは所詮必要なので,この操作回数自体は仕方がなく,むしろ最善といえるかもしれない。また,n=16の場合には16個のスイッチをすべて同時に押さねばならないことがあるので,姪たち以外に応援してくれる者がないと,各人が2つずつ同時にスイッチを操作するというような必要が生ずる。

 n=2kの解手順からn=2k+1の解手順をどのように構成するか述べよう。n=2kの場合に,r回以内に電灯をともす手段があるとして,その手順をXx1x2xrとしよう。各xiは2k個のスイッチに対する操作から構成されているが,xi′で2k+1個のスイッチに対してxiをコピーして行う操作を表そう。つまり,2k+1個のスイッチのうち対面に位置する2つのスイッチには同じ操作を行うことになる。先のスイッチが2個の場合と4個の場合に当てはめれば,P′=全,S′=対である。また,xi″で相続く半分のスイッチ2k個に対してはxiと同じ操作を行い,残りの2k個に対しては何もしないという操作を表そう。同様にスイッチが2個の場合と4個の場合に当てはめれば,P″=隣,S″=単である。すると,YPSP′とおけば,4個の場合の手順「全対全隣全対全単全対全隣全対全」はYPYSYPYと表すことができる。一般には,これを拡張してYを手順x1x2′…xr′とするなら,n=2k+1の場合の解手順はYx1Yx2″…YxrYと表せる。これでうまくいくことの厳密な証明は省略するが,概略を述べると,各Yは対面同士のスイッチが全て同じ状態の場合に電灯をつけるための手順であり,x1x2″…xr″はそうでない場合に対面同士を同じ状態にするための手順である。

 nが奇素数を因数に持つ場合には,電灯を確実に点灯させる手段は存在しない。これも厳密な証明は面倒だが,多少事情を説明すると,たとえばn=3の場合,スイッチの状態が000か111ならば,簡単に点灯させることができる。しかし,それ以外の001や011の場合を有限回で確実に000や111に持っていく手段がないからだ。一般には,各スイッチのオンオフ状態が周期2kを持つなら,先の操作を拡張した手順で全スイッチをオンにすることができるが,帽子屋たちによる邪魔があると,そうでない状態から周期2kを持つ状態へ確実に進む手段は存在しない。

参考にした本
Mathematical Puzzles:A Connoisseur's Collection(2004),
Mathematical Mind-Benders(2007) P. Winkler。
邦訳は『とっておきの数学パズル』(2011年),『続・とっておきの数学パズル』(2012年),ピーター・ウィンクラー著,坂井公・ 岩沢宏和・小副川健訳,日本評論社。

問題はこちらです