数学パズル　帽子ゲーム

難しい。そろそろ寝るのでとりあえず固まったところまで頑張ってみる。

教授が学生に次のようなゲームを提案した
１：学生に赤か白の帽子をかぶせ　自分の帽子は見えないが他人の帽子は見えるようにする
２：学生に順番に自分の帽子の色を予想して答えさせる　答は他の学生もわかるように行うが答えた色以外の情報は伝わらないとする
３：教授が学生に見えないように賽子をふる
１〜３を６回繰り返した後　教授が賽子で偶数を出した回の帽子の色を当てた人数を合計して学生に知らせる
６回のうちどの回で教授が偶数を出したか当てられれば学生の勝ちというゲームである
このゲームに学生が必ず勝つには学生が何人いればよいか　またその必ず勝つにはどうすればよいか
ただし学生は事前に相談出来るものとする

http://d.hatena.ne.jp/DreamSnow/20071112#1194884653

とりあえず全試行において学生側が正解の数を0から学生の数まで任意に決めることができることは自明。……自明じゃないけれどまあいいか。

そこで教授がどんな数を言っても、どの回の正解数の和であるかがわかればいいので、この問題は次のようになる。

次の条件を満たす最低の自然数 *1 $n$ を求めよ。
条件:自然数 $n$ 以下の相異なる $6$ つの自然数をうまく選ぶと、そのうちのどんな組み合わせの数の和も一致することがない。

まず、最低でも $15$ 人は必要であると示せる。
選ばれた $6$ つの数のうち、 $2$ 数の差が等しい組が存在するとそれらの数には次の関係が成り立つ。
$a_1 - a_2 = a_3 - a_4$ 　つまり
$a_1+a_4=a_2+a_3$ 　となり、条件に反する。
よって選ぶ $6$ 数のうちの $2$ 数の差は全て相異なる。
$6$ 数間の $2$ 数の差は $_6C_2 = 15$ 通りあり、また条件から $6$ 数全て自然数なので $6$ 数のうち最低の数と最大の数の差は最低でも $15$ 以上である。
よって、学生の数は15人以上必要である。