支払い金種問題

Copyright (C) virtual_high_school, 1996-2018

一見すると樹形図を使わなくては解けないようだが、よく考えると樹形図を使わない方が数学的構造が見やすくなっていい問題がある。

【問題1】
$1$円玉、$5$円玉、$10$円玉を使って$100$円を支払う方法は何通りあるか。---

(解１)
高額の金種から考える。10円玉を
　　　10枚、9枚、8枚、…、1枚、0枚
だけ支払ったら、5円玉の支払い方法はそれぞれ
　　　0枚の1通り、
　　　0,1,2枚の3通り、
　　　0,1,2,3,4枚の5通り、
　　　…………
　　　0,1,2,…,20枚の21通り
だけある。1円玉の支払い方法は自動的に決まるので考える必要はない。
結局、求める答は奇数の和の公式から
　　　$1+3+5+ \cdots +21=(\frac{1+21}{2})^{2}=121$通り■

(解２)
$10k (0 \leq k \leq 10)$円を1円玉、5円玉で払う方法の数$m(k)$を求めると、5円玉の個数が
　　　$ 0, 1, 2, \cdots, 2k(=10k/5) $
の$2k+1$通りであるので、$m(k)=2k+1$である。$k$がすべての場合をわたれば
　　　$ \displaystyle \sum_{k=0}^{10} m(k) =\displaystyle \sum_{k=0}^{10} (2k+1) = 2 \times 55 + 11 = 121 $
で121通りである。■

これは数列の和の公式を使う問題なのであった。コインの種類を増やしてみる。

【問題2】
$1$円、$5$円、$10$円、$50$円の$4$種類のコインを使って$500$円を支払う方法は何通りあるか。---

(解)
まず、$50l (0 \leq l \leq 10) $円を1円、5円、10円の3種類だけで払う方法を考える。
前問の解答を真似て
　　　$ n(l) = \displaystyle \sum_{k=0}^{5 l} (2 k+1) = 2 \times \frac{5l(5l+1)}{2} + (5l +1) = 25 l^{2} + 10 l +1 $
($\sum$の上端は$50l \div 10=5l$から)となる。
最後に、一番大きな金種の50円玉の枚数を考える。$l$が$0 \leq l \leq 10$をわたればよいので、
　　　$ \displaystyle \sum_{l=0}^{10} n(l) = \displaystyle \sum_{l=0}^{10} (25 l^{2} + 10 l +1) = 25 \times 385 + 10 \times 55 + 11 = 10186 $
通りである。■