こんにちは。東久留米市の学習塾塾長です。
快晴で気温も２０℃と過ごしやすい日になりました。明日、明後日は、前線を伴う低気圧の影響で下り坂ですが、それ以降は、いい天気が続くようです。
さて、今回は２００３年日本数学オリンピック予選に出題された整数問題を取り上げます。
問題は、
「１円玉、５円玉、１０円玉、５０円玉、１００円玉、５００円玉を使ってちょうど７７７円を支払い、支払う硬貨の合計枚数が最小になるようにする。このときの合計枚数を求めよ。
ただし、どの硬貨も十分な枚数をもっているものとし、使わない硬貨があってもよいものとする。」
です。
早速、取り掛かりましょう。
１円玉、５円玉、１０円玉、５０円玉、１００円玉、５００円玉を使ってちょうど７７７円を支払う方法は有限個なので、硬貨の合計枚数を最小にする支払い方が存在します。
そこで、７７７円の支払いに使う１円玉、５円玉、１０円玉、５０円玉、１００円玉、５００円玉の枚数をそれぞれａ枚、ｂ枚、ｃ枚、ｄ枚、ｅ枚、ｆ枚とすると、
ａ＋５ｂ＋１０ｃ＋５０ｄ＋１００ｅ＋５００ｆ＝７７７ （１）
が成り立ちます。
このとき、５円を支払うとき、５枚の１円玉より１枚の５円玉のほうが硬貨の枚数が少ないので、
０≦ａ≦４
です。
同様に、２枚の５円玉と１枚の１０円玉、５枚の１０円玉と１枚の５０円玉、２枚の５０円玉と１枚の１００円玉、５枚の１００円玉と１枚の５００円玉では、それぞれ後者のほうが硬貨の枚数が少ないので、
０≦ｂ≦１
０≦ｃ≦４
０≦ｄ≦１
０≦ｅ≦４
です。
これらを基にして調べていきましょう。
まず、ａ＋５ｂ＋１０ｃ＋５０ｄ＋１００ｅの最大値を調べると、それは、ａ＝４、ｂ＝１、ｃ＝４、ｄ＝１、ｅ＝４のときで、
４＋５＋４０＋５０＋４００＝４９９
です。
すると（１）から
５００ｆ＝７７７－（ａ＋５ｂ＋１０ｃ＋５０ｄ＋１００ｅ）
≧７７７－４９９
≧２７８
で、ｆ≧１です。
このとき、ｆ≧２とすると、
ａ＋５ｂ＋１０ｃ＋５０ｄ＋１００ｅ＋５００ｆ≧ａ＋５ｂ＋１０ｃ＋５０ｄ＋１００ｅ＋１０００
＞７７７
になり、「ちょうど７７７円を払う」ことができません。
したがって、ｆ＝１になります。
次に、ｆ＝１を（１）に代入して整理すると、
ａ＋５ｂ＋１０ｃ＋５０ｄ＋１００ｅ＝２７７ （２）
になります。
ここで、ａ＋５ｂ＋１０ｃ＋５０ｄの最大値を調べると、それは、ａ＝４，ｂ＝１、ｃ＝４、ｄ＝１のときで、
４＋５＋４０＋５０＝９９
です。
すると（２）から
１００ｅ＝２７７－（ａ＋５ｂ＋１０ｃ＋５０ｄ）
≧２７７－９９
＝１８８
で、ｅ≧１です。
このとき、ｅ≧３とすると、
ａ＋５ｂ＋１０ｃ＋５０ｄ＋１００ｅ＋５００≧ａ＋５ｂ＋１０ｃ＋５０ｄ＋３００＋５００
＝ａ＋５ｂ＋１０ｃ＋５０ｄ＋８００
＞７７７
になり、「ちょうど７７７円を払う」ことができません。
また、ｅ＝１とすると、（２）から
ａ＋５ｂ＋１０ｃ＋５０ｄ＝１７７＞９９
になり、７７７円支払うことができません。
したがって、ｅ＝２になります。
次に、ｅ＝２を（２）に代入して整理すると、
ａ＋５ｂ＋１０ｃ＋５０ｄ＝７７ （３）
になります。
ここで、ａ＋５ｂ＋１０ｃの最大値を調べると、それは、ａ＝４、ｂ＝１、ｃ＝４のときで、
４＋５＋４０＝４９
です。
すると（３）から
５０ｄ＝７７－（ａ＋５ｂ＋１０ｃ）
≧７７－４９
＝２８
で、ｄ≧１です。
このとき、ｄ≧２とすると、
ａ＋５ｂ＋１０ｃ＋５０ｄ＋２００＋５００≧ａ＋５ｂ＋１０ｃ＋１００＋２００＋５００
＝ａ＋５ｂ＋１０ｃ＋８００
＞７７７
になり、「ちょうど７７７円を払う」ことができません。
したがって、ｄ＝１になります。
次に、ｄ＝１を（３）に代入して整理すると、
ａ＋５ｂ＋１０ｃ＝２７ （４）
になります。
ここで、ａ＋５ｂの最大値を調べると、それは、ａ＝４、ｂ＝１のときで、
４＋５＝９
です。
すると（４）から
１０ｃ＝２７－（ａ＋５ｂ）
≧２７－９
＝１８
で、ｃ≧２です。
このとき、ｃ≧３とすると、
ａ＋５ｂ＋１０ｃ＋５０＋２００＋５００≧ａ＋５ｂ＋３０＋５０＋２００＋５００
＝ａ＋５ｂ＋７８０
＞７７７
になり、「ちょうど７７７円を払う」ことができません。
したがって、ｃ＝２になります。
次に、ｃ＝２を（４）に代入して整理すると、
ａ＋５ｂ＝７ （５）
になります。
ここで、ａの最大値を調べると、それは、ａ＝４です。
すると、（５）から
５ｂ＝７－ａ
≧７－４
＝３
で、ｂ≧１です。
このとき、ｂ≧２とすると、
ａ＋５ｂ＋２０＋５０＋２００＋５００≧ａ＋１０＋２０＋５０＋２００＋５００
＝ａ＋７８０
＞７７７
になり、「ちょうど７７７円を払う」ことができません。
したがって、ｂ＝１になります。
最後に、ｂ＝１を（５）に代入して整理すると、
ａ＋５＝７
から、ａ＝２になります。
以上から、１円玉２枚、５円玉１枚、１０円玉２枚、５０円玉１枚、１００円玉２枚、５００円玉１枚を使って７７７円支払う場合が硬貨の合計枚数が最小になり、その合計枚数は ９枚 で、これが答えです。
長くなりましたが、やっていることは簡単です。
快晴で気温も２０℃と過ごしやすい日になりました。明日、明後日は、前線を伴う低気圧の影響で下り坂ですが、それ以降は、いい天気が続くようです。
さて、今回は２００３年日本数学オリンピック予選に出題された整数問題を取り上げます。
問題は、
「１円玉、５円玉、１０円玉、５０円玉、１００円玉、５００円玉を使ってちょうど７７７円を支払い、支払う硬貨の合計枚数が最小になるようにする。このときの合計枚数を求めよ。
ただし、どの硬貨も十分な枚数をもっているものとし、使わない硬貨があってもよいものとする。」
です。
早速、取り掛かりましょう。
１円玉、５円玉、１０円玉、５０円玉、１００円玉、５００円玉を使ってちょうど７７７円を支払う方法は有限個なので、硬貨の合計枚数を最小にする支払い方が存在します。
そこで、７７７円の支払いに使う１円玉、５円玉、１０円玉、５０円玉、１００円玉、５００円玉の枚数をそれぞれａ枚、ｂ枚、ｃ枚、ｄ枚、ｅ枚、ｆ枚とすると、
ａ＋５ｂ＋１０ｃ＋５０ｄ＋１００ｅ＋５００ｆ＝７７７ （１）
が成り立ちます。
このとき、５円を支払うとき、５枚の１円玉より１枚の５円玉のほうが硬貨の枚数が少ないので、
０≦ａ≦４
です。
同様に、２枚の５円玉と１枚の１０円玉、５枚の１０円玉と１枚の５０円玉、２枚の５０円玉と１枚の１００円玉、５枚の１００円玉と１枚の５００円玉では、それぞれ後者のほうが硬貨の枚数が少ないので、
０≦ｂ≦１
０≦ｃ≦４
０≦ｄ≦１
０≦ｅ≦４
です。
これらを基にして調べていきましょう。
まず、ａ＋５ｂ＋１０ｃ＋５０ｄ＋１００ｅの最大値を調べると、それは、ａ＝４、ｂ＝１、ｃ＝４、ｄ＝１、ｅ＝４のときで、
４＋５＋４０＋５０＋４００＝４９９
です。
すると（１）から
５００ｆ＝７７７－（ａ＋５ｂ＋１０ｃ＋５０ｄ＋１００ｅ）
≧７７７－４９９
≧２７８
で、ｆ≧１です。
このとき、ｆ≧２とすると、
ａ＋５ｂ＋１０ｃ＋５０ｄ＋１００ｅ＋５００ｆ≧ａ＋５ｂ＋１０ｃ＋５０ｄ＋１００ｅ＋１０００
＞７７７
になり、「ちょうど７７７円を払う」ことができません。
したがって、ｆ＝１になります。
次に、ｆ＝１を（１）に代入して整理すると、
ａ＋５ｂ＋１０ｃ＋５０ｄ＋１００ｅ＝２７７ （２）
になります。
ここで、ａ＋５ｂ＋１０ｃ＋５０ｄの最大値を調べると、それは、ａ＝４，ｂ＝１、ｃ＝４、ｄ＝１のときで、
４＋５＋４０＋５０＝９９
です。
すると（２）から
１００ｅ＝２７７－（ａ＋５ｂ＋１０ｃ＋５０ｄ）
≧２７７－９９
＝１８８
で、ｅ≧１です。
このとき、ｅ≧３とすると、
ａ＋５ｂ＋１０ｃ＋５０ｄ＋１００ｅ＋５００≧ａ＋５ｂ＋１０ｃ＋５０ｄ＋３００＋５００
＝ａ＋５ｂ＋１０ｃ＋５０ｄ＋８００
＞７７７
になり、「ちょうど７７７円を払う」ことができません。
また、ｅ＝１とすると、（２）から
ａ＋５ｂ＋１０ｃ＋５０ｄ＝１７７＞９９
になり、７７７円支払うことができません。
したがって、ｅ＝２になります。
次に、ｅ＝２を（２）に代入して整理すると、
ａ＋５ｂ＋１０ｃ＋５０ｄ＝７７ （３）
になります。
ここで、ａ＋５ｂ＋１０ｃの最大値を調べると、それは、ａ＝４、ｂ＝１、ｃ＝４のときで、
４＋５＋４０＝４９
です。
すると（３）から
５０ｄ＝７７－（ａ＋５ｂ＋１０ｃ）
≧７７－４９
＝２８
で、ｄ≧１です。
このとき、ｄ≧２とすると、
ａ＋５ｂ＋１０ｃ＋５０ｄ＋２００＋５００≧ａ＋５ｂ＋１０ｃ＋１００＋２００＋５００
＝ａ＋５ｂ＋１０ｃ＋８００
＞７７７
になり、「ちょうど７７７円を払う」ことができません。
したがって、ｄ＝１になります。
次に、ｄ＝１を（３）に代入して整理すると、
ａ＋５ｂ＋１０ｃ＝２７ （４）
になります。
ここで、ａ＋５ｂの最大値を調べると、それは、ａ＝４、ｂ＝１のときで、
４＋５＝９
です。
すると（４）から
１０ｃ＝２７－（ａ＋５ｂ）
≧２７－９
＝１８
で、ｃ≧２です。
このとき、ｃ≧３とすると、
ａ＋５ｂ＋１０ｃ＋５０＋２００＋５００≧ａ＋５ｂ＋３０＋５０＋２００＋５００
＝ａ＋５ｂ＋７８０
＞７７７
になり、「ちょうど７７７円を払う」ことができません。
したがって、ｃ＝２になります。
次に、ｃ＝２を（４）に代入して整理すると、
ａ＋５ｂ＝７ （５）
になります。
ここで、ａの最大値を調べると、それは、ａ＝４です。
すると、（５）から
５ｂ＝７－ａ
≧７－４
＝３
で、ｂ≧１です。
このとき、ｂ≧２とすると、
ａ＋５ｂ＋２０＋５０＋２００＋５００≧ａ＋１０＋２０＋５０＋２００＋５００
＝ａ＋７８０
＞７７７
になり、「ちょうど７７７円を払う」ことができません。
したがって、ｂ＝１になります。
最後に、ｂ＝１を（５）に代入して整理すると、
ａ＋５＝７
から、ａ＝２になります。
以上から、１円玉２枚、５円玉１枚、１０円玉２枚、５０円玉１枚、１００円玉２枚、５００円玉１枚を使って７７７円支払う場合が硬貨の合計枚数が最小になり、その合計枚数は ９枚 で、これが答えです。
長くなりましたが、やっていることは簡単です。
