文献あり

100人の囚人問題: 最善の戦略は？その1

1561

初めに

"100人の囚人問題"とか"100人の囚人と50個の箱"と呼ばれる数学のパズルがある。英語では"100 prisoners problem"、"The locker puzzle"、"100 lockers puzzle"などと言わるようである。大変有名な問題なので、web上探せばいくつも解説ページが出てくる。

これはある課題を達成するための良い戦略を考える問題である。後述するように、直観では不可能にも思える課題であるにも関わらず、驚くべき戦略が存在する。

一連の記事で、解答として一般に提示される戦略が、単に良いだけではなく最善であることに関してコメントする。その証明はRef.[1]に書かれている。数学的な証明というよりは解説文的な感じなので、大変平易に書いてある。が、それでも、自分にはちょっとわかりにくいところがあった。また、英語のWikipediaに100 prisoners problemのページ(Ref.[4])があり、その記事のoptimality(最良性)の項目を読んだのだが、いまいち解説が的を射てないように思う。さらに日本語の解説ページも見つけられなかったので、ここに記しておくことにした。

一つの記事にまとめると長くなるので、前座である本記事と、最善の証明を解説した次の記事に分けた。本記事"その1"ではまず、問題の提示と、ある程度詳しい解答を書いておく。これは長ったらしいので（他のサイトと同じだと面白くないと思い...）、短いのがお好みな方は例えばRef.[2]を参照されたい。最善の証明に関しては次の記事"その2"で解説する。すでに問題と解答を知っている方は、"その2"から読んでいただければと思う。

問題と解答

100人の囚人問題は、通常100人の囚人と50個の箱が出てくるが、ここではRef.[1]にならい、ロッカーを使った形で書いておく。

問題

100人の囚人問題

ある部屋に100人集められている。別の部屋に100個のロッカーがあり、それぞれのロッカーには100人のうち1人の名前が書かれた紙が入れてある。違うロッカーには違う名前の紙が入っている。

順番を決め、1人がロッカーの部屋に入り、50個のロッカーを開ける。その中に自分の名前があれば、ロッカーを元の状態に戻し、次の人がロッカー部屋に入り、50個のロッカーを開ける。これを繰り返し、100人が皆自分の名前を見つけられたらゲームは成功。1人でも名前が見つけられなければゲームは失敗である。

100人はゲームを始める前に議論し戦略を決めることができる。ただしゲームが始まったらお互いに話すこと・情報を伝えることはできない。

このゲームにおいて、30%以上の確率で成功する戦略を考えよ。

皆ランダムにロッカーを開けるとしたら、成功する確率は$(1/2)^{100}$という絶望的な数字になる。

解答

この問題の解答として、"pointer following"(以下p.f.と称する)とか"pointer chasing"と呼ばれる以下の戦略が存在する：

Pointer following (p.f.)

人とロッカーに番号をふる。$i$番目の人はまず$i$番目のロッカーを開ける。その中に入っている人の名前に対応する番号のロッカーを次に開ける。これを繰り返し、50個のロッカーを開ける。

もう少し数学的にマシな言い方に変えると以下のようになる。

人とロッカーが$2N$人および$2N$個あるとする。人とロッカーに1から$2N$までの番号を振る。ロッカーの状態を$P$として、
\begin{align} P=(\sigma(1),\sigma(2),\cdots,\sigma(2N)) \end{align}
は$i(=1,\cdots,2N)$番目のロッカーに$\sigma(i)(=1,\cdots,2N, \ \sigma(i)\neq \sigma(j) \text{ for } i\neq j)$番目の人の名前が書かれている紙が入っている状態とする。
この時、p.f.は以下の戦略である：

Pointer following (p.f.)

$i$番目の人は最初に$i$のロッカーを開ける。次に開けるロッカーは$\sigma(i)$、次は$\sigma(\sigma(i))$を開ける。これを続ける。つまり$j$回目（最初にロッカーを開けるのを0回目とする）には
\begin{align} \sigma^{j}(i)= \begin{cases} i \ \ (j=0),\\ \overbrace{\sigma(\sigma(\cdots(\sigma}^{j\text{コ}}(i)))\cdots) \ \ (j\ge 1) \end{cases} \end{align}
を開ける。

成功率30%以上の証明

問題では50個のロッカーを開けるが、以下自分の名前を見つけるまでロッカーを開け続けることとし、開けたロッカーの個数が皆50個以下なら成功ということにしよう。これは元のゲームと等価である。

