1. はじめに

1
2017 年 12 月 20 日

財布の小銭の最適化その 2
新潟工科大学 情報電子工学科 竹野茂治

1

はじめに

以前、[1] で、財布の中の小銭をできるだけ減らすにはどのように支払えばよいかを数学的な証明をつけて考察した。
その際は、どのように支払えばよいかを「表側」から考察したが、逆におつりと合わせて財布に残る側から考えることで、前回の考察を簡略化できる部分があることに気がついた。それをここにまとめておく。

2

設定

問題の設定として、[1] と同じ、以下のものを仮定する。

• 仮定 1: 目標は、代金の支払いで、おつりの枚数を減らすことではなく、最終的に財布に残る小銭の枚数をなるべく少なくすること。
• 仮定 2: お札の枚数は考慮しないし、代金を払うには十分なお札も持っている。
• 仮定 3: 代金を支払う前の財布の中には無駄な小銭はない。すなわち、(日本の硬貨系では) 1 円、10 円、100 円硬貨はそれぞれ最大で 4 枚まで、5 円、50 円、500円硬貨はそれぞれ最大で 1 枚しかない。
• 仮定 4: おつりを返す店側には、すべての種類の硬貨が十分な枚数揃っていて、店員は枚数が最も少なくなるようにおつりを返す。
• 仮定 5: 支払う硬貨の一部が、そのままおつりの一部として戻ってくる払い方はしない。
なお、考える硬貨系は、[1] と同じ、一般化した硬貨系とする。すなわち、

j1 = 1 < j2 < · · · < jm

3. 主要命題の易しい証明

2の額の硬貨が、Njk ≥ 2 (1 ≤ k ≤ m) に対して

jk =

k−1
∏

Nji(k ≥ 2)

i=1を満たし、札の金額 Mc はMc =m∏

Njii=1であるとする。この場合各硬貨 jk の必要枚数は Njk − 1 枚で、それに対して、[1] の命題 1, 2 が成り立つ。

命題 1. ([1])
この硬貨系では、各硬貨の必要枚数以内で Mc 未満の金額はすべて表現でき、そしてそのような表現は一意的である。

命題 2. ([1])
必要枚数以内という制限を外して考えた場合、Mc 未満の金額の表現は、常に必要枚数以内の表現が枚数は最小となり、その最小を与える表現は一意的に決定する。

この命題 1, 2 は、この硬貨系の基本的な命題であり、本稿では中心的な役割を果たす。
命題 1 の証明はそれほど長くはないし難しくもない ([1] 参照)。命題 2 も、必要枚数を越えている表現は両替してより少ない枚数の表現に変換できることを考えれば、命題 1 から導くのは難しくはない。
なお、今後この硬貨系の必要枚数以下の小銭しかない状態を、「冗長性がない」と呼ぶことにする。

3

主要命題の易しい証明

本節で、[1] の中心的な命題である命題 11 の易しい証明を紹介する。命題 11 は以下の通り。

3. 主要命題の易しい証明

3

命題 11. ([1])
代金に対する最適解、すなわち最終的に財布に残る小銭の枚数を最小にするような支払い方は一意的に決まり、それ以外の支払い方では財布の小銭は最適解よりも必ず多くなる。

この命題 11 は、そのような支払い方 (最適解) が一意的であることの保証であり、最適解が存在することを直接は保証はしていないが、[1] では命題 3 から命題 10 にかけて最適解の構成の考察を行っていて、実際には最適解の存在も (しかもその解の構成法も) 示している。
本稿では、この命題 11 を、命題 1 を用いて「逆」から考える。まず、「非冗長解」を、「財布に残る小銭に冗長性がないような支払い方」と定義する。これは、最適解の定義とは異なるが、のちにこれが最適解と一致するものであることが示される (命題 13)。
なお、命題番号は、[1] とぶつからないように、続きの番号から始める。

命題 12.

非冗長解が存在すれば、それは最適解となる。

証明支払う額、そして支払う前の財布の中身が決まっていれば、支払った後に財布に残る金額は、支払い方によらずに一つの額に決定するはずである。そして非冗長解の場合はその金額を冗長性がない形で表現する小銭の集まりを作るが、それが命題 2 により最小枚数の表現になるので、よって非冗長解は最適解となる。

この命題 12 は、非冗長解の存在を保証するものではなく、存在すればそれが最適解となる、という主張であるから、非冗長解が最適解に完全に一致することはまだ保証されていない。それは次の命題 13 で示される。

命題 13.

各代金に対して、非冗長解は常に存在する (よって非冗長解と最適解は常に一致する)。

証明
もとの財布の小銭の集まりを A、支払い後の財布の金額の最小表現 (冗長でない表現) による小銭の集まりを B とする。まず、札が必要ない場合を考える。Aと B に共通に現れる小銭の集まりを C と書き、A, B から C を除いたものをそ3. 主要命題の易しい証明

4

れぞれ A′ , B ′ とする。このとき、A′ を支払えばおつりが B ′ であることを示そう。もし、それが言えれば、支払い後の財布の中身は B ′ と C を合わせた B になり、よってこの支払いは非冗長解となる。
まず、A の合計金額 Tot(A) は、代金 x と Tot(B) の合計に等しいが、Tot(A) = Tot(A′ ) + Tot(C),Tot(B) = Tot(B ′ ) + Tot(C)より、Tot(A′ ) = x + Tot(B ′ )となるので、x の代金に A′ を支払えば、確かに Tot(B ′ ) の金額のおつりが返ってくる。B ′ は B の一部だから、当然冗長性はなく、よって仮定 4 と命題 1 の一意性により、おつりは B ′ として返ってくるはずである。
札が必要な場合も、上の式の左辺に札の金額 Mc を追加するだけであり、議論はほぼ同じである。

