硬貨で支払える金額の場合の数(両替)

スポンサーリンク
以下の硬貨の全部または一部を使って支払える金額は何通りあるか.  (1)\ \ 100円硬貨が4枚,\ 50円硬貨が1枚,\ 10円硬貨が3枚  (2)\ \ 100円硬貨が1枚,\ 50円硬貨が3枚,\ 10円硬貨が2枚  (3)\ \ 100円硬貨が2枚,\ 50円硬貨が1枚,\ 10円硬貨が7枚 \\ 硬貨で支払える金額の場合の数 \\  (1)\ \ 100円硬貨4枚の使い方は,\ 0\,~\,4枚の 5通り 0}50円硬貨1枚の使い方は,\ 0\,~\,1枚の 2通り 0}10円硬貨3枚の使い方は,\ 0\,~\,3枚の 4通り ∴ 0円になる場合を除く}と  厄介なのは,\ (2),\ (3)のように異なる硬貨で同じ金額になりうる条件の場合である. (1)の条件では,\ 異なる硬貨で同じ金額になることはない. よって,\ 各硬貨がそれぞれ何通りの使い方ができるかを考え,\ 積の法則を利用}して求めれば済む.  (2)\ \ 100円硬貨1枚を50円硬貨2枚に両替}すると,\ 50円硬貨5枚,\ 10円硬貨2枚となる. 50円硬貨5枚の使い方は,\ 0\,~\,5枚の 6通り 10円硬貨2枚の使い方は,\ 0\,~\,2枚の 3通り 100円硬貨1枚と50円硬貨2枚は同じ金額を表す. よって,\ (1)と同様の方法では,\ 正しい場合の数は得られない. このような場合,\ 大きい金額の硬貨を小さい金額の硬貨に両替して考える}ことが有効である. 両替の考え方自体は問題集に載っているが,\ 両替で答えが求まる理由までは載っていないことが多い. それゆえ,\ ほとんどの学生は,\ 今一つ納得感を得られぬまま解法を丸暗記しているのが普通である. しかし,\ 丸暗記では思わぬ落とし穴にはまる可能性がある.\ 別解とその解説で理解を深めてほしい.  50円硬貨2枚を100円硬貨1枚に両替}する. すると,\ 100円硬貨2枚,\ 50円硬貨1枚,\ 10円硬貨2枚となる. 100円硬貨2枚の使い方は,\ 0\,~\,2枚の 3通り 0}50円硬貨1枚の使い方は,\ 0\,~\,1枚の 2通り 0}10円硬貨2枚の使い方は,\ 0\,~\,2枚の 3通り 本解とは逆に,\ 小さい金額の硬貨を大きい金額の硬貨に両替}して求めたものである. 実は,\ 小さい金額の硬貨から大きい金額の硬貨への両替は常に可能であるとは限らない.} ここで,\ (2)の50硬貨の枚数を1枚減らしたときの場合の数を求めてみよう. つまり,\ 「100円硬貨が1枚,\ 50円硬貨が2枚,\ 10円硬貨が2枚」のときの場合の数である. 本解の方法では,\ 50円硬貨4枚,\ 10円硬貨2枚となるから,\ 5・3-1=14\ (通り)\ である. 別解の方法では,\ 100円硬貨2枚,\ 10円硬貨2枚となるから,\ 3・3-1=8\ (通り)\ である. このように,\ 50円硬貨3枚のときは本解で別解で答えが一致するが,\ 2枚のときは一致しない.} まず,\ 100円硬貨1枚と50円硬貨3枚}で支払える金額を考える. 最大の250円まで,\ 50円,\ 100円,\ 150円,\ 200円,\ 250円と50円刻みで支払うことができる.} これは,\ 100円硬貨1枚を50円硬貨2枚に両替し,\ 50円硬貨5枚になっても変わらない. \scalebox{.94}[1]{さらに,\ 50円硬貨2枚を100円硬貨1枚に両替し,\ 100円硬貨2枚と50円硬貨1枚になっても変わらない. 次に,\ 100円硬貨1枚と50円硬貨2枚}で支払える金額を考える. 最大の200円まで,\ 50円,\ 100円,\ 150円,\ 200円と50円刻みで支払うことができる.} これは,\ 100円硬貨1枚を50円硬貨2枚に両替し,\ 50円硬貨4枚になっても変わらない. しかし,\ 50円硬貨2枚を100円硬貨1枚に両替し,\ 100円硬貨2枚にすると話が変わってくる. 50円硬貨が1枚もなくなってしまうため,\ 50円,\ 150円が支払えなくなる}のである. 以上から,\ 50円硬貨が残る場合にのみ,\ 100円硬貨に両替が可能}であることがわかる. $つまり,\ 小さい金額の刻み方が可能なだけ硬貨が残る場合のみ,\ 大きい金額の硬貨への両替が可能}である.$ 支払えなくなるリスクは,\ 大きい金額の硬貨を小さい金額の硬貨に両替する場合には生じ得ない.  100円硬貨1枚の使い方は,\ 0\,~\,1枚の 2通り 0}50円硬貨3枚の使い方は,\ 0\,~\,3枚の 4通り 0}10円硬貨2枚の使い方は,\ 0\,~\,2枚の 3通り $0円になる場合を除く}と,\ 異なる\dot{支}\dot{払}\dot{い}\dot{方}\dot{法は 2・4・3-1}=23\ (通り)$ 100円と150円には,\ それぞれ2通りの支払い方法がある. この2通りのいずれに対しても10円硬貨の使い方が3通りある. よって,\ 2通りの支払い方法がある金額}は\ $2×3=6$\ 通り}である. ∴ 異なる\dot{金}\dot{額は 23-6}=17\ (通り)}$} \\ 異なる硬貨を使う場合を異なる支払い方法とみなす. まず異なる支払い方法を場合の数を求め,\ 後から同じ金額になる場合の数を引く.} 参考までに示したが,\ 問題がより複雑になるとこの解法は難しい. 100円の支払い方法は,\ 100円硬貨1枚または50円硬貨2枚の2通りある. 150円の支払い方法は,\ 100円硬貨1枚,\ 50円硬貨1枚または50円硬貨3枚の2通りある. 10円硬貨2枚分も考慮すると,\ 110円,\ 120円,\ 160円,\ 170円の支払い方法も2通りある. 表から,\ 100円硬貨1枚と50円硬貨3枚で支払える金額は 6通り 10円硬貨2枚の使い方は,\ 0\,~\,2枚の 3通り 硬貨の枚数が少なく,\ 問題の構造が単純ならば,\ すべて書き出す最終手段}も有効である. 同じ金額になり得るのは100円硬貨と50円硬貨の使い方次第なので,\ 表で書き出してみればよい.  (3)\ \ 100円硬貨2枚を10円硬貨20枚,\ 50円硬貨1枚を10円硬貨5枚に両替}する. すると,\ 10円硬貨32枚となる. 10円硬貨32枚の使い方は,\ 0\,~\,32枚の 33通り 50円硬貨1枚と10円硬貨5枚が同じ金額を表すから,\ 50円硬貨1枚を10円硬貨5枚に両替する. すると,\ 100円硬貨2枚と10円硬貨12枚となる. さらに,\ 100円硬貨1枚と10円硬貨10枚が同じ金額を表す. よって,\ 100円硬貨2枚を10円硬貨20枚に両替することになる. なお,\ 10円硬貨5枚を50円硬貨1枚に両替することはできない.\ 理由は(2)で述べたとおりである. 50円硬貨1枚と10円硬貨7枚があるとき,\ 10円から120円までを10円刻みで支払える.} これは,\ 50円硬貨1枚を10円硬貨5枚に両替し,\ 50円硬貨12枚になっても変わらない. しかし,\ 10円硬貨5枚を50円硬貨1枚に両替し,\ 50円硬貨2枚と10円硬貨2枚では話が変わる. 10円硬貨が2枚しかないので,\ 30円,\ 40円,\ 80円,\ 90円が支払えなくなる.} 10円刻みでの支払いが可能なだけの硬貨が残る場合のみ,\ 50円硬貨への両替が可能}である. 50円まで10円刻みで支払うためには,\ 10円硬貨が4枚必要}である. よって,\ 50円硬貨1枚と10円硬貨9枚ならば,\ 50円硬貨2枚と10円硬貨4枚に両替できる. いずれの場合も,\ 140円まで10円刻みで支払うことができる.