スタッフBLOG

帽子の色 答え2016年10月26日

こんにちは、チューターの田村です。

先週の問題の答えです。

 

もう一度問題を書いておきます。

 

問題1

赤か白の帽子をランダムにかぶった100人が縦一列に並ぶ。

後ろの人から1番、2番、…と番号を付けていくと、自分より大きな番号の人の帽子は見える。

(例えば1番の人は自分以外の人の帽子は見えています。)

全員が順番に自分の帽子の色(だと思う色)を答える。(答える順番は好きな順番で良い。)

ゲーム開始前(帽子をかぶる前)に全員で作戦を練れるとして、帽子の色を間違える人を最多でも1人に抑える作戦は?

ただし、ゲーム開始後は色を答える以外の行動はできないとし、また解答者以外は解答者が答えた色以外の情報は何も与えられないとする。

 

問題2

問題1とルールは同様で、今度は無限人(1番、2番、…)が縦一列に並ぶ。

帽子の色を間違える人を有限人に抑える作戦は?

 

 

答え1

この問題のポイントは起きうる全ての場合を大きく2つに分けることです。

 

1番の人は自分の帽子の色を知る方法が無いので、逆に言うと1番以外の人は全員正解しなければいけません。

つまり、情報を2つに分け、1番の人がそのどちらであるかを答え、それをもとに2番以降の人が答えていくのです。

 

さて、答えです。

2つに分けるとしたら、すぐに思いつくのは偶奇での場合分けですね。

1番の人は、2~100番の中に赤の帽子をかぶった人が偶数人いたら赤、奇数人いたら白と言います。

あとは2番以降の人は自分より前の人と今まで出た答えから自分の色を推測して答えれば良いです。

 

例えば、1番目の人が赤と言い、2番目の人の番に、自分より前に赤の帽子をかぶった人が奇数人見えていたとします。

すると、自分を入れて赤をかぶった人が偶数人いなくてはいけないので自分は赤だとわかります。

 

答え2

これはかなり難しいです。

自力で解けた人は間違いなく天才だと思います。

 

まず、起きうる全ての場合を考え、次の同値関係を考えます。(分数で1/2と2/4を等しいとみなすのと同じ考えです。)

2つの全員の帽子のかぶり方は有限人を除いて同じとき等しい

例えば、赤赤赤…というかぶり方と赤白赤赤…(どちらも…はずっと赤)を等しいとみなし、赤赤赤…(ずっと赤)と白白白…(ずっと白)は異なります。

同値関係で等しいとみなしたもの(同値類といいます)の中からそれぞれ一つをとってきます。(分数で言うと既約分数を選ぶ事と似ています。1/2,2/4,3/6,…の中から1/2を選び、1/3,2/6,3/9,…から1/3を選び、…。)

これを代表元(1/2,1/3,…)といいます。

 

さて、実際に今自分が見ている帽子を見ると今の帽子のかぶり方がどの同値類に入っているか分かります。

というのも、自分より後ろの人は有限人しかいないので、自分より後ろの帽子の色がどうなっていようとも同じ同値類に入ります。

そこでその同値類の代表元を考え、その代表元での自分の帽子の色を答えます

すると、実際の帽子のかぶり方と、答えた帽子の色は同じ同値類に入っているので有限人を除いて同じになるはずです。

つまり、間違える人は有限人になります。