7 上位と下位の分解

代金と財布の中身の両方に対して、 ある硬貨以下の部分だけを見たときに、 そこは上の額の硬貨を借りずに払える場合は、 そこで上位と下位に分離して考えて良いことを次に示す。

そのために、ある額以上の硬貨と以下の硬貨に分離するための記号を 導入する。

$n<m$ に対して $Y_n^+, Y_n^-\in U_1$ を、

$$n_j(Y_n^+) = \left\{\begin{array}{ll} N_j - 1 & (j \geq j_n... ...l} 0 & (j > j_n),\\ N_j - 1 & (j \leq j_n)\end{array}\right.$$

とすると、$A\in U_1$ に対して、 $A$ の $j_{n+1}$ 以上の硬貨の部分 $A^+$, $A$ の $j_n$ 以下の硬貨の部分 $A^-$ は、それぞれ

$$A^+ = A\mathrel{\wedge}Y_{n+1}^+, \hspace{1zw}A^- = A\mathrel{\wedge}Y_n^-$$

のように書くことができることになる。

命題 8.

$\mathrm{Tot}(H) \geq x (>0)$, $X=F_M(x)$ を $j_n$ $(0<n<m)$ より大きいか それ以下かで上位、下位に分け、

$$H^+ =H\mathrel{\wedge}Y_{n+1}^+, \hspace{0.5zw}H^- =H\math... ...{\wedge}Y_{n+1}^+, \hspace{0.5zw}X^- =X\mathrel{\wedge}Y_n^-$$

とするとき、

1. $\mathrm{Tot}(H^-)\geq \mathrm{Tot}(X^-)$ ならば $\mathrm{Tot}(H^+)\geq \mathrm{Tot}(X^+)$ で なくてはならない。
2. $\mathrm{Tot}(H^-)\geq \mathrm{Tot}(X^-)$ の場合、 $X^{\pm}$ に対する $H^{\pm}$ での最適解 $P^{\pm}$ とそのおつり $R^{\pm}$ に より、$X$ の $H$ での最適解 $P$, $R$ は、 $P=P^-\mathrel{\oplus}P^+$, $R=R^-\mathrel{\oplus}R^+$ により得られる。

これは、例えば $H$ が 772 円で、代金 $x$ がそれで払える額である場合、 1. は 100 円未満の部分が 72 円で払えるならば、100 円以上の方も、 その 72 円の残りを使わなくても 700 円で払えるはずだ、ということを意味し、 よってこちらの証明は易しい。

また 2. は、その場合最適な支払いは、 72 円での 100 円未満の最適化と、 700 円での 100 円台の最適化に分けて考えればいいことを意味している。

証明

1. もし $\mathrm{Tot}(H^+) < \mathrm{Tot}(X^+)$ ならば、 少なくとも $\mathrm{Tot}(X^+) \geq \mathrm{Tot}(H^+) + j_{n+1}$ であるが、 この硬貨系では $\mathrm{Tot}(H^-) < j_{n+1}$ であるので、

$$\mathrm{Tot}(H) = \mathrm{Tot}(H^+)+\mathrm{Tot}(H^-) < \mathrm{Tot}(X^+)-j_{n+1} + j_{n+1} \leq \mathrm{Tot}(X)$$

すなわち $\mathrm{Tot}(H)<x$ となり仮定に反する。

2. もし、$P$, $R$ が最適解でないとすると、 これとは別に最適解 $P_3$ とそのおつり $R_3$ があり、

$$\mathrm{Num}(P_3)-\mathrm{Num}(R_3) > \mathrm{Num}(P)-\mathrm{Num}(R)$$ (33)

となるはずである。このように仮定して矛盾を示す。

なお、命題 5 より、$P_3$ はお札は不要のはずで、 よって $P_3\ll H$ である。 以下、2 つの場合に分けて考える。

Step 1. まず $P_3$ の下位部分で $X^-$ が払える場合を考える。

$P_3$, $R_3$ を上位、下位に分け、

$$P_3^+ =P_3\mathrel{\wedge}Y_{n+1}^+, \hspace{0.5zw}P_3^- =... ...dge}Y_{n+1}^+, \hspace{0.5zw}R_3^- =R_3\mathrel{\wedge}Y_n^-$$

とする。

