硬貨の枚数
[問題2]
5
円,10円,100円硬貨が、いずれも各1枚以上でb枚あり、合計金額はa円である。
各硬貨の枚数は何枚か求めよ。
[解答]
5円,10円,100円硬貨をそれぞれ、x,y,z枚とする。題意より
$$5x+10y+100z=a\cdots(1)$$
$$x+y+z=b\cdots(2)$$ $$(1)より、a=5(x+2y+20z)だから$$
$$a\equiv 0
(\mod 5)$$ $$\hspace{2.0cm}(1)\div
5\hspace{1.0cm}x+2y+20z=\dfrac{a}{5}\cdots(3)$$
$$\hspace{2.0cm}(3)-(2)\hspace{1.0cm}y+19z=\dfrac{a}{5}-b$$
$$\hspace{4.0cm}19z=\dfrac{a}{5}-b-y$$
これより
$$\left(\dfrac{a}{5}-b-y\right)\equiv
0(\mod 19) $$ $$ゆえに、 \left(\dfrac{a}{5}-b\right)\equiv
y (\mod 19) $$
$$1<=x,1<=y,1<=zと(2)から、y<=b-2としてよい。$$
$$(ここで、\mod n とはある整数をnで割ったときの余りのこと。)$$
要するにこの場合、
合計金額÷5
と硬貨枚数の差を19で割った余りと、
１０円硬貨の枚数を19で割った余りが一致するものをさがせという話になる。
実際には、
$$\left(\dfrac{a}{5}-b\right) (\mod
19)の値をあらかじめ求めておき$$ $$y <b-2だから、y=(b-3),(b-4),\cdots
,2,1のうち$$
$$y(\mod 19)が上で求めたものと一致
するものについて、次のように計算すればよい。$$
(1),(2)式から、 $$x=\frac{ \left
| \begin{array}{cc} a-10y & 100 \\ b-y & 1
\end{array} \right | } { \left | \begin{array}{cc} 5
& 100 \\ 1 & 1 \end{array} \right | } ,
z=\frac{ \left | \begin{array}{cc} 5 & a-10y \\ 1
& b-y \end{array} \right | } { \left |
\begin{array}{cc} 5 & 100 \\ 1 & 1 \end{array}
\right | }$$ となるので $$x=-\dfrac{a-100b+90y}{95}\ ,\
z=-\dfrac{5b-a+5y}{95}$$
[例]
$$a=1000,b=36
の場合\dfrac{a}{5}-b=200-36=164 \equiv 12(\mod
19)となるので$$$$y<34より、解となるものは、y=12,y=31であるから、これについて計算すればよい。$$
y=12 のとき、 $$x=-\dfrac{1000-100\times
36+90\times 12}{95}=-\dfrac{-1520}{95}=16$$
$$z=-\dfrac{5\times
36-1000+5\times12}{95}=-\dfrac{-760}{95}=8$$
y=31のとき、
$$x=-\dfrac{1000-100\times 36+90\times
31}{95}=-\dfrac{190}{95}=-2$$ $$z=-\dfrac{5\times
36-1000+5\times 31}{95}=-\dfrac{-665}{95}=7$$
$$となるが、x<0だから、これは問題に合わない。$$ [答]5円16枚,10円12
枚,100円8枚
