帽子のパズル その２

この話のネタ元は、四年前のNYTimesの記事。この問題は、もともとはあるComputerScienceの大学院生が1998年に書いた博士論文に載っていたものらしい。どうやら最初のバージョンは3人のものだったようだが、7人の場合を自分の生徒にやらせようとして,初めてこの問題が一筋縄では行かないことが明るみにでたということだ。

気がついたらこの問題はニュースグループに投稿されており、そして瞬く間にComputerScientists、数学者、統計学者などの間に広まった。さらに間もないうちに明らかになったのは、この問題の解法が暗号理論や通信理論と深いところでつながっていたということである。専門外なので詳しくは知らないが、通信理論の基本的なツールであるHamming Codeがちょうどこの問題の解にきれいに対応しているということだ。Hamming Codeに基づいた戦略に従うと、囚人の人数nが増えるにしたがって、彼らの生存確率は１に収束していく。ただし、これが最適解であると確認されているのは（このあたりNYTimesの記事は曖昧なので、僕の解釈が入ってます）、ｎ=２＾ｍ−１のときのみである。記事によると、そうでない場合の最適解は、9人以上の場合については未だに知られていないという。実際バークレーの数学者Hendrik LenstraとHP研究所のGadiel Seroussiは、ｎが大きい場合にHamming Codeよりも効率的な戦略を見つけたらしい。

しかし、n=3の場合はなんとか飛び道具なしで解くことができるのだ。解答を知りたい方は、「続きを読む」をクリック。

(解答）

まず、次のような戦略をとれば、3/4の確率で全員助かる。

自分のほかの囚人達の帽子の色が違えば黙っている。
自分のほかの囚人達の帽子の色が同じなら、それではない色を答える

この戦略に従うと、（赤、赤、赤）あるいは（青、青、青）の時は全員間違えるが、それ以外のときは助かる（二人がパスし、残りの一人が自分の帽子の色を当てる）。

次にこれが最適な理由は、以下のとおり助かる確率が3/4以上にならないことによる。（オリジナルに作った答えなので、最もエレガントな解ではないかも）

囚人をA,B,Cと呼び、それぞれが正しく答える確率をa,b,c,とする。一般性を失うことなく、aが一番大きいと仮定しよう。

（１）全員が助かる確率＜＝誰かが正解する確率＜＝a+b+c<=3a
（２）すでにコメントで指摘されているとおり、それぞれの囚人が正解する確率と間違える確率は等しい。よって囚人Aは確率aで間違えるので、全員が助かる確率は1-aより小さい。

まとめると、全員が助かる確率はmin｛3a,1-a｝より小さいが、これはaの値に関わらず3/4より小さい(aが1/4の時に3/4。）　　Q.E.D.

ちなみに、この議論はn人の場合にも簡単に拡張できて、その場合は助かる確率の上限はn/n+1になる。実はｎ=２＾ｍ−１の場合にはHamming Codeでこの確率が達成できる（らしい）ので、Hamming Codeの最適性も確認できる。