6 札を使う場合

この節では、やはり当然と思われる次の命題を証明する。

命題 5.

代金が財布の中の小銭で払える額の場合は、 札を使う解よりも、より小銭を少なくするような 小銭のみの支払いでの解が必ず存在する。

これは、例えば、財布の中の小銭が 500 円玉 1 つと 1 円玉 1 つで、 代金が 496 円であった場合、

• 1000 円札 1 枚と 1 円の 1001 円を払っておつりを 505 円もらう $\rightarrow$ 小銭は 1 枚減って 2 枚増える
• 500 円玉 1 枚払っておつりを 4 円もらう $\rightarrow$ 小銭は 1 枚減って 4 枚増える

という例があるので、「常に」小銭で支払う方が小銭の枚数が減る、 ということではなく、 小銭で払う方が小銭の枚数が減るような小銭での支払い方が 「少なくとも 1 つは」存在する、という話である。 例えば上の例でも、501 円の支払いをすれば、小銭は 2 枚減って、 おつりは 5 円玉 1 枚であり、これが札を使う場合よりも小銭が減る 最適解になる。

この命題 5 の証明のために、 「極小解」という概念を導入する。 $x$ 円 ($0<x<M_c)$ の支払い $P (\ll H)$ が 極小解 であるとは、 $x$ の小銭表現 $X=F_M(x)$ に対して、次を満たすような $j_0 (>1)$ が 存在すること、と定義する:

$$\left\{\begin{array}{lll} j>j_0 & \mbox{ ならば } & n_j(P)... ...)+1,\\ j<j_0 & \mbox{ ならば } & n_j(P)=0 \end{array}\right.$$ (26)

なお、この $P$ が解であるためには、 $1\leq j<j_0$ で $n_j(X)>0$ であるような $j$ がなければならず、 そしてこの場合必ず $\mathrm{Tot}(R)>0$ になる。

また、この極小解は、$x$, $H$ に対して一意的ではない。 例えば、$x=120$ 円、$H$ が 500 円玉 1 つ、100 円玉 1 つ、50 円玉 1 つ (650 円) の場合、 500 円玉 1 つのみの支払いも極小解 $(j_0=500)$ だし、 100 円玉 1 つと 50 円玉 1 つの支払いも極小解 $(j_0=50)$ となるが、 500 円玉 1 つと 50 円玉 1 つの支払いは極小解ではない。

補題 6.

$\mathrm{Tot}(H)\geq x$ の場合、丁度支払える解か極小解のいずれかが必ず存在する。

証明 (補題 6)

$X=F_M(x)$ とする。このとき、 すべての $j\in K$ に対し $n_j(X)\leq n_j(H)$ であれば、 $X\ll H$ なので 丁度 $X$ を支払う解が存在する。

そうでない場合は、ある $j\in K$ に対して $n_j(X)>n_j(H)$ となるが、 そのような $j$ の一番大きいものを $j_a$ とすると、 $n_{j_a}(X)>n_{j_a}(H)$ で、 かつすべての $j>j_a$ に対して $n_j(X)\leq n_j(H)$ となる。

このとき、$j_b>j_a$ で $n_{j_b}(X)<n_{j_b}(H)$ となる $j_b$ が 少なくとも一つ存在する。 それは、もしそうでないとすると、 すべての $j>j_a$ で $n_j(X)=n_j(H)$ ということになるが、 それだと $n_{j_a}(X)>n_{j_a}(H)$ より $x>\mathrm{Tot}(H)$ となってしまうからである。

この $j_b$ を $j_0$ とすれば、 (26) を満たすような $P\ll H$ が作れることになる。

極小解は、ある意味では単純な支払い方法で、 必ずしもおつりの枚数を減らすことにはつながらないが、 命題 5 の証明には利用できる。

命題 5 よりも少し強い形の命題も紹介しよう。

命題 7.

