数学A

場合の数の問題なのですが、
硬貨の一部または全部を使って、支払うことができる金額は何通りあるか。
(1)　１０円硬貨４枚　５０円硬貨１枚　１００円硬貨３枚
(2)　１０円硬貨２枚　５０円硬貨３枚　１００円硬貨３枚
(3)　１０円硬貨７枚　５０円硬貨１枚　１００円硬貨３枚
の３つの場合です。
それぞれの解き方はなんとなくわかるのですが、
どんなときにどの解き方を使えばよいのかわかりません。
そこんところを宜しくお願いします。
（例）
(1)　(2)　については　５×２×４－１＝３９　３×２×５－１＝２９
なのに(3)はできな～い
(1)　(3)　については　３９０÷１０＝３９　４２０÷１０＝４２
なのに(2)はできな～い

No.3 ベストアンサー 回答者： kumipapa 回答日時： 2007/11/04 18:35

どんな場合でも必ず同じ方法で解ける方法を考えるのはなかなかやっかいだし、その方法があったとしても、それが実用上最善かどうかは疑問です。

例えば、１０円Ａ枚、５０円Ｂ枚、１００円Ｃ枚を組み合わせる場合、
f(x) = (1+x^1+x^2+...+x^A)(1+x^5+x^10+...+x^(5B))(1+x^10+x^20+...+x^(10C) )
という多項式を考えて、これを展開したときのx^y (y≧1）の項の数が、支払うことのできる金額の通りの数になります。１０円２枚、５０円３枚、１００円１枚ならば
f(x) = (1+x^1+x^2)(1+x^5+x^10+x^15)(1+x^10)
=1+x^1+x^2+x^5+x^6+x^7+2x^10+2x^11+2x^12+2x^15+2x^16+2x^17+x^20+x^21+x^22+x^25+x^26+x^27
となって、x^y (y≧1）の項の数は１７個だから、１７通りの金額を支払える。ちなみに、x^10やx^11などいくつかの項の係数が2なのは、100円や110円払うときには２通りの払い方があることを示しています。
もっと良い方法もあるかもしれませんが、例えばこの考え方ならば、どんな硬貨が何枚づつあろうと必ず解けます。が、こんな面倒なことをして解こうとは思わないですよね。
組み合わせの問題を考える場合には柔軟にいろいろな考え方を身に付けた方が良いです。ひとつの方法（考え方）に無理やりあてはめようとするとかえって失敗したり、時間が無駄になる場合が多い。 だから、質問者さんの回答で問題なし。ただ、どんなときにどんな方法かは、ぱっと選択できるようにしておくことが必要でしょう。そこは慣れ、経験でしょうか。

ただ、今回の質問で３９０÷１０＝３９、４２０÷１０＝４２という考え方をちょっと広げて、そこから「払えない額の通りの数を引く」ということを追加してやればほとんどの場合に対応できそうです。例えば（２）を解こうとすると、
１０円×２枚＋５０円×３枚＋１００円×３枚＝４７０円
４７０円÷１０円＝４７
ただし、１０円の位が３，４，８，９は支払えないので、
４００円以下では　Ｘ３０，Ｘ４０，Ｘ８０，Ｘ９０のＸが０から３の４×４＝１６通りを支払えない
４００円台では４３０円，４４０円の２通りを支払えない
の合計１８通りが払えないので４７－１８＝２９通りの金額を支払える。

この回答への補足

回答ありがとうございます。
おかげでバッチリわかりました。
これからはその方法で頑張っていきます＾＾

補足日時：2007/11/04 19:14

No.2 回答者： DONTARON 回答日時： 2007/11/04 17:39

（１）（３）のように１０円硬貨が４枚以上あり５０円硬貨もあり１００円硬貨が３枚あるということは、

（１）（３）ともに１０円から３９０円までは１０円ごとの支払いがすべてできます。
（１）は最高３９０円まで（３）は４２０円までできるので
すでに答えは書かれてある通りです。
（２）の場合は１０円硬貨が２枚しかないので
できる場合だけ書いていくと
１０,２０,５０,６０,７０，１００，１１０，１２０，１５０,１６０，１７０，２００，２１０，２２０,２５０，２６０，２７０，３００，３１０，３２０，３５０，３６０，３７０、４００，４１０，４２０，４５０，４６０，４７０
これも答えは書かれてある通り
すべて答えは出ています。
解き方はどんな解き方でもかまいません。
すべて同じ解き方で解かなくてもかまいません。

この回答への補足

回答ありがとうございます。
全通りを書くということは確かに間違いないのですが、
自分は一応これを全部いちいち書かずに出す方法を探しています。
なければしょうがないですが.....

補足日時：2007/11/04 19:12

No.1 回答者： noname#47894 回答日時： 2007/11/04 17:38

(1)　(2)　については　５×２×４－１＝３９　３×２×５－１＝２９

なんの計算かと思いましたが、なんとなくわかりました。
10の位の数が、何通り可能か求めて、次に、どこまで大きくできるか調べた方が早いような．．．

（１）は、00～90　まで　10通り可能、最大で390円、0円っていうのはダメなんだろうから、39通り

（２）は、00、10、20、50、60、70の６通りが可能で、最大で470円で、４×６－1で23通り

（３）は、00～90　まで　10通り可能、最大で420円、42通り

でいいと思います。
その質問方法にある計算方法も捨てがたいですが、どのような場合に可能で、どのような場合に不可かがわからないと使い物にならないでしょう。

この回答への補足

ご説明ありがとうございます。
（１）、（２）についてはよく理解できたのですが、
（３）が微妙で.....
えっと、９通りでできない場合のみ
１０の位の通り×最大の数の１００の位ー１で
そのほかは最大÷１０の位の通りでOK何でしょうか？

補足日時：2007/11/04 19:06