指定された種類の硬貨がそれぞれ指定された枚数あるとき、これらの硬貨の一部または全部を使って、ちょうど支払うことができる金額は何通りあるかを求める問題です。 (1) 10円硬貨4枚、50円硬貨1枚、100円硬貨3枚 (2) 10円硬貨2枚、50円硬貨3枚、100円硬貨3枚 (3) 10円硬貨7枚、50円硬貨1枚、100円硬貨3枚

1. 問題の内容

指定された種類の硬貨がそれぞれ指定された枚数あるとき、これらの硬貨の一部または全部を使って、ちょうど支払うことができる金額は何通りあるかを求める問題です。

(1) 10円硬貨4枚、50円硬貨1枚、100円硬貨3枚

(2) 10円硬貨2枚、50円硬貨3枚、100円硬貨3枚

(3) 10円硬貨7枚、50円硬貨1枚、100円硬貨3枚

2. 解き方の手順

各場合について、考えられる金額の組み合わせを数え上げます。ただし、支払わない場合（0円）を除く必要があります。また、同じ金額になる組み合わせが複数ある場合、それは1通りとしてカウントします。

10円硬貨、50円硬貨、100円硬貨の枚数をそれぞれ$x, y, z$とします。

(1)

10円硬貨は0枚から4枚、50円硬貨は0枚または1枚、100円硬貨は0枚から3枚使用できます。

単純に考えると、$(4+1) \times (1+1) \times (3+1) = 5 \times 2 \times 4 = 40$通りですが、全て0枚の場合(0円)は除くので39通りです。

ここで、10円玉5枚で50円になるので、10円玉だけで50円以上にできる場合は、50円玉を10円玉に置き換えることを検討します。

10円硬貨4枚で最大40円、50円硬貨1枚で50円、100円硬貨3枚で300円。

10円硬貨の取りうる金額は0, 10, 20, 30, 40円の5通り。

50円硬貨の取りうる金額は0, 50円の2通り。

100円硬貨の取りうる金額は0, 100, 200, 300円の4通り。

これらの組み合わせで金額が重複するものはないので、$(4+1)(1+1)(3+1) - 1 = 5 \cdot 2 \cdot 4 - 1 = 40 - 1 = 39$通り。

(2)

10円硬貨は0枚から2枚、50円硬貨は0枚から3枚、100円硬貨は0枚から3枚使用できます。

10円硬貨2枚で最大20円、50円硬貨3枚で150円、100円硬貨3枚で300円。

10円硬貨の取りうる金額は0, 10, 20円の3通り。

50円硬貨の取りうる金額は0, 50, 100, 150円の4通り。

100円硬貨の取りうる金額は0, 100, 200, 300円の4通り。

単純に考えると、$(2+1) \times (3+1) \times (3+1) = 3 \times 4 \times 4 = 48$通りですが、全て0枚の場合(0円)は除くので47通りです。

50円玉2枚で100円になるので、100円を50円2枚に置き換えることを検討します。

100円硬貨1枚=50円硬貨2枚 と考えると、50円硬貨は最大3+3*2=9枚まで使用できることになります。

このとき、取りうる金額は0,10,20,50,100,150,200,250,300,350,400,450です。

しかし、10円は最大20円しか作れないので、重複する金額はないと考えられます。

したがって、$(2+1)(3+1)(3+1) - 1 = 3 \times 4 \times 4 - 1 = 48 - 1 = 47$通り。

(3)

10円硬貨は0枚から7枚、50円硬貨は0枚または1枚、100円硬貨は0枚から3枚使用できます。

10円硬貨7枚で最大70円、50円硬貨1枚で50円、100円硬貨3枚で300円。

10円硬貨の取りうる金額は0, 10, 20, 30, 40, 50, 60, 70円の8通り。

50円硬貨の取りうる金額は0, 50円の2通り。

100円硬貨の取りうる金額は0, 100, 200, 300円の4通り。

単純に考えると、$(7+1) \times (1+1) \times (3+1) = 8 \times 2 \times 4 = 64$通りですが、全て0枚の場合(0円)は除くので63通りです。

10円玉5枚で50円になるので、10円玉だけで50円以上にできる場合は、50円玉を10円玉に置き換えることを検討します。

10円硬貨7枚までなので、50円硬貨1枚を10円5枚に置き換えることは可能です。

50円玉を使わないとき、0円, 10円, 20円, 30円, 40円, 50円, 60円, 70円の8通り。

50円玉を使うとき、50円, 60円, 70円, 80円, 90円, 100円, 110円, 120円の8通り。

ここで、50円硬貨を使わない場合と使う場合で金額が重複する可能性があるのは、50, 60, 70円です。

50円硬貨を使わない場合でも50円, 60円, 70円を作れるので、これらを重複して数えないようにします。

50円硬貨を使わない場合は8通り。50円硬貨を使う場合は50円, 60円, 70円を除いた5通り。

100円硬貨は0, 100, 200, 300円の4通り。

したがって、$(8+5) \times 4 - 1 = 13 \times 4 - 1 = 52 - 1 = 51$通りとなります。

しかし、これは間違っています。

10円玉が5枚以上あるので、50円玉を10円玉に変換して考えることが可能。

10円玉を7枚、50円玉1枚持っている状態は、10円玉を12枚持っている状態と同じ。

よって、10円玉と100円玉の組み合わせを考えれば良い。

10円玉は0-12枚, 100円玉は0-3枚

$13 \times 4 = 52$通り、ただし0円を除くので51通り。

3. 最終的な答え

(1) 39通り

(2) 47通り

(3) 51通り