東久留米 学習塾 塾長ブログ

東京都東久留米市滝山の個別指導型学習塾「学研CAIスクール 東久留米滝山校」塾長白井精一郎のブログ

日本数学オリンピックの簡単な問題(126)

2017-04-25 12:34:24 | 数学・算数の話
こんにちは。東久留米市の学習塾塾長です。

快晴で気温も20℃と過ごしやすい日になりました。明日、明後日は、前線を伴う低気圧の影響で下り坂ですが、それ以降は、いい天気が続くようです。

さて、今回は2003年日本数学オリンピック予選に出題された整数問題を取り上げます。

問題は、
「1円玉、5円玉、10円玉、50円玉、100円玉、500円玉を使ってちょうど777円を支払い、支払う硬貨の合計枚数が最小になるようにする。このときの合計枚数を求めよ。
 ただし、どの硬貨も十分な枚数をもっているものとし、使わない硬貨があってもよいものとする。」
です。

早速、取り掛かりましょう。

1円玉、5円玉、10円玉、50円玉、100円玉、500円玉を使ってちょうど777円を支払う方法は有限個なので、硬貨の合計枚数を最小にする支払い方が存在します。

そこで、777円の支払いに使う1円玉、5円玉、10円玉、50円玉、100円玉、500円玉の枚数をそれぞれa枚、b枚、c枚、d枚、e枚、f枚とすると、
a+5b+10c+50d+100e+500f=777    (1)
が成り立ちます。

このとき、5円を支払うとき、5枚の1円玉より1枚の5円玉のほうが硬貨の枚数が少ないので、
0≦a≦4
です。

同様に、2枚の5円玉と1枚の10円玉、5枚の10円玉と1枚の50円玉、2枚の50円玉と1枚の100円玉、5枚の100円玉と1枚の500円玉では、それぞれ後者のほうが硬貨の枚数が少ないので、
0≦b≦1
0≦c≦4
0≦d≦1
0≦e≦4
です。

これらを基にして調べていきましょう。

まず、a+5b+10c+50d+100eの最大値を調べると、それは、a=4、b=1、c=4、d=1、e=4のときで、
4+5+40+50+400=499
です。

すると(1)から
500f=777-(a+5b+10c+50d+100e)
    ≧777-499
    ≧278
で、f≧1です。

このとき、f≧2とすると、
a+5b+10c+50d+100e+500f≧a+5b+10c+50d+100e+1000
                        >777
になり、「ちょうど777円を払う」ことができません。

したがって、f=1になります。

次に、f=1を(1)に代入して整理すると、
a+5b+10c+50d+100e=277         (2)
になります。

ここで、a+5b+10c+50dの最大値を調べると、それは、a=4,b=1、c=4、d=1のときで、
4+5+40+50=99
です。

すると(2)から
100e=277-(a+5b+10c+50d)
    ≧277-99
    =188
で、e≧1です。

このとき、e≧3とすると、
a+5b+10c+50d+100e+500≧a+5b+10c+50d+300+500
                       =a+5b+10c+50d+800
                       >777
になり、「ちょうど777円を払う」ことができません。

また、e=1とすると、(2)から
a+5b+10c+50d=177>99
になり、777円支払うことができません。

したがって、e=2になります。

次に、e=2を(2)に代入して整理すると、
a+5b+10c+50d=77                (3)
になります。

ここで、a+5b+10cの最大値を調べると、それは、a=4、b=1、c=4のときで、
4+5+40=49
です。

すると(3)から
50d=77-(a+5b+10c)
   ≧77-49
   =28
で、d≧1です。

このとき、d≧2とすると、
a+5b+10c+50d+200+500≧a+5b+10c+100+200+500
                      =a+5b+10c+800
                      >777
になり、「ちょうど777円を払う」ことができません。

したがって、d=1になります。

次に、d=1を(3)に代入して整理すると、
a+5b+10c=27                    (4)
になります。

ここで、a+5bの最大値を調べると、それは、a=4、b=1のときで、
4+5=9
です。

すると(4)から
10c=27-(a+5b)
   ≧27-9
   =18
で、c≧2です。

このとき、c≧3とすると、
a+5b+10c+50+200+500≧a+5b+30+50+200+500
                     =a+5b+780
                     >777
になり、「ちょうど777円を払う」ことができません。

したがって、c=2になります。

次に、c=2を(4)に代入して整理すると、
a+5b=7                          (5)
になります。

ここで、aの最大値を調べると、それは、a=4です。

すると、(5)から
5b=7-a
  ≧7-4
  =3
で、b≧1です。

このとき、b≧2とすると、
a+5b+20+50+200+500≧a+10+20+50+200+500
                    =a+780
                    >777
になり、「ちょうど777円を払う」ことができません。

したがって、b=1になります。

最後に、b=1を(5)に代入して整理すると、
a+5=7
から、a=2になります。

以上から、1円玉2枚、5円玉1枚、10円玉2枚、50円玉1枚、100円玉2枚、500円玉1枚を使って777円支払う場合が硬貨の合計枚数が最小になり、その合計枚数は 9枚 で、これが答えです。


長くなりましたが、やっていることは簡単です。

東久留米の学習塾学研CAIスクール 東久留米滝山校
http://caitakiyama.jimdo.com/
TEL 042-472-5533
ジャンル:
ウェブログ
コメント   この記事についてブログを書く
この記事をはてなブックマークに追加
« 日本数学オリンピックの簡単... | トップ | 日本数学オリンピックの簡単... »
最近の画像もっと見る

コメントを投稿

数学・算数の話」カテゴリの最新記事