$\mathrm{Tot}(P_3)\geq x$ であるから、 $\mathrm{Tot}(P_3^-)\geq \mathrm{Tot}(X^-)$ の場合は、 命題 8 の 1. により $\mathrm{Tot}(P_3^+)\geq \mathrm{Tot}(X^+)$ となる。 よって、$P_3^{\pm}$ の $X^{\pm}$ に対するおつりが $R_3^{\pm}$ となり、 これに関しては $X^{\pm}$ の最適解は $P^{\pm}$, $R^{\pm}$ なので、

$$\mathrm{Num}(P^{\pm})-\mathrm{Num}(R^{\pm}) \geq \mathrm{Num}(P_3^{\pm})-\mathrm{Num}(R_3^{\pm})$$

となるはずであり、よって上位、下位の式を辺々加えれば

$$\mathrm{Num}(P)-\mathrm{Num}(R)\geq \mathrm{Num}(P_3)-\mathrm{Num}(R_3)$$

となり、(33) に反する。

Step 2. 次に $\mathrm{Tot}(P_3^-)<\mathrm{Tot}(X^-)$ の場合を考える。

この場合は、 $\mathrm{Tot}(P_3^+)=\mathrm{Tot}(X^+)$ では $\mathrm{Tot}(P_3)\geq x$ とならないので、よって少なくとも $\mathrm{Tot}(P_3^+)\geq \mathrm{Tot}(X^+)+j_{n+1}$ であることになる。

この場合、$P_3$ で $X$ を支払ったおつり $R_3$ は、 $P_3^+$ で $X^+$ を払ったおつり $R_4^+$ に $P_3^-$ を加えて、 そこから $X^{-}$ を払ったおつりに等しい。 よって、その上位部分である $R_3^+$ は、$R_4^+$ から $j_{n+1}$ を 引いたものであり、

$$R_3^{+} = F_M(\mathrm{Tot}(R_4^{+})-j_{n+1}) = F_M(\math... ...P_3^{+})-\mathrm{Tot}(X^{+})-j_{n+1}) \hspace{0.5zw}(\geq 0)$$ (34)

に等しく、$R_3^-$ は、$j_{n+1}$ と $P_3^{-}$ の和 $P_4^- = F_M(j_{n+1})\mathrel{\oplus}P_3^-$ から $X^-$ を 払ったおつりに等しい:

$$R_3^- = F_M(\mathrm{Tot}(P_4^-)-\mathrm{Tot}(X^-)) = F_M(j... ...+ \mathrm{Tot}(P_3^-)-\mathrm{Tot}(X^-)) \hspace{0.5zw}(> 0)$$ (35)

この場合、まず上位の $X^+$ に対しては、$P^+$, $R^+$ が最適解なので、

$$\mathrm{Num}(P^+)-\mathrm{Num}(R^+)\geq \mathrm{Num}(P_3^+)-\mathrm{Num}(R_4^+)$$ (36)

である。また、(34) より

$$\mathrm{Tot}(R_3^+\mathrel{\oplus}F_M(j_{n+1}))=\mathrm{Tot}(R_4^{+})$$

であるから、命題 2 より

$$\mathrm{Num}(R_3^+\mathrel{\oplus}F_M(j_{n+1})) = \mathrm{Num}(R_3^+) + 1 \geq \mathrm{Num}(R_4^+)$$ (37)

となる。

最後に $R_3^-$ であるが、これは $P_3^-$ に $j_{n+1}$ という上位の 硬貨を追加して代金を払ったおつりが $R_3^-$ なので、 命題 7 (式 (32)) により、 最適解 $P^-$, $R^-$ との枚数の間には、

$$\mathrm{Num}(P^-) - \mathrm{Num}(R^-) \geq \mathrm{Num}(F_M(j_{n+1})\mathrel{\oplus}P_3^-) - \mathrm{Num}(R_3^-) + 1$$

$$= \mathrm{Num}(P_3^-) - \mathrm{Num}(R_3^-) + 2$$ (38)

という不等式が成り立つ。

結局、 (36), (37), (38) の辺々をそれぞれ加えて整理すると、

$$\mathrm{Num}(P)-\mathrm{Num}(R)\geq \mathrm{Num}(P_3)-\mathrm{Num}(R_3)+1$$ (39)

となり、よって (33) に反する。