d:id:nuc:20050823:p2
確定的に出来る。少なくともn-1人が当てられる方法。
西からと名前を付け、赤なら0、白なら1とする。
- は自分より東にいる人の白帽子の数を数える。
- は白帽子の数の偶奇を伝える。が当たるかどうかは定かではない。
- は自分より東にいる人の白帽子の数を数える。
- はの情報と自分が計算した値から自分の帽子の値を計算出来る。
- は同様に自分の帽子の数を推測できる。
- 以下同様。
google:小人のパズル]やら[google:小人 帽子の色で見つかるなぁ。
すごい勘違い。恥ずかしい(;´Д`)
n-1人は上のプロトコルで確実に当てられるので、が自分の帽子を当てる確率が1/2であれば題意は示される。
等確率
なので、1/2で問題無し。
帽子の色分けは2^n通りあるけど、偶奇しか問題にしていないので、1/2でOK。