このゲームにおいて、以下が成り立つ：

$i$の人が自分の番号を見つけるまでにかかる回数を$N_i$とすると、$\sigma$は
\begin{align} \sigma^{N_i}(i)=i, \ N_i\ge 1 \end{align}
を満たす。
この時$\sigma^1(i), \sigma^2(i), \cdots, \sigma^{N_i-1}(i)$番目の人も$N_i$回で自分の番号を見つける

これは次のようにしてわかる：

$k=0,1,\cdots,N_i-1$に対し、$\sigma^k(i)$番目の人のめぐる番号の列を考える。$\sigma^j(i)$の定義より、$a,b\in \mathbb{N}$に対して
\begin{align} \sigma^{a}(\sigma^b(i))=\overbrace{\sigma(\sigma(\cdots(\sigma}^{(a+b)\text{コ}}(i)))\cdots)=\sigma^{a+b}(i) \end{align}
である。よって
\begin{align} \sigma^{N_i}(\sigma^k(i))=\sigma^{N_i+k}(i)=\sigma^{k}(\sigma^{N_i}(i))=\sigma^{k}(i) \ \ (\because \sigma^{N_i}(i)=i) \end{align}
であり、かつ$j< N_i$の時$\sigma^{j}(\sigma^k(i))$が$\sigma^k(i)$と等しくなることはないので（もし等しいものがあれば、このループの長さは$N_i$ではない）、 $N_{\sigma^k(i)}=N_i$であることがわかる。また、$\sigma^k(i)$番目の人がめぐる列は
\begin{align} \sigma^k(i)\rightarrow \sigma^{k+1}(i) \rightarrow \cdots \rightarrow\sigma^{N_i}(i)=i=\sigma^0(i) \rightarrow \sigma^{1}(i) \rightarrow \cdots \rightarrow \sigma^{k}(i) \end{align}
である。

$\sigma^1(i), \cdots, \sigma^{N_i-1}(i), \sigma^{N_i}(i)(=i)$の番号の人は、同じ番号の列を巡回する。この巡回列を「長さ$N_i$のループ」と呼ぶことにする。

以上の準備でp.f.における成功率を求めることができる。この確率は
ランダムに状態$P$を発生させるとき、$P$に50以下のループのみ存在する確率
である。
これを計算するため、ランダムな$P$に長さ$k \ (k>N)$のループが存在する確率を求める。これを$Pr(k)\ $とすると

$P$に長さ$k \ (k>N)$のループが存在する確率

\begin{align} Pr(k)=\frac{1}{k} \ \ \ (k>N) \end{align}

である。

$Pr(k)=1/k \ \ (k>N)$の証明

$k>N$の時、もし$P$に長さ$k$のループがあれば、それは1つだけである。$2N$個の番号から、$k$ループを作るための$k$個の番号を選び出す組み合わせは${}_{2N} C_k$である。選び出した$k$個の番号から$k$ループを作る通りの数を考える。$k$個の番号として$\{a_1,a_2,\ldots,a_k\}$（ただし$a_i\neq a_j$ for $i\neq j$）と選んだとき、この通りの数は
$$ \ \ \ \{\sigma(a_1),\sigma^2(a_1),\ldots,\sigma^k(a_1)\}が集合として\{a_1,a_2,\ldots,a_k\}と等しくなる写像の数 $$
である。ただし$\sigma^k(a_1)=a_1$。(記事末の(注)参照)

$\sigma(a_1)$は$a_1$以外の$k-1$通りの数が可能。$\sigma^2(a_1)$は$a_1,\sigma(a_1)$以外の数が可能なので$k-2$通り。これを繰り返せば、$\sigma$として可能な写像は$(k-1)!$通り存在することがわかる。
また、$a_1$から$a_k$以外の数字を並べる通りの数は$(2N-k)!$通り存在する。

以上から、長さ$k \ (k>N)$のループが存在する$P$の数は
\begin{align} {}_{2N} C_k\times (k-1)! \times (2N-k)! \end{align}
である。$P$は全部で$(2N)!$存在するので、ランダムに$P$を選んだ時、$k$ループが存在する確率$Pr(k) \ (k>N)$は
\begin{align} Pr(k)&={}_{2N} C_k\times (k-1)! \times (2N-k)!/(2N)!\\ &=(2N)!/k!/(2N-k)!\times(k-1)!\times(2N-k)!/(2N)!\\ &=\frac{1}{k} \end{align}
である。${}_\blacksquare$

