MarriageTheoremのこと

_ プレプリント確認状況：arXiv:math 8月3日分まで、arXiv:quant-ph 5月31日分まで、IACR ePrint：2012/048まで

_ "prisoners and hats puzzle"と呼ばれているらしい問題を某所で知った。曰く、

無限の人数の囚人たちがそれぞれ赤か白の帽子を被らされ、各々は自分の被っている帽子を見ることはできないが、他の囚人の帽子の色は全て把握することができるとする。囚人たちは、帽子を被らされる前には互いに相談が可能だが、帽子を被った後には互いに相談できない。この状況で、囚人たちが一斉に自分の被った帽子の色を答えて、間違えた人数が有限であれば囚人たちの勝ちとなる。さて、どのように帽子を被らされたとしても必ず囚人たちが勝てるような戦略は存在するだろうか？

詳細は上のリンク先などにあるので省くけれども、選択公理を仮定すると（囚人の集合の濃度の如何に関わらず）必勝法の存在を示すことができる。さて、ではこのゲームの必勝法の存在は選択公理と同値だろうか？私は答えを知らないので、後で考えてみたい。