第４３２問の解答
問題［ 推理］
 |
 |
 |
|
|
算チャレ共和国では、次のような種類の硬貨が流通しています。
この国ではジュースは１本１０４円ですが、国民は上記の硬貨のうち（どのような組み合わせでもいいから）２０種類を１枚ずつ所有していれば、必ず２枚の硬貨で（ぴったり）支払うことができるので、特に不便は感じていないそうです。 では、この国で流通している硬貨の中で、最大金額のもの（上の？に当てはまる数）として考えられるもののうち、最大のものを答えてください。 |
|
 |
|
 |
解答例１
あ〜く＠ぴかぴかの（略さん、辻。さん、Taroさん、アヒーのおじさんさん、uchinyanさん、みかんさん、なかさん、スモークマンさん、N.Nishiさん、akiraさん、takaisaさん、トトロ＠Ｎさん、エルクさん、arijuneさん、他
鳩の巣原理を用います。
（鳩の巣原理）
ｎ個の巣に(n+1)個のハトが入れば、必ずどれかの巣には２羽以上
（証明）
どの巣にも１羽以下のハトしか入っていないと仮定すると、ハト合計数≦nとなって矛盾する。
よって、どれかの巣には２羽以上入っていることになります。さて、鳩の巣原理を念頭において本問を考えてみましょう。
この国の硬貨のうち、和が１０４円となる２種類の 硬貨をペアにしてグループをつくっていきます。
ただし、１０４円の半分となる５２円玉、および１０４円を超える額の硬貨は単独で１グループを作ることになります。（５２−１）÷２＋１＝１８なので、１円玉から５２円玉までで１８グループとなります。
５５円玉から１０３円玉までは、これらのグループに入りますが、
１０６円玉は新しいグループ、すなわち１９番目のグループとなります。１円玉から１０６円玉までの中から２０種類の硬貨を選ぶと、鳩の巣原理により、
必ずどれかのグループから２枚の硬貨が選ばれることになります。
従って、この２枚の硬貨で１０４円のジュースを買うことが出来ます。ところが、１０９円玉を加えると２０グループになるので、各グループより１枚ずつ２０種類の硬貨を選ぶことにより、どうやっても２枚の硬貨で１０４円となることはありません。
従って、 題意を満たすような最大の硬貨は１０６円玉と求まります。
答： １０６円玉
以上
