第３９問の解答
１．問題 ［推理算？］
|
ゆたか君のクラスでは、５人の委員を選ぶことになりました。そこで、全員が投票用紙に、自分自身を含めたクラス全員の中から５人の名前を書いて提出しました。 さて、ゆたか君が全ての投票用紙を調べてみたところ、面白いことに気づきました。どの投票用紙２枚を見比べても、同じ人の名前が１人だけ書かれていたのです。 ゆたか君のクラスの人数は何人なのでしょうか。 |
２．解答例（たなかさん他）
クラスの人数をｎ人、および題意にある、「どの投票用紙２枚を見比べても、同じ人の名前が１人だけ書かれていた」を投票一致性と呼ぶことにする。
（ｎ＞５となること）
５人投票できることから、ｎ≧５である。
もしちょうどｎ＝５とすると、全員が全員に投票することとなり、投票一致性に反するので、ｎ＞５となる。（全員が得票数５となること）
もし、全員の得票数が全て４以下とすると、得票数合計はｎ×４以下となるが、得票数合計は、投票数合計＝ｎ×５に等しいので、矛盾する。
よって、得票数は５以上である。得票が６以上の人がいたとする。この人をＸとしよう。
Ｘに投票した人を#1、#2、#3、#4、#5、#6・・とする。#1から#6のどの２人の投票結果を見ても、投票一致性からＸ以外の投票結果は全て異なるので、下図のようになる。
さて、もしクラス全員がＸに投票したとすると、投票数合計＝１＋ｎ×４となり矛盾するので、Ｘ以外の人に投票した人が必ずいることになる。これを、Ｚとしよう。
Ｚは、投票一致性から、a1、・・、a4の中から１人、b1、・・、ｂ4の中から１人、以下同様にして、f1、・・、f4の中から１人投票したことになる。すなわち、投票数が６以上になり、矛盾する。
よって、得票数は５以下でなければならず、結局全員の得票数が５となり、下図のようになる。
（クラスの人数が２１人となること）
上の図で、投票された人が２１人いることになる。
さて、#1から#5以外の任意の人をＺとする。
なお、実際に題意を満たす投票結果例として下記のようなものがある。
先ほどと同様に、Ｚはa1、・・、a4の中から１人、b1、・・、ｂ4の中から１人、以下同様にして、e1、・・、e4の中から１人投票したことになり、これだけで５票となる。
従って、上図にある人以外に投票された人はいないこととなり、クラスの人数は２１人と分かる。