小額の硬貨のみで払える場合、 高額の硬貨を使用した場合よりも、 高額の硬貨を使用せずに小銭をより少なくするような解が必ず存在する。

より詳しく述べると、$H$ の $j_n$ $(n<m)$ 以下の 硬貨のみからなるものを $\hat{H}$ とすると、 $\mathrm{Tot}(\hat{H})\geq x$ であるとき、 $\hat{H}\gg P$ ではない支払い $P (\ll H)$ とそのおつり $R$ に対して、

$$\mathrm{Num}(\hat{P}) - \mathrm{Num}(\hat{R}) > \mathrm{Num}(P) - \mathrm{Num}(R)$$ (27)

となるような支払い $\hat{P} (\ll \hat{H})$ と そのおつり $\hat{R}$ が存在する。

この命題 7 を用いれば 命題 5 を証明することは容易である。 すなわち、命題 5 の札 ($M_c$ 円札) を $M_c$ 円の硬貨だと思えば、 それは命題 7 そのものになり、 それにより (27) が言えれば、 $M_c$ 円の硬貨を元の札に戻せば、 (27) の右辺の $\mathrm{Num}(P)$ の硬貨は さらに 1 枚減ることになるから、 命題 5 が示されることになる。

よって、以下ではより強い命題 7 を証明する。

証明 (命題 7)

Step 1. まず $P$ が簡単な場合に帰着できることを示す。

$\mathrm{Tot}(\hat{H})$ の小銭で $x$ 円が丁度払える場合は、 系 4 よりそれが唯一の最適解であるので、 この場合はその解が (27) を満たす ことがわかる。

よって、以後は丁度は払えない場合を考えるが、 もし $j_n$ より大きな額の硬貨が複数 $P$ に含まれれば、 少なくとも一つ以外はおつりにも返されてしまうことになるので 仮定 5 に反する。よって、$j_n$ より大きな額の硬貨は 1 枚のみ $P$ に含まれることになる。

また、その硬貨は $j_{n+1}$ でかつ $n_{j_n}(X)>0$ である場合のみ 考えればよい。 それは、もしその硬貨 $j_k$ が $j_{n+1}$ より大きい額の硬貨である場合 ($k>n+1$) は、 $P$ の $j_k$ を $j_{n+1}$ で置き換えたものを $P'$ とすると、 $P$ で $X$ を払ったおつりは、 $P'$ で $X$ を払ったおつりに $j_k$ で $j_{n+1}$ を払った おつりを加えたものになるので、 払う枚数は両者で変わらないが、 もらうおつりは $P$ よりも $P'$ の方が少なくなる。 よって $P$ よりも $P'$ の方が小銭は確実に少なくなるので、 もし $P'$ に対してこの命題が成り立てば、 $P$ に対してもこの命題が成り立つことになる。

Step 2. $\hat{P}$ を構成するため、 小さい額の方を除いた金額の極小解 $P_2$ を作る。

$P$ から $j_{n+1}$ の硬貨 1 枚を取り除いたものを $P_1 (\ll\hat{H})$ とする。 もし $\mathrm{Tot}(P_1)\geq x$ だと $j_{n+1}$ の硬貨そのものがおつりとして 返却されてしまうことになるので、 $\mathrm{Tot}(P_1) < x$ でなければならない。

$\bar{x} = x - \mathrm{Tot}(P_1) (>0)$ とし、$P_1\ll\hat{H}$ より $\bar{H} = \hat{H}\mathrel{\ominus}P_1$ とすると、

$$\mathrm{Tot}(\bar{H}) = \mathrm{Tot}(\hat{H})-\mathrm{Tot}(P_1) \geq x - \mathrm{Tot}(P_1) = \bar{x}$$

