論理クイズ(帽子の色当て問題)

数学のクイズを紹介します。問題文は少し長いですがかなり面白いです。

問題設定

以下のゲームにおいて 12\dfrac{1}{2} よりも高い確率で成功する「作戦」を考えよ。

  • 登場人物は nn3\geq 3)人。みんなで協力して成功を目指す

  • 各々,黒か白の帽子をかぶせられる

  • どちらの色なのかはランダム(確率 12\frac{1}{2}),それぞれ独立

  • 各々,自分の帽子の色は分からないが,他の n1n-1 人の帽子の色は分かる

  • 他人の帽子の色を見た上で,みんなで事前に話し合って決めた「作戦」に基づき,各々が(全員同時に)自分の帽子の色を予測する。ただし,パスすることもできる。

  • 「成功」の条件は,「全員がパス」ではない,かつパスしなかった人は全員正解。

答えを見る前に考えてみてください!

確率1/2で成功する作戦

確率 12\dfrac{1}{2} で成功する作戦を構成するのは簡単です。nn人のうちリーダーを一人決めて,リーダーが「黒」,それ以外の人が「パス」を選べばOKです。

他の人の帽子の色を見たところで自分の帽子の色の情報は何も得られないのだから,成功確率を 12\dfrac{1}{2} よりも高くすることはできないと考える人もいるでしょう。しかし,12\dfrac{1}{2} よりも高くできるのです!

3人の場合,確率3/4で成功する作戦

n=3 の場合の解答

「自分以外の2人の色が同じなら,それとは異なる色を答える,そうでないならパス」という作戦で成功確率が34\frac{3}{4}になる。

黒黒黒 → 全員白と答えて失敗

黒黒白 → 黒の2人はパス,白の1人が正解

黒白白 → 白の2人はパス,黒の1人が正解

白白白 → 全員黒と答えて失敗

という感じです。(確率は上から順に18\frac{1}{8},38\frac{3}{8}38\frac{3}{8}18\frac{1}{8})

4人以上の場合

3人の場合の結果は4人以上の場合にも使えます(けっこう気づくの難しい)。

解答

n4n\geq 4 の場合の解答です。

代表者を3人選ぶ。代表者たちは他の人の帽子の色は無視してn=3n=3の場合の作戦を取る。他の人たちは全員パスする,という作戦で成功確率が34\frac{3}{4}になる。

ちなみに,さらに成功確率が高い作戦も存在します。 n=2k1n=2^k-1kk22 以上の整数)の場合には成功確率が nn+1\frac{n}{n+1} である作戦が構成できます(ハミング符号というものを用いる)。

ちょっとしたクイズ,論理パズルも記事にしていきたいです。