次の硬貨を全部または一部使って、ちょうど支払うことができる金額は何通りあるかを求める問題です。 (1) 10円硬貨5枚, 100円硬貨3枚, 500円硬貨3枚の場合 (2) 10円硬貨2枚, 50円硬貨3枚, 100円硬貨4枚の場合

1. 問題の内容

次の硬貨を全部または一部使って、ちょうど支払うことができる金額は何通りあるかを求める問題です。

(1) 10円硬貨5枚, 100円硬貨3枚, 500円硬貨3枚の場合

(2) 10円硬貨2枚, 50円硬貨3枚, 100円硬貨4枚の場合

2. 解き方の手順

(1)

10円硬貨5枚, 100円硬貨3枚, 500円硬貨3枚で支払える金額のパターン数を考えます。

10円硬貨は0枚から5枚の6通り、100円硬貨は0枚から3枚の4通り、500円硬貨は0枚から3枚の4通り使えます。

したがって、考えられる金額の組み合わせは、

$6 \times 4 \times 4 = 96$ 通り

ただし、全て0枚の場合（0円）は除くので、

$96 - 1 = 95$ 通り

ここで、100円玉を10円玉に換算して考えます。

100円玉3枚は10円玉30枚に相当します。

したがって、10円玉は最大で35枚まで使用可能です。

10円玉35枚で作れない金額は存在しません。

500円玉を10円玉に換算して考えます。

500円玉3枚は10円玉150枚に相当します。

したがって、10円玉は最大で155枚まで使用可能です。

10円玉155枚で作れない金額は存在しません。

ただし、金額が重複する場合があるので注意します。

10円硬貨の金額は $0, 10, 20, 30, 40, 50$ 円の6通り

100円硬貨の金額は $0, 100, 200, 300$ 円の4通り

500円硬貨の金額は $0, 500, 1000, 1500$ 円の4通り

それぞれの金額を組み合わせて作ることができる金額を考えます。

10円硬貨と100円硬貨で作れる金額は $0, 10, 20, 30, 40, 50, 100, 110, 120, 130, 140, 150, 200, 210, 220, 230, 240, 250, 300, 310, 320, 330, 340, 350$ 円の24通り

これに500円硬貨を組み合わせると、

$0, 10, 20, ..., 350, 500, 510, 520, ..., 850, 1000, 1010, 1020, ..., 1350, 1500, 1510, 1520, ..., 1850$ 円となります。

0円の場合を除くと、$6 \times 4 \times 4 - 1 = 96 - 1 = 95$ 通りです。

(2)

10円硬貨2枚, 50円硬貨3枚, 100円硬貨4枚で支払える金額のパターン数を考えます。

10円硬貨は0枚から2枚の3通り、50円硬貨は0枚から3枚の4通り、100円硬貨は0枚から4枚の5通り使えます。

したがって、考えられる金額の組み合わせは、

$3 \times 4 \times 5 = 60$ 通り

ただし、全て0枚の場合（0円）は除くので、

$60 - 1 = 59$ 通り

ここで、50円玉を10円玉に換算して考えます。

50円玉3枚は10円玉15枚に相当します。

したがって、10円玉は最大で17枚まで使用可能です。

100円玉を10円玉に換算して考えます。

100円玉4枚は10円玉40枚に相当します。

したがって、10円玉は最大で57枚まで使用可能です。

ただし、金額が重複する場合があるので注意します。

10円硬貨の金額は $0, 10, 20$ 円の3通り

50円硬貨の金額は $0, 50, 100, 150$ 円の4通り

100円硬貨の金額は $0, 100, 200, 300, 400$ 円の5通り

それぞれの金額を組み合わせて作ることができる金額を考えます。

この場合も、$3 \times 4 \times 5 - 1 = 60 - 1 = 59$ 通りです。

3. 最終的な答え

(1) 95通り

(2) 59通り