日々の流転

λ. ω人の小人のパズル

小人のパズルを100人からω人にしたらどうなるかという話を、PPL2009の懇親会で聞いた。 すなわち、各小人の前に可算無限人の小人がいる場合。

ω人の小人が怪獣に捕まってしまいました。 小人たちが怪獣に命乞いをしたところ、条件を出されました。

怪獣が小人たちを縦に一列に並べ、それぞれの小人の頭に 赤か黄色か青のうちのどれか一色の帽子を被せます。 小人たちは自分より前に並んでいる小人の帽子の色はすべてわかりますが、 自分を含め、後ろに並んでいる小人の帽子の色は全くわかりません。 （各小人は、自分の前に並んでいるω人分の帽子の色がすべてわかる）

小人たちはひとりずつ赤か青か黄色の色を一回だけ答えることができ、 それが自分の帽子の色と同じだった場合は命が助かるというものです。 答える順番はどの小人からでも構いません。

このような条件が与えられ、小人たちには作戦タイムが与えられました。 小人たちは少しでも数多く生き残れるような戦術をとるものとします。 たとえば、一番後ろの小人が目の前の小人の帽子の色を答え、 その小人は食べられてしまうとしても、次に後ろから二番目の小人が 今と同じ答えを言えば、その小人は助かります。 これを繰り返していけば、最低でも半分の小人は助かることなります。

さて、小人たちは何人助かるでしょうか？ また、そのときの戦略は？

なお、被らされる帽子の順番に特徴的なもの （赤、青、黄色が順番にならんでいるとか） はないものとします。