d:id:nuc:20050823:p2

確定的に出来る。少なくともn-1人が当てられる方法。
西からa_1,a_2,...,a_nと名前を付け、赤なら0、白なら1とする。

  1. a_1は自分より東にいる人の白帽子の数を数える。
    • a_1は白帽子の数の偶奇を伝える。a_1が当たるかどうかは定かではない。
  2. a_2は自分より東にいる人の白帽子の数を数える。
    • a_2a_1の情報と自分が計算した値から自分の帽子の値を計算出来る。
  3. a_3は同様に自分の帽子の数を推測できる。
  4. 以下同様。

google:小人のパズル]やら[google:小人 帽子の色で見つかるなぁ。

すごい勘違い。恥ずかしい(;´Д`)
n-1人は上のプロトコルで確実に当てられるので、a_1が自分の帽子を当てる確率が1/2であれば題意は示される。
等確率なので、1/2で問題無し。
帽子の色分けは2^n通りあるけど、偶奇しか問題にしていないので、1/2でOK。