パズルの国のアリス

女王陛下,ご自身の冠の色は?(解答)

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

 

解答例アリスの戦略は,例えば「他の2人の冠の色が同じなら,その反対の色を答える。2人の色が赤と白なら『わからない』と答える」というもの。この戦略では, 全員の色が同じであれば,全員が間違いを答えて負けになる。しかし,それ以外は,他の2人と違う色の冠をかぶっている者は正解を答え,他のものは「わからない」と答えるので勝ちになる。3人が赤白どちらかになるから,2の3乗で8通り。このうち,3人とも同じ色になるのは2通りしかなく,残りの6通りはす べて1対2で色が分かれる。なので,アリスの戦略だと勝率は3/4になる。

さて,7人いる場合に,この戦略を拡張することを考えよう。7人の冠の色がそれぞれ白か赤のどちらかであるということは,便宜上,白を0,赤を1とすれ ば,すべてのパターンを0000000(全員が白),1000000(最初の1人だけが赤)などと,7ビット2進数として表すことができる。実はアリスの戦略は,デジタルデータにエラーが生じた際に,それを検出し訂正するときに使う「誤り訂正符号」をヒントにしている。ここでは特に「ハミング符号」を利用してみよう。

7ビット2進数のパターンは2の7乗だから128個あるが,そのうち次の16個の集合Cをハミング符号という。

0000000 00010110010110 00111010101100 01001110111010 01100011011000 10100111001110 10001011110100 11111111100010 1101001

ハミング符号Cの特徴は,どんな7ビットの2進数を与えられても,違いが1ビット以内のものが必ず1つだけCの中にあるということだ。例えば, 1101010はCにある最後から2番目の1100010と1ビット違いである。また,0101010は7番目の0111010と1ビット違いだ。このような符号(2進数の集合)を完全符号という。

完全符号を,冠の色当て問題に応用してみよう。まず,各人が自分の色を赤(1)と仮定して,Cの16個のどれかと一致するかを考えてみる。次に白(0)と仮定して一致を調べる。どちらを仮定しても一致するものがCの中になければ「わからない」と答える。一致するものがあれば,自分の冠は「その反対の色だ」と答える。例えば,自分の色を白と仮定したときに,冠が表す2進数がCの中にあれば「赤」と答えるのだ。

この戦略のポイントは,7ビットの2進数は128種類あるのに対し,Cの要素数は16しかないという点にある。

まず,上に述べた完全符号の性質から,どんな2進数もCのどれかと1ビットしか違わないので,全員が「わからない」と答えて負けることはない。

次に間違える可能性を検討してみよう。かぶせられた冠のパターンがCの要素のどれかと完全に一致していたら, 明らかに全員が間違いを答えて負けとなる。残り128-16=112種類の2進数はC内の2進数のどれかと1ビット違いとなる。このときは,その違うビットに対応する人は自分の冠の色を正しく言い当て,他は全員「わからない」と答えるので勝ちになる。したがって,冠のかぶせ方がランダムならば勝率は 112/128=7/8となる。

一般に,k人に冠をかぶせるときに,符号に基づく上のような戦略を用いる場合,Cの要素数をc0,Cの要素との違いが1ビット以内の2進数の数をc1とすると,勝率は(c1-c0)/2kとなる。従って,c0が小さく,c1が大きいCを使うのが得策となる。ハミング符号はc0が比較的小さいのにc1は最大の2kに達するところに特徴がある。例えば長さk=2m-1のハミング符号も存在するが,その場合,c0=2k-mだから,勝率は1-(1/2)mとなる。

一部の人に「わからない」と言わせることにすれば,少人数の戦略はそのまま多人数の場合にも使えるから,kが大きくなることは,少しも不利にならない。よって,最適戦略による勝率はkに対して単調増加であり,1に収束するといえる。

 

 

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

 

 

問題に戻る

 

 

 

問題はこちらです