18/07/20 23:44:33.17 RMS2vK39.net
またまたWinkler本から。囚人と看守のやつです。
----
あなたは他のn人と共にある牢獄に収監されている。
ある日看守からあるゲームに参加することを指示された。
勝てば全員釈放、負ければ全員死刑である。
ゲームの内容は以下のようなものである。
まず看守は秘密裏に囚人に順序付けを行う。
囚人は全員独居房に入れられた後、一人ずつ呼び出され、自分以外のn-1人の並びについて教えられる。
その情報のみに基づいて各囚人は赤か青の帽子を選択できる。
帽子を選択した後、囚人は独居房に戻される。
この作業を全員について行ったのち、囚人全員が集められ、先の決められた順に応じて整列させられる。
その際、囚人のかぶっている帽子の色が赤青交互になっていれば（一人目は赤でも青でもよい）囚人の勝ち、なっていなければ看守の勝ちである。
囚人に許されているのは、このルール説明の後、独居房に移される前に一度だけ全員が集まって選ぶ帽子の色についての取り決めをしておくことだけである。
それ以降には囚人は互いに情報を交換する機会は一切与えられない。
全員が釈放されるための取り決めを考えてほしい。
----
答え見て「へぇ、こんなシンプルな取り決めでうまくいくもんだなぁ」とちょっと感心しました。
取り決め自身はシンプルなんですが、その取り決めでうまくいく部分の証明がややてこずるかもしれません。
一つ解を見つければ正解です。
当方も別解があるのかどうか知りません。