[パズル] 99人の囚人

「99人の囚人」という論理パズルについて、問題と解答を書きます。

この問題は、職場の先輩のブログ: にゃんたこす!徒然草。99人の囚人 問題編(数学パズル)という記事に載っていたものです。面白い問題と思ったので、自分のブログにも転載させて頂きます。解答は私が書いたのですが、結構ややこしいものになってしまいました。エレガントな解答を思いついた方がいらっしゃいましたら、ぜひコメントにて指摘頂ければと思います。


ではまず問題から。(前述のブログから引用)

問題

99人の囚人がいます。彼らの頭に1~100までのナンバーカードが貼りつけられた帽子をランダムにかぶせます。
他人の帽子は見ることができても、自分の帽子は見ることができません。
帽子の数は全部で100なので、一つ使われずに余ります。
そのナンバーは囚人達にはわからないようにしておきます。
この状況で、囚人たちに一斉に自分のナンバーを宣言させて、全員が正解だったら釈放するという賭けをします。
囚人たちには帽子をかぶせられる前に相談タイムが設けられています。
どういう戦略を取れば、助かる確率を最も高くできるでしょうか?

以下では、ヒントと答えを書きます。


ヒント

各囚人は、自分以外の98人の囚人のナンバーカードを見ることができます。ナンバーカードは全部で100個あるため、自分のナンバーは2通りある (すなわち、1〜100の数のうち、他の囚人98人が被っている98個の数 以外の2つの数) ことが分かります。その2通りの数のうち、1つは自分のナンバー、もうひとつは、使われなかったナンバーということになります。下の表では、各囚人にとってどの番号を見ることができるかを示します (未使用の番号を61としています)。

囚人1
の番号
囚人2
の番号
...囚人i-1
の番号
囚人i囚人i+1
の番号
...囚人99
の番号
未使用
の番号
見えない
囚人1にとって38...205914...796と61
囚人2にとって96...205914...738と61
:::...:::...:::
囚人iにとって9638...2014...759と61
:::...:::...::
:
囚人99にとって9638...205914...7と61


ヒントの1つめ
「見えない2つの数を元に必ず自分の番号を当てる方法」は存在し得ません。なぜなら、ある囚人にとって、「他の囚人が被っている帽子の番号の情報(98個の整数)」のみでは、2つの可能性を1つに絞ることができないからです。(※1)。
そこで、答えは、「あらかじめ2つの可能性を1つに絞るためのルールを決めておく」、より正確には「相談タイムにて『各囚人があるルールに基づいて2つの数のうちの一方を宣言する』と取り決め、各囚人はその通りに宣言する」となります。

ちなみに、各囚人が「見えない2つ数のうちの1つを適当に宣言する」とすれば、全員が釈放される可能性はほぼゼロ (1/2の100乗≒宝くじで1等を5連続で当てる確率) となります。

ヒントの2つめ
次の性質を持つルールが存在します: そのルールに基づいて各囚人が宣言した場合、1/2の確率で「全員が正しい数を宣言する」が、1/2の確率で「全員が間違った数を宣言する」。

※1 もし問題に条件を追加して、「他の人が被っている帽子を見た後、何らかの意思疎通を行って良い」とか、「宣言する際には一斉に行う必要はない」とかとするならば、100%の確率で脱出できる答えが出てきます。


答え

答えは「相談タイムにて『(囚人1の番号, 囚人2の番号, ..., 囚人99の番号, 未使用の番号) という順列が偶順列(※2)である』と山を掛ける。各囚人は、他の囚人の番号を見て、前述の順列が偶順列となるように自分の番号を決め、それを宣言する」です。
このようにすると、50%の確率で全員が解放されます。もし、山が当たった場合(すなわち前述の順列が偶順列であった場合)、全ての囚人は自分の番号を正しく定めることができるため、開放されます。一方、不幸にも前述の順列が奇順列であった場合は、全ての囚人が自分の番号を誤ります。

