パズルの国のアリス

死刑囚の生き残り戦略(解答)

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

解答例エースが授けた戦略は,例えば「まず最初に左から数えて自分の番号になる箱を開けろ」というもの(エースは1とする)。もしそれが外れであれば,次はその箱に入っていた免罪符の番号の箱を開ける。それも外れであれば,さらに次にはその箱に入っていた番号の箱を開ける。

戦略のツボは,どういう方法でもいいから4つの箱と4人の死刑囚との対応を定めること。そうすると,その関係は,数学用語で「置換」と呼ぶものと同じになる。置換とは要は物の並び替えのことで,例えば,1234を並べ替えて4213や2413にすることをいう。

自分の箱からスタートして,上の戦略のように次々に進めて,自分の免罪符にぶつかるまで引き続ける場合を考えてみよう。例えば免罪符の配置が2413の ようになっていると,エースが箱を開けるときは2→4→3→1の順となり,自分の免罪符を引き当てるのは最後となる。この配置では,他の3人の箱の開け方も順繰りにずれて,自分の免罪符を引くのはやはり最後になる。このような置換を「長さ4の巡回置換」といい,エースの戦略では,全員が自分の免罪符に巡り合うまえに制限回数の3を超えてしまう。

逆に,例えば4213のように,長さ4の巡回置換以外の場合,全員が3回以内に自分の免罪符を引くことになる。

4要素の置換は全部で4! =24通りあるが,自分の免罪符に巡り合うのが最後になる長さ4の巡回置換は3! =6通りしかないので,処刑される確率は6/24,つまりわずか1/4だ。

一般に囚人がn人いてn-1個の箱を開ける場合,一人ひとりが自分の免罪符を引き当てられる確率は(1-1/n)なので,何の戦略もなしに箱を開ければ全員が引き当てられる確率は(1-1/n)のn乗となる。その値はnが大きくなるにつれて増加するが,極限はよく知られているように1/eだ(eは自然対数の底で約2.7182)。つまり,約0.368に近づくが,それ以上には大きくならない。半分よりもかなり大きな確率で全員が処刑されてしまうことになる。

一方,上に挙げた戦略を使うと,最初の一人がどこかで免罪符を引ければ,必ず全員が免罪符を引ける。その確率は1-1/nだ。従って,nが大きくなればなるほど免罪される確率はいくらでも1に近づく。

この戦略が秀でているのは,開けることのできる箱の数がn-1でなくても有効なことである。女王が開ける箱を3つに増やすことを認めなかったとしても, 免罪確率は5/12と,1/2よりもわずかに下がるだけで,何の戦略もない場合の1/16に比べ格段に良い。

一般にn個の箱のうちのk個を開けていい場合,kがnの半分以上なら,簡単な組み合わせ論的考察で,処刑される確率は

1/(k+1)+1/(k+2)+…+1/nになることがわかる。n=2k,すなわちちょうど半分の箱を開けていい場合,この和はkが大きくなるとlog2すなわち0.693に近づくことが知られている。つまりnが大きくなっても,言い換えれば囚人の数が増えても,免罪確率が0.3以下になることはない。何の戦略もない場合の絶望的な確率(1/2) のn乗と比較してみられたい。

 

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

 

 

問題はこちらです