この命題 13 により、非冗長解が常に存在することが構成的に示されたことになり、そして命題 12 によりそれは最適解となる。なお、命題 13 は、非冗長解が一つしかないことは保証していないが、その証明の考え方を用いれば、実はそれが一つであることも示される。

命題 14.

各代金に対して、非冗長解は一意に決定する。

証明
命題 13 の証明の記号をそのまま用いることとする。札が必要ない場合を考える
が、札が必要な場合もほぼ同様であるので、そちらは省略する。
命題 13 の証明の支払い方 A′ とは違う支払い方 A′′ の非冗長解があるとすれば、
A′ , A′′ の 2 つの支払い方で共に財布に残る小銭 B が同じになる。この場合、
A′ ̸= A′′ より、A′′ に C の一部が含まれるか、または A′′ には C の小銭は含まれないかのいずれかである。
後者の場合、A′′ は A′ に完全に含まれることになり、A′ ̸= A′′ より、Tot(A′′ ) <Tot(A′ ) となる。当然、そのおつり B ′′ も Tot(B ′′ ) < Tot(B ′ ) となるが、一方、B ′′ と支払わなかった小銭 (C と、A′ から A′′ を除いたもの) が最終的に残る小銭となる。そしてそれが B に一致するはずなので、支払わなかった小銭のうち、A′ から A′′ を除いたものは B から C を除いた B ′ にも含まれていなければなら3. 主要命題の易しい証明

5ない。ということは、A′ から A′′ を除いたものは A′ にも B ′ にも共通に含まれていることになり、それは C, A′ , B ′ の定義に反する。
また前者の場合は、仮定 5 によって A′′ に含まれる C の一部はおつり B ′′ には含まれないことになるが、その C の一部は支払っている際の財布の中にもなく、またおつりにも含まれないので、B の中にも当然含まれないことになる。しかし、これは C の定義に反する。
よって、A′ と違う払い方で結果が B となることはないことが示され、これにより非冗長解の一意性が示されたことになる。

この命題 12, 13, 14 が、[1] の命題 11 の別証明にあたるが、[1] の論法に比べてかなりシンプルになっている。特に、[1] では多用した新しい記号による数式が、こちらの証明の考え方ではほとんど必要がないことがわかる。
なお、一意性を示す命題 14 は最後にしたが、これは [1] では示していない次の命題を用いれば、一意性はすぐに従う。

命題 15.

支払い方が違えば、財布に残る小銭の集まりは必ず異なる。

証明

2 通りの支払い方を、下の位の硬貨から見ていって、初めてその出し方が違う位の部分を考えると、そこは一方は何枚か出し、他方はその位の硬貨は出してない、という形になっているはずである。
それは、もし両者ともその位の硬貨を出していて、その枚数が違っているとすると、それより下の位の硬貨は同じものを出すわけだから、その位の硬貨の枚数の多い方は、仮定 5 に反するからである。
その位の硬貨を何枚か出す方は、やはり仮定 5 によりおつりにはその額の硬貨は含まれないので、財布のその額の硬貨は必ず減ることになる。一方、その位の硬貨を出さない方には、そのおつりにその額の硬貨が必ず含まれる (それより下の位は他方と同じものを出すので) から、財布の中のその額の硬貨は必ず増えることになる。
よって、支払い方が異なれば、財布に残る小銭の集まりは必ず異なることになる。

これは、支払い方が違えば、小銭の「集まり」が違う、ということで、枚数が違うとまでは言っていないことに注意。例えば、代金 11 円に、15 円支払うのと 51 円支払う

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

6のは、どちらも 2 枚減って、おつりが 4 枚なので、違う支払い方だけれども枚数は同じとなる (もちろんいずれも最適解ではない)。

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) の引き算は、以下のようにすれば足し算に改良できる。

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

7

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 円が残ることになり、確かに非冗長解が得られる。
これは、引き算は多少楽になり、足し算で考えられるようになることが多少のメリットであるが、ただし慣れるまではかなり不安の残る方法だと思う。

5. 最後に58

最後に

本稿では、「裏側」から考えることで、[1] の主要な命題の証明を易しくすることができることを紹介した。
最後の節に書いたように、それ (に近いこと) を実際の場面で応用することもできなくはないが、そこにも書いたように、引き算で計算しない分、若干不安が残り、実際に実行するにはかなり勇気が必要そうな気がする。
私も普段は [1] の方法で考えながら出すことが多いが、間違えることもあって、財布が仮定 3 を満たさない状態であることもある。今回の方法ではどうかと言えば、コンビニのレジで商品を袋につめてもらう間に間違えずに計算できる自信はあまりないが、計算の優劣を決めるため、余裕があるときは試してみたいと思う。
なお、お釣りが 5 円、50 円、500 円になる場合は、1 円、10 円、100 円になる場合より少し自明さが少ないので、レジの人が少しとまどうことも多い。特に 55 円、550 円などのお釣りになる場合を読み切って小銭を正しく出せると、怪訝そうな顔をされることもある。ただし、そういう際に得意気な顔をするのは、間違えたときに逆に恥ずかしい思いをするかもしれないし、最近はまとめてお金を入れて自動的にお釣りを計算して出してくれるレジが増えているので、なんとも思ってくれないことも多いかもしれない。

参考文献[1] 竹野茂治、「財布の中の小銭の最適化について」、
http://takeno.iee.niit.ac.jp/~shige/math/lecture/misc/misc.html#kozeni1 (2014)