となるが、 $j_{n+1}$ 円 + $P_1$ の $x$ 円の代金のおつりが $\mathrm{Tot}(R)$ 円で、 これは $j_{n+1}$ 円に $\bar{x}$ 円の代金のおつりと等しいので、 このおつりも $R$ となる。 よって、 $\bar{X} = F_M(\bar{x})$ とし、 $R$ の一番少額の硬貨を $j_s$ とすると、

$$\left\{\begin{array}{lll} j_s<j\leq j_n & \mbox{ならば} & ... ..., j>j_n & \mbox{ならば} & n_j(\bar{X}) = 0 \end{array}\right.$$ (28)

であることがわかる。

一方、もし $\bar{H}$ で $\bar{x}$ が丁度払えるとすると、 それに $\mathrm{Tot}(P_1)$ を合わせれば元の $x$ の丁度の解になってしまうので、 仮定より $\bar{H}$ で $\bar{x}$ を丁度払うことはできない。 よって、補題 6 により、 $\bar{H}$ 内で $\bar{x}$ の代金に対する極小解 $P_2$ と そのおつり $R_2$ が存在する ( $\mathrm{Tot}(P_2)>0$)。 極小解 $P_2$ の定義 (26) の $j_0 (\leq j_n)$ を 考えると、

$$\left\{\begin{array}{lll} j_0<j\leq j_n & \mbox{ならば} & ... ... j<j_0, j>j_n & \mbox{ならば} & n_j(P_2)=0 \end{array}\right.$$ (29)

であり、かつ $j<j_0$ で $n_j(\bar{X})>0$ となる $j$ が 少なくとも一つある。 よって、(28) より $j_s<j_0$ であることがわかる。

Step 3. $\bar{x}$ の代金に対して、 $j_{n+1}$ の支払いに対するおつり $R$ と、 $P_2$ の支払いに対するおつり $R_2$ との関係を考える。

今、 $y = j_{n+1} - \mathrm{Tot}(P_2) (>0)$, $Y = F_M(y)$ とすると、

$$\mathrm{Tot}(Y) + \mathrm{Tot}(R_2) = j_{n+1} - \mathrm{T... ...) + \mathrm{Tot}(R_2) = j_{n+1} - \bar{x} = \mathrm{Tot}(R)$$

であり、$n_j(Y)$ は、$j<j_0$ では $n_j(Y)=0$, $j=j_0$ では、(28), (29)より、

$$\begin{eqnarray*}n_j(Y) &=& N_j - n_j(P_2) = N_j - n_j(\bar{X}) - 1 = N_j - (N_j - n_j(R) - 1) - 1 &=& n_j(R) \end{eqnarray*}$$

$j_0<j\leq j_n$ では、

$$\begin{eqnarray*}n_j(Y) &=& N_j - n_j(P_2) - 1 = N_j - n_j(\bar{X}) - 1 = N_j - (N_j - n_j(R) - 1) - 1 &=& n_j(R) \end{eqnarray*}$$

なので、結局、

$$j_0\leq j\leq j_n \mbox{ ならば } n_j(Y)=n_j(R), \hspace{0.5zw}j<j_0, j>j_n \mbox{ ならば } n_j(Y)=0$$

となり、よって $Y\ll R$ であることがわかる。

$$\mathrm{Tot}(R) - \mathrm{Tot}(Y) = j_{n+1} - \bar{x} - (... ...ot}(P_2)) = \mathrm{Tot}(P_2) - \bar{x} = \mathrm{Tot}(R_2)$$

なので、よって $R_2\ll R$ であり、 $y>0$ より $\mathrm{Num}(Y)>0$ で、

$$R_2 = R\mathrel{\ominus}Y, \hspace{0.5zw}\mathrm{Num}(R_2) = \mathrm{Num}(R) - \mathrm{Num}(Y)$$ (30)

となることがわかる。

Step 4. 最後に $\hat{P}$, $\hat{R}$ を構成する。

さて、 $P_3 = P_1\mathrel{\oplus}P_2$ とすると、 $\bar{H}=\hat{H}\mathrel{\ominus}P_1\gg P_2$ より $P_3\ll\hat{H}$ で、

$$\mathrm{Num}(P_3) = \mathrm{Num}(P_1)+\mathrm{Num}(P_2)$$ (31)

となる。

$$\mathrm{Tot}(P_3) - x = \mathrm{Tot}(P_1) + \mathrm{Tot}(P... ...ot}(P_1)) = \mathrm{Tot}(P_2) - \bar{x} = \mathrm{Tot}(R_2)$$

