文献あり

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

1730

初めに

"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個のロッカーを開ける。

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

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

Pointer following (p.f.)

$i$ 番目の人は最初に $i$ のロッカーを開ける。次に開けるロッカーは $σ (i)$ 、次は $σ (σ (i))$ を開ける。これを続ける。つまり $j$ 回目（最初にロッカーを開けるのを0回目とする）には
$\begin{array}{r} σ^{j} (i) = {\begin{cases} i (j = 0), \\ \overset{j コ}{\overset{⏞}{σ (σ (\dots (σ}} (i))) \dots) (j \geq 1) \end{cases} \end{array}$
を開ける。

成功率30%以上の証明

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

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

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

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

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

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

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

P

に長さ

k (k > N)

のループが存在する確率

$\begin{array}{r} P r (k) = \frac{1}{k} (k > N) \end{array}$

である。

P r (k) = 1 / k (k > N)

の証明

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

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

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

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

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

ゲームに成功する確率

$\begin{aligned} 1 - (P r (51) + P r (52) + \dots + P r (100)) & = 1 - (1 / 51 + 1 / 52 + \dots + 1 / 100) \\ ≃ 1 - 0.68817 \\ ≃ 0.3118 \end{aligned}$

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

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

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

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

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

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

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