基本例題 支払いに関する場合の数
1500円,100円, 10円の3種類の硬貨がたくさんある。この3種類の硬貨を使っ
1200円を支払う方法は何通りあるか。 ただし, 使わない硬貨があってもよい
ものとする。
指針支払いに使う硬貨500円, 100円, 10円の枚数をそれぞれx, y, z とすると
500x+100y+10z=1200(xは0以上の整数)
この解(x,y,z)の個数を求める。
からxの値を絞り、 場合分けをする。
・金額が最も大きい 500円の枚数xで場合分けすると、分け方が少なくてすむ。
支払いに使う500円 100円, 10円硬貨の枚数をそれぞれx, y,|
とすると, x,y,zは0以上の整数で
500x+100y+10z = 1200 すなわち 50x+10y+z=120
よって
ゆえに 50x120-10y+z) 120
xは0以上の整数であるから
[]x=2のとき
10y+z=20
この等式を満たす0以上の整数y, zの組は
(y,z)=(2,0),(1,10),(0,20) の3通り。
x=0, 1,2
[2]x=1のとき
10y+z=70
この等式を満たす0以上の整数y, zの組は
5x≤12
²7,0),(6,10), ......, (0,70)の8通り。
基本7
[3]x=0のとき
10y+z=120
この等式を満たす0以上の整数y の組は
(y, z)=(12, 0), (11, 10), …... (0, 120) 13通り。
[1] [2] [3] の場合は同時には起こらないから, 求める場合の
は
3+8+13=24 (通り)
不定方程式 (p.515~)。
y, 2≧0であるから
50x≤120 これを満た
す0以上の整数を求める。
10y=20-2≦20 から
10y 20 すなわち y≦2
よって y=0, 12
<10y=70-zM70 から
10y70 すなわち y≦7
よって y=0, 1, …, 7
<10y=120-z≦120から
10y120 すなわち y≦12
よって y=0, 1, …, 12
の法則