９９人の囚人　解答

簡単のため囚人が３人で１〜４のゼッケンを使う場合について説明します。

まず、ゼッケンとは別に、囚人に１、２、３と囚人番号をふっておきます。
このとき４人目の囚人がいると仮定して、彼の囚人番号を４とします。

これで、準備は完了です。

その後、囚人達にゼッケンが割り当てられます。
あまったゼッケンは囚人番号４の囚人に割り当てられるとしましょう。

仮に、以下のようになったとします。
---------------------------------------
囚人番号：１　２　３　４
ゼッケン：３　４　２　１
---------------------------------------

囚人番号１の囚人の立場になって、この状況を見てみましょう。
---------------------------------------
囚人番号：１　２　３　４
ゼッケン：？　４　２　？
---------------------------------------

彼は、囚人番号２と３のゼッケンはわかりますが、
自分と囚人番号４のゼッケンが何かはわかりません。

ゼッケン番号の並びだけに着目すると、「？４２？」です。
「１４２３」なのか、「３４２１」なのか、これだけではわかりません。

そこで、あらかじめ次のような約束を全員の間で交わしておきます。
---------------------------------------------------------------------
【お約束】
偶数回だけ二人のゼッケンを取り替えることで、
ゼッケンの並びを「１２３４」にできる方を選ぶ。
---------------------------------------------------------------------

どういうことか。例えば候補の一つである「１４２３」は、
囚人番号２と３のゼッケンを入れ替えると
「１２４３」という並びになります。

ここでもう一度、囚人番号３と４の間でゼッケンを入れ替えると、
「１２３４」になります。

合計２回でゼッケンの並びを「１２３４」にできました。
では、もう一方の候補である「３４２１」はどうでしょうか。

「３４２１」→「１４２３」→「１２４３」→「１２３４」

と、合計３回の交換が必要です。

したがって、約束に従えば「偶数回」のゼッケン交換を行った
「１４２３」を選ぶべきだということになります。

あらかじめ、このような取り決めをしておけば、

『実際のゼッケンの並び』が
『偶数回だけ二人のゼッケンを取り替えることで、
ゼッケンの並びを「１２３４」にできる』

という性質を満たしていた場合に、全員が正解することができます。
そして、そのような確率は５０％であることが容易に確かめられます。
９９人で１００枚のゼッケンの場合も同様です。

おまけの問題（未解決）
・ゼッケンが２枚以上あまる場合はどうなるでしょう？