各囚人は、必ず一意に自分の番号を決めることができます。自分の番号となる数は2つあり、そのうち1つを選ぶと前述の順列が偶順列となり、もう1つを選ぶと奇順列となります。理由は、任意の2要素に対して、それらを交換した順列は奇偶が逆になる(※3)ためです。

# 順列の偶奇を使わずに解く方法を考えてみたのですが、思いつきませんでした。もし思いついた方がいらっしゃいましたらぜひ教えて下さい。


注:
  • ※2 異なる整数からなる順列 (a1, ..., ai, ...)があるとき、「その順列に対する転倒数」を、「ijかつ aiaj である組(i, j)の個数」と定めます。転倒数が偶数である順列を偶順列、奇数である順列を奇順列と定めます。
  • ※3 順列 (..., ai, ..., aj, ...) と、2要素 aiaj を入れ替えた順列 (..., aj, ..., ai, ...) の偶奇が逆になる理由について説明します。まず、順列の i<・<j 番目の部分で、aiよりも小さい要素の個数をm個、ajよりも大きい要素の個数をn個とします。すると、入れ替えることによって、以下の理由から、順列の転倒数の偶奇は反転します。
    • aiの位置がi番目からj番目に移ることにより、転倒数はm減り、(ji−1)−m増えます。
    • ajの位置がj番目からi番目に移ることにより、転倒数はn減り、(ji−1)−n増えます。
    • aiajについて、もしaiajならば転倒数は1増え、aiajならば転倒数は1減ります。
    • 上の3点を合わせると、転倒数は −m(ji−1)−mn(ji−1)−n±1=2(−mnji−1)±1 だけ増えることとなり、転倒数の偶奇が反転します。

コメント 13つ:

にゃんたこす さんのコメント...

おお、こんな素敵なブログを運営されていたとは!

ちなみにこの問題は、稲葉直貴さんというパズル作家さん?の作品のようです・・・
http://inabapuzzle.com/hirameki/suuri_6.html

Mah さんのコメント...

にゃんたこすさん、
コメントありがとうございます。そして、問題の紹介ありがとうございました。

ご紹介のHPを見ました。確かに同じ問題ですね。本も執筆されているようですので、今度読んでみようと思います。

匿名 さんのコメント...

お恥ずかしながら数学には疎いもんで答の意味が解らなかったんですがwそんな難しい事しなくても皆正解できますよ?
例えば№50が余りとします、皆自分の番号と余りの2択になるんですから、その2択の番号が隣接する人を決められた位置に集合させます。
次に№49、№51が集合し№49が№51を見て自分が低い数字だと解ります。
最後に№49→№51と並べば余りは№50だと皆解ります。
まートンチですけどねw

匿名 さんのコメント...

いやしゃべったり合図しちゃだめでしょw

匿名 さんのコメント...

仮に
囚人1が帽子1,囚人2が帽子2,囚人3が帽子3,・・・,囚人98が帽子98を被っていたとします。
このとき、囚人99は帽子99,帽子100のどちらかの選択肢があるわけですが、帽子99,帽子100どちらをえらんでも遇順列となり、囚人99はルールに従おうにも答えを絞りきれず適当に選択せざるを得ないと思います。こういった立場に陥る囚人は例の場合だけでなく他の場合においても一人は登場するのではと思います。
したがって、この方法の生存確率は25%ではないでしょうか?

匿名 さんのコメント...

筆者の問題中には書かれていないですが、
ヒント二つ目の※1に
「他の人が被っている帽子を見た後、何らかの意思疎通を行って良い」という条件がないことを暗に示しています。
したがって、匿名さん2014.11/4の方法は決められた位置に集合させるという点で、これに反すると考えられます。

匿名 さんのコメント...

存在しない番号を囚人100とした100個の順列と考えているので、偶奇は一意に定まるのでは?

匿名 さんのコメント...