なので、$P_3$ で $x$ を支払うおつりは $R_2$ になる。 ただし、$P_3$ には $P_1$ も含まれていて、 そこに $R_2$ と共通の硬貨が含まれる可能性も考慮し、 $P_3$ と $R_2$ から共通の硬貨 $B = P_3\mathrel{\wedge}R_2$ を取り除く。 $B$ は $B\ll P_3$, $B\ll R_2$ で、 $\hat{P} = P_3\mathrel{\ominus}B$, $\hat{R} = R_2\mathrel{\ominus}B$ とすれば、 $\hat{P}\mathrel{・}\hat{R} = 0$ となり、 $\hat{P}\ll P_3\ll\hat{H}$ で、

$$\begin{eqnarray*}\lefteqn{\mathrm{Num}(\hat{P}) - \mathrm{Num}(\hat{R}) = (\m... ...mathrm{Num}(B))} &=& \mathrm{Num}(P_3) - \mathrm{Num}(R_2) \end{eqnarray*}$$

となる。

よって、$\hat{P}$ で $x$ を支払ったおつりは $\hat{R}$ で、 (30), (31) より

$$\begin{eqnarray*}\lefteqn{\mathrm{Num}(\hat{P}) - \mathrm{Num}(\hat{R}) = \mat... ...P)-\mathrm{Num}(R)) + (\mathrm{Num}(P_2) + \mathrm{Num}(Y) - 1) \end{eqnarray*}$$

となるが、 $\mathrm{Num}(P_2)>0$, $\mathrm{Num}(Y)>0$ より、

$$\mathrm{Num}(\hat{P}) - \mathrm{Num}(\hat{R}) \geq \mathrm{Num}(P)-\mathrm{Num}(R) +1$$ (32)

となり、よって $\hat{P}$, $\hat{R}$ により (27) が成り立つことになる。

証明がだいぶ長くてわかりにくいかもしれないが、 $j_{n+1}=500$ 円、$\hat{H}$ が 372 円、$x=247$ 円、 $P$ が 552 円の例で考えると、 $R$ は $552-247=305$ 円、 $P_1$ は $552-500=52$ 円、 $\bar{x}$ と $\bar{H}$ は $x$ と $H$ からこの $P_1$ の 52 円を除いて、 $\bar{x}=247-52=195$ 円、$\bar{H}$ は $372-52=320$ 円となる。

$P_2$ は $\bar{H}$ での $\bar{x}$ に対する極小解なので、 この場合は必然的に 200 円となり、おつり $R_2$ は 5 円、 $Y$ は $500-200=300$ 円となる。 よって $P_3$ は $52 + 200 = 252$ 円で、 これは $R_2$ とは交わらないので、$B$ は 0 円、 $\hat{P}=P_3$ で 252 円、$\hat{R}=R_2$ で 5 円となる。

この場合、 $\mathrm{Num}(P)-\mathrm{Num}(R)=4-4=0$、 $\mathrm{Num}(\hat{P})-\mathrm{Num}(\hat{R})=5-1=4$ であるが、 その差 4 は $\mathrm{Num}(P_2)+\mathrm{Num}(Y)-1 = 2 + 3 - 1$ に 等しくなっていることが確認できる。

なお、一般に $B$ が 0 であることが証明できるのか、 それとも $B$ が正の金額となるような例があるのかはよくわからないが、 それは上の命題の証明には直接影響はない。