中学生でも解ける東大大学院入試問題（７８）

こんにちは。東久留米市の学習塾塾長です。

昨日より気温は高いですが、弱い北風が吹いて寒く感じます。今日もラジオで箱根駅伝を聴いていますが、青山学院が快走中です。

さて、今回は平成２６年度東大大学院工学系研究科システム創成学の入試問題です。

問題は、
「１００人の学生が１００点満点のテストを受けた。全学生の合計点が４９００点だったとき、同じ点数を取った学生がいることを示せ。ただし、点数は非負の整数とする。」
です。

これは背理法を使うと簡単です。背理法は、中３の数学で√２が無理数であることを証明するときに出てきますが、それは、初めに、与えられた命題が成り立たないと仮定して矛盾が生じることを示す証明法です。

本問の場合は、「同じ点数を取った学生がいない」と仮定して矛盾が生じることを示すことになります。

それでは始めましょう。１００人の学生が１００点満点のテストを受けて、各学生の点数は負でない整数で、同じ点数を取った学生がいないのですから、学生の取った点数は、０点から１００点までの１０１種類のなかから１００種類を選んだものになります。

ここで、選ばれなかった点数をａとすると、全学生の合計点Ｓは、
Ｓ＝０＋１＋２＋・・・＋１００－ａ
　＝５０５０－ａ　　　　　　　　　　　　（１）
０≦ａ≦１００、ａは整数　　　　　　　　（２）
となります。

一方、全学生の合計点は４９００点なので、（１）から、
５０５０－ａ＝４９００
となり、
ａ＝１５０
です。

これは、（２）と矛盾し、これは、「同じ点数を取った学生がいない」と仮定したことによって生じたので、結論として、「同じ点数を取った学生がいる」となります。

背理法は都立高校入試には出題されませんが、頭に入れておくと役に立つこともあるでしょう。