4 実際の支払い時への応用

前節の最適解 (= 非冗長解) の構成法も、[1] とは かなり異なる方法であるが、実際にこれを支払いに使う方法について考えてみる。

[1] の最適解の構成法は、代金 $x$ と財布の小銭 $A$ を見て、 命題 8 のようにそれらを分解できる単位に分解して考え、 下の位の硬貨から最適な支払い方を構成していく、という方法であり、 比較的自然なものであった。

例えば、財布に 1324 円 (1000 円札 1 枚、100 円玉 3 枚、10 円玉 2 枚、 1 円玉 4 枚) あるとき、716 円を支払う場合は、1300 円で 700 円を、 24 円で 16 円を支払うように分割して考え、 700 円の方は 100 円玉 2 枚と 1000 円札 1 枚、 16 円の方は 1 円玉 1 枚と 10 円玉 2 枚、 と、結局 1221 円を支払えばよいわけである。

一方、命題 13 の証明の構成法は、 まず最終的な残金

$$(1324 円)\ - (716 円)\ =\ (608 円)$$ (1)

を求め、$B$ をこの 608 円の非冗長表現、$C$ を $A$ と $B$ の共通部分とする:

• $A$: 100 円玉 3 枚、10 円玉 2 枚、1 円玉 4 枚
• $B$: 500 円玉 1 枚、100 円玉 1 枚、5 円玉 1 枚、1 円玉 3 枚
• $C$: 100 円玉 1 枚、1 円玉 3 枚

元の $A$, $B$ からこの $C$ を除いたものが $A'$, $B'$ である:

• $A'$: 100 円玉 2 枚、10 円玉 2 枚、1 円玉 1 枚
• $B'$: 500 円玉 1 枚、5 円玉 1 枚

この $A'$ と 1000 円札を合わせて支払うのが非冗長解、 その際のおつりが $B'$ となる。

確かにこの支払い方は、前の最適解の支払い方に一致する。 しかし、(1) の引き算を暗算でやることはやや面倒だし、 さらに $B$ を求めて共通部分 $C$ を求め、それを $A$ から取り除く、 という計算を暗算でやるのはかなり難しそうである。

これを、多少暗算でもできそうな計算に改良してみる。 まず、(1) の引き算は、以下のようにすれば足し算に改良できる。

1. 代金を 1000 円から引き算する ($p$ 円とする)
2. それに $A$ を足し算する

この前者の引き算は、前の例では

$$(1000 円)\ - (716 円)\ =\ (284 円)$$

となって、これも少し面倒ではあるが、これは、

$$1000 - 716 = 1 + 999 - 716 = 1 + 283 = 284$$

と考えれば、それほど難しくはない (999 からの引き算は、 桁をまたぐ計算が発生しないので易しい)。

$p$ 円に $A$ を加えた金額が最終的に財布に残る金額となるので、 その冗長性を排除するように $A$ から小銭を出していく、 言い変えれば「両替」をしていく、と考えればよい。

例えば、例の場合は 284 円に 324 円を加えるわけであるが、 284 円をもらう際の冗長性を「両替」するように出していけばよい。 まず、324 円から 1 円玉を 1 枚出せば

$$(284 円)\ +\ (1 円)\ =\ (285 円)$$

となって、1 円玉の冗長性が解消される。 次に、手元に残った 323 円から 20 円を出せば

$$(285 円)\ +\ (20 円)\ =\ (305 円)$$

となって、10 円玉、50 円玉の冗長性が解消される。 さらに、手元の 303 円から 200 円をこれに追加すれば、

$$(305 円)\ +\ (200 円)\ =\ (505 円)$$

となり、100 円玉の冗長性が解消される。

これにより、1000 円札と 1 円玉 1 枚、10 円玉 2 枚、100 円玉 2 枚を出せば、 手元の 103 円とおつりの 505 円が残ることになり、 確かに非冗長解が得られる。

これは、引き算は多少楽になり、足し算で考えられるようになることが 多少のメリットであるが、 ただし慣れるまではかなり不安の残る方法だと思う。