[パズル] 99人の囚人

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

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

---

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

問題

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

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

---

ヒント

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

	囚人1 の番号	囚人2 の番号	...	囚人i-1 の番号	囚人i	囚人i+1 の番号	...	囚人99 の番号	未使用 の番号		見えない 数
囚人1にとって	？	38	...	20	59	14	...	7	？		96と61
囚人2にとって	96	？	...	20	59	14	...	7	？		38と61
:	:	:	...	:	:	:	...	:	:		:
囚人iにとって	96	38	...	20	？	14	...	7	？		59と61
:	:	:	...	:	:	:	...	:	:		:
囚人99にとって	96	38	...	20	59	14	...	？	？		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 異なる整数からなる順列 (a₁, ..., a_i, ...)があるとき、「その順列に対する転倒数」を、「i＜jかつ a_i＞a_j である組(i, j)の個数」と定めます。転倒数が偶数である順列を偶順列、奇数である順列を奇順列と定めます。
• ※3 順列 (..., a_i, ..., a_j, ...) と、2要素 a_i, a_j を入れ替えた順列 (..., a_j, ..., a_i, ...) の偶奇が逆になる理由について説明します。まず、順列の i＜・＜j 番目の部分で、a_iよりも小さい要素の個数をm個、a_jよりも大きい要素の個数をn個とします。すると、入れ替えることによって、以下の理由から、順列の転倒数の偶奇は反転します。
  
  • a_iの位置がi番目からj番目に移ることにより、転倒数はm減り、(j−i−1)−m増えます。
  • a_jの位置がj番目からi番目に移ることにより、転倒数はn減り、(j−i−1)−n増えます。
  • a_iとa_jについて、もしa_i＜a_jならば転倒数は1増え、a_i＞a_jならば転倒数は1減ります。
  • 上の3点を合わせると、転倒数は −m＋(j−i−1)−m−n＋(j−i−1)−n±1＝2(−m−n＋j−i−1)±1 だけ増えることとなり、転倒数の偶奇が反転します。