次へ: 6 札を使う場合 上へ: 財布の中の小銭の最適化について 前へ: 4 硬貨系 (PDF ファイル: kozeni1.pdf)


5 基本的な事実

この節では、硬貨系の支払いとおつり等に関する 基本的な事実をいくつか取り上げていく。

命題 2.
$A\in U_0$, $B\in U_1$ が $\mathrm{Tot}(A) = \mathrm{Tot}(B)$ であれば、 $\mathrm{Num}(A)\geq \mathrm{Num}(B)$ となる。 さらに、この等号が成り立つのは $A=B$ のときのみである。
これは、同じ額では、$A$ のように仮定 3 を満たさない 硬貨の集まりよりも、仮定 3 を満たす集まりの方が 硬貨の枚数は少なくなることを意味する。

例えば、同じ 552 円を表す組は、 $U_0$ でなら 10 円玉 5 枚以上も使えるし、 100 円玉も 5 枚以上使えるので色々あるが、 その枚数が最小になるのは、 $U_1$ の 500 円玉 1 枚、50 円玉 1 枚、1 円玉 2 枚、 になることを意味する。

命題 2 の一般の場合を証明する前に、 簡単な例として 1 円玉、5 円玉、10 円玉の 3 種類だけの場合を考える。 この場合命題 2 は、

    $\displaystyle a + 5b + 10c = a' + 5b' + 10c',$ (13)
    $\displaystyle (a\geq 0, b\geq 0, c\geq 0, 0\leq a'< 5, 0\leq b'< 1, 0\leq c'< 5)$  

のときに、
\begin{displaymath} a + b + c \geq a' + b' + c'\end{displaymath} (14)

であることを意味する。

(13) を 5 で割った余りを考えれば、

\begin{displaymath} a \equiv a' (\mathrm{mod} 5) \end{displaymath}

となり、$a\geq 0$, $0\leq a'<5$ より
\begin{displaymath} a=a'+5r_1\end{displaymath} (15)

となる 0 以上の整数 $r_1$ が存在することになる。 これは、すなわち $a$ のうち $5r_1$ 円分の 1 円玉は $r_1$ 個の 5 円玉で置きかえられることを意味する。

(15) を (13) に代入して整理すれば、

\begin{displaymath} a'+5r_1 + 5b + 10c = a' + 5b' + 10c', \hspace{1zw}r_1 + b + 2c = b' + 2c' \end{displaymath}

となるので、最後の式を 2 で割った余りで考えれば、上と同様にして
\begin{displaymath} r_1 + b \equiv b' (\mathrm{mod} 2) \end{displaymath}

より
\begin{displaymath} r_1 + b= b' + 2r_2\end{displaymath} (16)

となる 0 以上の整数 $r_2$ が存在する。 これは、$b$ 個の 5 円玉と、$r_1$ 個の 5 円玉分の 1 円玉の集まりのうち、 $5\times 2r_2$ 円分は $r_2$ 個の 10 円玉で置きかえられることを意味する。

(16) を上の式に代入すれば、

\begin{displaymath} b' + 2r_2 + 2c = b' + 2c' \end{displaymath}

より
\begin{displaymath} r_2 + c = c'\end{displaymath} (17)

となる。 これは、$c$ 個の 10 円玉と $r_2$ 個の 10 円玉分の下からの繰り上がりが $c'$ 個の 10 円玉に等しいことを意味する。

(15), (16), (17) を辺々加えると、

\begin{displaymath} r_1 + r_2 + a + b + c = a' + b' + c' + 5r_1 + 2r_2 \end{displaymath}

となるので、
\begin{displaymath} a + b + c = a' + b' + c' + 4r_1 + r_2 \geq a' + b' + c' \end{displaymath}

であることがわかる。しかも、等号が成り立つのは $r_1=r_2=0$ の ときであるから、 (15), (16), (17) より $a=a'$, $b=b'$, $c=c'$ のときであることがわかる。

一般の場合も、これと同様の考察を行えば、 命題 2 が証明できる。

証明 (命題 2)

$\mathrm{Tot}(A) = \mathrm{Tot}(B)$ より

\begin{displaymath} \sum_{k=1}^m n_{j_k}(A)\cdot j_k = \sum_{k=1}^m n_{j_k}(B... ... \hspace{1zw}(n_{j_k}(A)\geq 0, 0\leq n_{j_k}(B) < N_{j_k}) \end{displaymath} (18)

(10) より、$j_2 = N_{j_1}$ で割った余りを考えると、
\begin{displaymath} n_{j_1}(A) \equiv n_{j_1}(B) (\mathrm{mod} N_{j_1}) \end{displaymath}

より、
\begin{displaymath} n_{j_1}(A)=n_{j_1}(B) + r_1N_{j_1} \end{displaymath} (19)

となる 0 以上の整数 $r_1$ が存在する。 これを (18) に代入し、 両辺から $n_{j_1}(B)$ を引き、$N_{j_1}$ で割ると、 (12) より
\begin{displaymath} r_1 + n_{j_2}(A) + N_{j_2}(\ldots) = n_{j_2}(B) + N_{j_2}(\ldots) \end{displaymath}

のような形になるので、これを $N_{j_2}$ で割った余りを考えると、
\begin{displaymath} r_1 + n_{j_2}(A) \equiv n_{j_2}(B) (\mathrm{mod} N_{j_2}) \end{displaymath}

なので、
\begin{displaymath} r_1 + n_{j_2}(A) = n_{j_2}(B) + r_2N_{j_2} \end{displaymath}

となる 0 以上の整数 $r_2$ が存在する。 この作業を繰り返すと、結局 $2\leq k<m$ の $k$ に対し
\begin{displaymath} r_{k-1} + n_{j_k}(A) = n_{j_k}(B) + r_kN_{j_k} \end{displaymath} (20)

となるような 0 以上の整数 $r_k$ が存在し、さらに
\begin{displaymath} r_{m-1} + n_{j_m}(A) = n_{j_m}(B) \end{displaymath} (21)

となる。

(19), (20), (21) を辺々加えると、

\begin{displaymath} \sum_{k=1}^{m-1}r_k + \sum_{k=1}^m n_{j_k}(A) = \sum_{k=1}^m n_{j_k}(B) + \sum_{k=1}^{m-1}r_k N_{j_k} \end{displaymath}

となるので、よって
\begin{displaymath} \mathrm{Num}(A) = \mathrm{Num}(B) + \sum_{k=1}^{m-1}r_k (N_{j_k}-1) \end{displaymath} (22)

となるので、 $\mathrm{Num}(A)\geq \mathrm{Num}(B)$ が成り立つ。

さらに、 $\mathrm{Num}(A)=\mathrm{Num}(B)$ となるのは、 $N_{j_k}\geq 2$ よりすべての $r_k$ が 0 になることと同値で、 それは、 (19), (20), (21) より すべての $j$ に対して $n_j(A) = n_j(B)$ であることと同じ、 すなわち $A=B$ と同じであることがわかる。

以後、主に $H\in U_1$ を財布の小銭全部、$x>0$ を代金、 $P\in U_1$ を支払う小銭 (必要な場合はこれに $M_c$ 円の額のお札を 追加する場合もある)、$R\in U_1$ をおつりの小銭、とする。

$P$ と $R$ は仮定 5 を満たさなければいけないので、 各硬貨成分 $n_{j}$ に対して、 $n_{j}(P)$ と $n_{j}(R)$ のいずれかが必ず 0 でなければならない。 すなわち、すべての $j\in K$ に対して $n_{j}(P)n_{j}(R) = 0$ となるので、 通常のベクトルと同じように内積を

\begin{displaymath} A\mathrel{・}B = \sum_{j\in K}n_j(A)n_j(B)\end{displaymath} (23)

と定めると、この仮定 5 の条件は、 簡単に $P\mathrel{・}R=0$ と書くことができる。

逆に、$P$, $R$ が

\begin{displaymath} P,R\in U_1, \hspace{0.5zw}\mathrm{Tot}(P)>\mathrm{Tot}(R), \hspace{0.5zw}P\mathrel{・}R=0\end{displaymath} (24)

を満たしているとき、 $y=\mathrm{Tot}(P)-\mathrm{Tot}(R)$ とすると、 $R$ は代金 $y$ に対して $P$ を支払ったおつりと見ることができる。 実際、$R\in U_1$ より $R$ は仮定 4 を満たすし、 $P\mathrel{・}R=0$ より仮定 5 も満たされていて、 金額的にも適合する。 すなわち、支払いとおつりは (24) の関係を満たすことが 互いの条件であることがわかる。

命題 3.
$x (<M_c)$ が代金、$P (\in U_1)$ が支払い、 $R (\in U_1)$ がおつりの場合、 $X=F_M(x)$ とすると、
\begin{displaymath} \mathrm{Num}(X)\geq \mathrm{Num}(P)-\mathrm{Num}(R) \end{displaymath} (25)

が成り立つ。等号成立は $\mathrm{Tot}(R)=0$ のときで、かつこのときに限る。
これは例えば、代金が 72 円で、支払いが 122 円、 おつりが 50 円の場合を考えると、 $\mathrm{Num}(X)$ は 50 円玉 1 枚、10 円玉 2 枚、1 円玉 2 枚より 5 枚、 $\mathrm{Num}(P)$ は 100 円玉 1 枚、10 円玉 2 枚、1 円玉 2 枚より 5 枚、 $\mathrm{Num}(R)$ は 50 円玉 1 枚なので、
\begin{displaymath} \mathrm{Num}(X)=5,\hspace{1zw}\mathrm{Num}(P)-\mathrm{Num}(R) = 5-1 = 4 \end{displaymath}

となり、(25) が成り立つ。

この命題 3 からすぐに次の系が得られる。

系 4.
丁度の代金を払える場合はそれが最適解であり、それは一意的である。 すなわち、おつりをもらう場合は、 丁度の代金の場合の小銭の枚数よりも 必ず減らせる小銭の枚数は少なくなる。

命題 3 は、命題 2 から容易に 示されるが、その証明のため、次の記号を導入する:

\begin{displaymath} \begin{array}{lll} \displaystyle A\mathrel{\oplus}B & = (n_... ...(\min\{n_{j_k}(A), n_{j_k}(B)\})_k & (A, B\in U_0) \end{array}\end{displaymath}

証明 (命題 3)

$X\mathrel{\oplus}R\in U_0$ の定義から明らかに、

\begin{displaymath} \mathrm{Tot}(X\mathrel{\oplus}R) = \mathrm{Tot}(X) + \mathrm{Tot}(R) = x + \mathrm{Tot}(R) = \mathrm{Tot}(P) \end{displaymath}

であるから、命題 2 より、 $\mathrm{Num}(X\mathrel{\oplus}R)\geq \mathrm{Num}(P)$ となるが、 定義より明らかに $\mathrm{Num}(X\mathrel{\oplus}R) = \mathrm{Num}(X) + \mathrm{Num}(R)$ なので、
\begin{displaymath} \mathrm{Num}(X)+\mathrm{Num}(R) \geq \mathrm{Num}(P) \end{displaymath}

となり、(25) が成り立つ。

また、等号が成り立つのは、 命題 2 より $X\mathrel{\oplus}R=P$ となる場合であるが、 (24) より $P\mathrel{・}R=0$ でなければいけないので、 $R$ の成分はすべて 0 でなければならない。よって、 $\mathrm{Tot}(R)=0$ となる。

逆に $\mathrm{Tot}(R)=0$、すなわちおつりがなければ、もちろん等号となる。

次へ: 6 札を使う場合 上へ: 財布の中の小銭の最適化について 前へ: 4 硬貨系
竹野茂治＠新潟工科大学
2014年11月19日