ゲームの成功率は長さ51以上のループが存在する確率を1から引いたものなので、
\begin{align} 1-(Pr(51)+Pr(52)+\cdots +Pr(100)) \end{align}
と書ける。ここで、$k>N$ならば、長さ$k$のループと$l \ (l\ge k)$のループが同時に存在することはなく、それらは排反の事象であることを用いた。

以上より、このゲームに成功する確率は

ゲームに成功する確率

\begin{align} 1-(Pr(51)+Pr(52)+\cdots +Pr(100))&=1-(1/51+1/52+\cdots +1/100)\\ &\simeq 1-0.68817\\ &\simeq 0.3118 \end{align}

である。確かに成功率は30%を超えている。

ちなみに、
\begin{align} \sum_{k=N+1}^{2N}\frac{1}{k}=\sum_{k=1}^{2N}\frac{(-1)^{k+1}}{k} \end{align}
であり、かつこの右辺は$\log(1+x)$のマクローリン展開に$x=1$を入れたものであるから、$N\rightarrow \infty$におけるゲームの成功率は
\begin{align} 1-\log 2 \simeq 0.3069 \end{align}
である。すなわち、どんなに人とロッカーが増えても、成功率は3割を超えることがわかる。厳密には、上記のマクローリン展開の収束半径は1であり、$x=1$で数列が収束するかは別に議論する必要があるが、まあ直感的にはこれで十分であろう。

付記："その2"への導入

問題および解答の解説は以上である。私が最初にこの問題を知ったのは、togetterの"あなたは解けるか？面接合格をかけた超難問論理パズル"(Ref.[3])という記事による。最初の方にも書いた通り、みんながランダムにロッカーを開ければ成功率は$(1/2)^{100}$という絶望的な確率である。証明なしに解答を聞いても信じられず、証明を探しているうち、Ref.[2]のサイトで、Ref.[1]にp.f.が最善の戦略であることが証明してあることを知った。俄かにはどのように証明するかわからなかったので、興味を持って読んでみたところ、簡単で面白い証明方法であり、かつこの証明は日本語での解説が見つけられなかった（あったらすみません）。次の記事でこれについて私なりにコメントしたい。${}_\blacksquare$

100人の囚人問題: 最善の戦略は？その2

（注）「最初の値」を$a_1$以外にした$\{\sigma(a_i),\sigma^2(a_i),\ldots,\sigma^k(a_i)\}$という写像は考慮しなくてよいのか？と思うかもしれないが、これと同じループは$\{\sigma(a_1),\sigma^2(a_1),\ldots,\sigma^k(a_1)\}$の中に必ず含まれる。例えば$\sigma(a_2)$から始まる合成写像の列を考えるとしよう。$\sigma^l(a_2)=a_1$だとしたら、$\sigma(a_2)$から始まる列において$\sigma$を$\sigma^{l+1}$とすれば、$\{\sigma(a_2),\sigma^2(a_2),\ldots,\sigma^k(a_2)\}\rightarrow \{\sigma(a_1),\sigma^2(a_1),\ldots,\sigma^k(a_1)\}$となる。

具体的に$a_1=1,a_2=2,a_3=3$とする。
このとき$\sigma^i(a_1)$は
\begin{align} \ \ \ \sigma(1)=2, \sigma^2(1)=\sigma(2)=3 \ \ \ [1a],\\ \ \ \ \sigma(1)=3, \sigma^2(1)=\sigma(3)=2 \ \ \ [1b], \end{align}
の2通り存在。
一方$\sigma^i(a_2)$は
\begin{align} \ \ \ \sigma(2)=3, \sigma^2(2)=\sigma(3)=1 \ \ \ [2a],\\ \ \ \ \sigma(2)=1, \sigma^2(2)=\sigma(1)=3 \ \ \ [2b], \end{align}
の2通り存在。
しかし[1a]と[2a]はどちらも「1のロッカーに2, 2のロッカーに3、3のロッカーに1の番号が入っている」という、同じロッカーの状態に対応する。[2a]で$\sigma$を$\sigma^3$とすると、[1a]に帰着する。
[1b]と[2b]も「1のロッカーに3, 2のロッカーに1、3のロッカーに2の番号が入っている」という同じ状態。[2b]で$\sigma$を$\sigma^3$にすると、[1b]に帰着する。${}_\blacksquare$