こんにちは、ヘルスケア事業部のちょうです。前回のクイズ問題はいかがでしょうか。
実はその問題、続きがあります。（前回の問題分からなくてもオーケーです。条件はまったく新しくなりますので）
「The Art of Multiprocessor Programming」第一章 問題5
The same warden has a different idea. He orders the prisoners to stand in line, and places red and blue hats on each of their heads. No prisoner knows the color of his own hat, or the color of any hat behind him, but he can see the hats of the prisoners in front. The warden starts at the back of the line and asks each prisoner to guess the color of his own hat. The prisoner can answer only “red” or “blue.” If he gives the wrong answer, he is fed to the crocodiles. If he answers correctly, he is freed. Each prisoner can hear the answer of the prisoners behind him, but cannot tell whether that prisoner was correct.
The prisoners are allowed to consult and agree on a strategy beforehand (while the warden listens in) but after being lined up, they cannot communicate any other way besides their answer of “red” or “blue.” Devise a strategy that allows at least P − 1 of P prisoners to be freed.
あの刑務所長また別の考えがあります。囚人たちを一列に並んで、一人一人に赤い帽子か青い帽子を被らせます。囚人たち誰一人も自分の帽子の色と自分の後ろに立つ人たちの帽子の色を知りません。しかし前に立つ人たちの帽子の色を見えます。刑務所長が列の最後尾から、囚人たち一人一人に自分の帽子の色を聞きます。囚人は「赤い」と「青い」しか答えられません。もし間違ったら、ワニに食べられます。正解でしたら、自由になります。囚人みんな後ろにいる人の答えを聞こえますが、その答えが正しいかどうかは分かりません。
囚人たちは列に並ぶまえに、予め話し合って一つの対応策を決めることが可能です（もちろん刑務所長は盗み聞きができますが）。列に入ったらお互いに「赤い」と「青い」の答え以外に話すことができません。
P人の囚人たちにすくなくともP - 1人が自由になる方法を考えてください。
P人のうちP - 1人が自由になれるのは、最大一人しか間違った色を答えないということです。直感で、この犠牲者は列の最後尾にいる囚人です。なぜなら、最後尾にいる人、自分の帽子のいろを見えないし、他にヒントになれるものがなにもないわけです。それに比べて、後ろから二番目の囚人は最後尾にいる人の答えがヒントになります。
P = 3の場合を考えましょう。
A B C(最後尾)
条件によって、Cが最後尾で、BとAの帽子のいろが見えます。同じく、BがAの帽子のいろを見えます。
ここで、もしCがBの帽子のいろを答えにして、BはAの帽子のいろを答えにすると、どうなりますか。一見BとAが正解を答えるかもしれないが、実際は不可能です。なぜというと、BがAの帽子のいろを答えにし、その答えが自分の帽子のいろではない可能性があります。つまり、一回の答えで、後ろにいる囚人から知っていた自分の帽子のいろと前にいる囚人の帽子のいろを同時に答えにすることができません。
ではどうすればいいでしょうか。
ヒントは「しかし前に立つ人たちの帽子の色を見えます」にあります。もし囚人たちはまえの人の帽子のいろを答えにするのではなく、自分のまえにいるすべての人のあるいろの帽子を数えると、どうなりますか。例えば、赤い帽子を数えるのを約束しましょう。
囚人Pが見えた赤い帽子の数をH(P)としよう。うえの例にいるCが見えたのはH(C)、Bが見えたのはH(B)、Aが見えたのはH(A)になります。ここで
- H(A) = 0
- H(B) = Aの帽子が赤いなら1、それ以外0
- H(C) = H(B) + Bの帽子が赤いなら1、それ以外0
そしてすこし変換しよう。
H(C) - H(B) = Bの帽子が赤いなら1、それ以外0
何が分かりになりましたか。囚人Bが見えた赤い帽子の数がH(B)、後ろにいるCがH(C)をBが理解できるある形にすれば、Bの帽子のいろが推測できます。
もう一つ
H(C) = Aの帽子が赤いなら1、それ以外0 + Bの帽子が赤いなら1、それ以外0
当たり前ですが、これはもうひとつ隠した推測方法です。AはBからH(B)を聞くではなく、CからH(C)を聞き、BからBの帽子のいろから、自分の帽子の色を推測できるということです。これはH(B)を依頼しない重要なポイントです。
つまり、三人の場合は、AとBはまずCからH(C)を聞き、別々の方法で自分の帽子のいろを推測します。
もし四人になる場合、
A B C D(最後尾）
- H(D) = H(C) + Cの帽子が赤いなら1、それ以外0
- H(C) = H(B) + Bの帽子が赤いなら1、それ以外0
- H(B) = Aの帽子が赤いなら1、それ以外0
- H(A) = 0
変換すると
Cに対して
- H(D) - H(C) = Cの帽子が赤いなら1、それ以外0
Bに対して、
- H(D) - H(C) = Cの帽子が赤いなら1、それ以外0
- H(D) - (H(B) + Bの帽子が赤いなら1、それ以外0) = Cの帽子が赤いなら1、それ以外0
- H(D) - H(B) - Bの帽子が赤いなら1、それ以外0 = Cの帽子が赤いなら1、それ以外0
- H(D) - H(B) - Cの帽子が赤いなら1、それ以外0 = Bの帽子が赤いなら1、それ以外0
Aに対して
- H(D) - Cの帽子が赤いなら1、それ以外0 - Bの帽子が赤いなら1、それ以外0 = Aの帽子が赤いなら1、それ以外0
では、最後のパズルはH(D)をどうやって伝えるかです。囚人は赤いと青いだけ答えるので、一番簡単な方法は奇数でしたら赤い、偶数でしたら青いを答えます。それでも推測できますか。
四人の場合を考えましょう。
A(赤い）B(青い）C(赤い）D(赤い）
犠牲者DはH(D)を伝えようとする、2なので、青いと答えます。 Cが青い（偶数）と聞いて、自分の前にある赤い帽子の数が1（奇数）を知り、奇数＋自分の帽子＝Dの偶数、自分の帽子のいろは赤いと答えます。 BがD（青い、偶数）とC（赤い）の答えを聞いて、自分の前にある赤い帽子の数は１（奇数）を知り、奇数＋自分の帽子＋Cの赤い＝Dの偶数、自分の帽子のいろは青いと答えます。 最後にAがD、C、Bの答えを聞いて、自分の帽子＋Bの青い＋Cの赤い＝Dの偶数、自分の帽子のいろが赤いと答えます。
これで問題解決できです。
まとめてみれば
- みんな前にある赤い帽子を数える
- 最後にいる人は、数字が奇数の場合赤い、偶数の場合青いと答える（50%の可能性でワニに食べられます）
- ほかの人は数えた結果と後ろにいる人たち（最後尾のひと除く）の帽子のいろを聞いて、自分の帽子のいろを推測する
いかがでしょうか。簡単そうな問題に見えますが、実際結構トリックな方法を使わないと解決できなそうでしたね。たまには、こういう問題を解いてみて、自分の考えを広げてみませんか。