↓これが答えだと思ったら違うのか・・・。
 帽子をかぶった後は皆意思疎通をせず、あらかじめ相談タイム時に決めておいた通りに動くだけ。
 各々が自分の判断で答えを出すので、悪くないと思うんだがなあ。
 まあ時間は必要になるけど。


1)まず、100人が各々で自分以外の全員の帽子ナンバーを
  確認し、自分の帽子のナンバーを2つに絞りこむ
  (例えば5の帽子の人は自分のナンバーを「5か61と認識」)

2)地面に10×10=100大きなマス目を書き、
  1~100の数字を書く
  マス目ひとつは人間が一人立てるくらい

3)100人が1列に整列し、一番最初の人から順番に
  自分の帽子ナンバーの可能性のあると思っているマス目に移動する

  例えば何番目かの5の帽子の人は「5」が「61」のマス目のどちらかを好きに選んで移動する。
  ここで、仮に5の帽子の人が「61」のマス目に入ったとすると、次の人以降は
  「5」の帽子の人が「61」の場所に立っているのを見ることになる。
  この時点で、「5」帽子の人の後ろに並んでいた人は全員まっすぐに自分の帽子番号の
  マス目に移動することが可能となる。


4)全員がマス目に移動を完了すると、1~100のマス目の内、
  「5」のマス目だけが空いた状態となる。
  ここで、それを確認した「5」の帽子の人は「61」のマス目から「5」のマス目に移動する。
  なぜなら、自分の帽子の番号が「61」よりも「5」である確率が圧倒的に高いから。
  (※他人のマス目移動時の挙動を観察してではなく、
    あくまで空いたマス目番号から判断している点が肝)

5)それぞれが自分の立っているマス目の数字を、自分の帽子の番号として宣言する
  →ほぼ100%に近い確率で全員助かる。



匿名 さんのコメント...

前の方とほぼ同じですが、
1)地面に1~100の番号を書きます。
2)一人ずつ順番に、2択の内の好きな方の位置に並んでいきます。
3)そのうち、正しくない位置に並ぶ人がでます。
4)その正しくない位置が欠番です。
5)それをみた次の人は、手を上げて、前の人が間違えたことを教えます。
6)間違えた人は、正しい位置に並び直し、残りの人は2択のうちの欠番でない方に並びます。
7)もし、最後の人まで間違えた人が出なければ、最後に残ったのが欠番です。
8)全員並び終えたら、一斉に自分の並んでいる位置の番号を宣言します。
これで100%ではないでしょうか。
地面に番号を書いたり、並んだり、手を上げたりしたらだめなんですか?

匿名 さんのコメント...

番号を割り当てられた後にとれる行動は他人の番号を確認することと自分の番号を宣言することの2つだけじゃね?
自由に行動していいのは番号を割り当てられる前の相談するときだけ。
問題の条件として番号を割り当てられた時は他人の番号は確認できるとしか書いてない。
つまりそれ以外の行動は全て禁止と考えるのが妥当。

匿名 さんのコメント...

> 2016年1月30日 18:56 さん

そうですね。
そもそも、意思疎通の権利があるなら自分の番号を周りに教えてもらえばいい話。

匿名 さんのコメント...

書いてないならダメっていう人いるけど、書いてないからいいんじゃね?w
それに、他の囚人確認できるって言うけどどーやってするん?部屋に閉じ込められてても動かないと無理wそれとも、ランダムに並ぶ数字からある程度の時間であまりの数字2つだせるわけw(それとも、確認する時間は無制限で?)
強引かもしれないが、抜け穴探す方法もありでは?
(偏見かもしれんが、理系の方は納得出来なさそうw周りに言ったら納得出来なさそうでしたw逆に文系の方は出来そう、偏見です、すまそ)

匿名 さんのコメント...

>>2016年10月19日 0:55

理論パズルなんだから問題外ってか見当違い過ぎて草