パズルの国のアリス

コイン投げ神託で数当て(解答)

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

 

解答例まず,カードもコインも2枚の場合を考えてみよう。これは簡単だ。2枚のカード(0 と1)のどちらかであるかを,左右一方のコインの裏表で伝えれば良い。例えば「右のコインが表なら0,裏なら1」と決めておくとしよう。赤のビショップは 投げたコインを見て,右が取り決め通りに出ていれば,左のコインを裏返し,そうでなければ右のコインを裏返す。白のビショップは,右のコインだけを見て, 決めた通りに答えれば良い。これを2n枚 の場合に一般化するのは,難問かもしれない。読者諸氏は,数の2進表記についてはご存知だろう。では,その排他的論理和についてはどうだろうか。念のため,簡単に説明すると,排他的論理和とは2進表記された2つの数を桁ごとに0+0=1+1=0 そして1+0=0+1=1という規則で加え合わせることで ある。

通常の和と違うのは1+1が0になることだ。ここでは,aとbの排他的論理和をa⊕bと書く。例えば12と10は,2進表記では1100と1010で,その排他的論理和は0110となるが,これは10進では6だから,このことを12⊕0=6と記す。

排他的論理和では,結合法則と交換法則が成り立つ。つまり,(a⊕b)⊕c=a⊕(b⊕c),a⊕b=b⊕a となり,a⊕0=0⊕a=aやa⊕a=0などの性質があるので,数学や計算機科学によく登場する。さて,赤から白のビショップへの通信の仕組みを作るのにこの演算を利用しよう。まず,並べたコインに左から0,1,2,…と順に番号を振る。投げたとき裏になったコインの番号をa,b, …,hとし,観客が引いたカードの数をkとすると,赤のビショップはa⊕b⊕…⊕h⊕k=mを計算し,番号mのコインを裏返す。一方,白のビショップは,その結果を見て,そのとき裏になっている コインの番号の排他的論理和を計算すれば良い。上に述べた排他的論理和の性質から,その結果の数値は,カードの番号kと一致するという寸法である。

たとえば,カードの番号kは8で,裏になったコインは0,3,7,9,12番の5枚だったとしよう。赤のビショップは,0⊕3⊕7⊕9⊕12⊕8=mの計算を行う。

8は2進で1000,またコイン番号は0000,0011,0111,1001,1100だから,その結果は,2進で1001,すなわちm=9である。そこで,9番のコインをひっくり返して表にする。

白のビショプが舞台に登場したとき,裏になっているのは0,3,7,12番の4枚で,白は0⊕3⊕7⊕12=8の計算をして,カードが8だとわかる。

カードが7で,コインの状況が同じだとしたら,0⊕3⊕7⊕9⊕12⊕7=6だから,赤は,9番ではなく,6番のコインをひっくり返して,裏にする。白は,0⊕3⊕6⊕7⊕9⊕12=7という計算により,カードの数が7だとわかる。

一般の場合について触れておく。少し考えればわかるが,コインの枚数pが2n以下でカードの枚数も2n以下なら,上の計算の結果mは2n未満になる。しかしm<pでないと,裏返すべき番号のコインがなくなるので,そういうことが起こらないようにコインの枚数は2nである必要がある。

余計な薀蓄を付け加えると,上の答えは,2009年11月号2010年11月号の解答で述べた「2進ハミング符号」と密接な関係がある。白のビショップがkを計算する際,番号0のコインは,表でも裏でも結果に影響を与えないことに,読者は気づかれただろう。

そこで,それを除いた15枚のコインの列を考える。このときk=0を与える15枚のコインの列(すなわち裏になっているコイン番号の排他的論理和が0になるような列)を集めると長さ15の2進ハミング符号となる。長さ7や3,一般には長さ2n-1の2進ハミング符号も同様に構成できる。

 

参考にした本:Peter Winkler による次の2冊(ともに出版元はA K Peters, Ltd. )Mathematical Puzzles: A Connoisseur’s Collection (2004)Mathematical Mind-Benders (2007)ルイス・キャロルによる『不思議の国のアリス』『鏡の国のアリス』(さまざまな出版社から,さまざまな訳者による翻訳本や注釈本が出ている)

 

 

問題に戻る

問題はこちらです