帽子の色

n人が協力する。彼らははじめに作戦を共有できる。作戦が決まったら東を向いて東西一列に並ぶ。ここで全員赤または白の帽子を等確率で被らされる。だが、東を向いているので、自分よりも東側にいる人の帽子の色しか分からない。

西側の人から順番に自分の帽子の色を当てていくときに適切な作戦を取れば、期待値で n-1/2 個の帽子の色が当てられることを示せ。

いつも楽しい問題ありがとうございます。

たとえば、一番後ろの人は、自分の前の赤い帽子の数が奇数のとき「赤」、偶数のとき「白」というと決めておく。次の人は、同様に自分の前の赤い帽子の数を数えて、奇数ならば、赤い帽子の数に変化がないわけだから、自分の帽子が白だと推論できる。偶数に変わっていれば、自分の帽子は赤だ。その次の人も同様に自分の前の赤い帽子の数を数えて、偶奇性に変化があれば「赤」、変化がなければ「白」といえばよい。

こうすると、一番後ろの人が自分の帽子の色を当てるのは運任せなので1/2だが、それ以外の人はぴたりとあてることができる。よって

があたる帽子の数の期待値になる。