前回書いた定理1を再掲する。
定理1: 財布の中身N円の構成がコンパクトで、そこからm円の買い物(m≦N)をする場合、釣銭をコンパクトな構成で返してくれるならば、支払いの結果として財布の中身がコンパクトになるような支払い方法が存在する。
さらに以下が成り立つ。
定理2: 定理1のような支払い方法の中で釣銭中の紙幣・硬貨の合計数が最小になるようなものはただ1つである。
つまり、買い物の後の財布の紙幣・貨幣の構成をコンパクトにするような払い方のうちで、最もムダのない払い方がただ1つだけ必ず存在する。
証明は難しいが、以下のように考えると感覚として理解することができる。
- こちらは財布の中身N円(コンパクトな構成)を全て払うとしてみる
- 店は釣り(N-m)円をコンパクトな構成で返すとする
- 1,2でやりとりした紙幣・貨幣のうち重複しているものを1の払いから除く
この3で生成されたものが最もムダのない払い方である。
以前のエントリで書いた例でやってみる。財布の中身は9159円、買い物の金額は3627円とする。
- 財布の中身9159円を全て払う(5000円札×1、1000円札×4、100円玉×1、50円玉×1、5円玉×1、1円玉×4)
- 3627円を引いた釣り5532円を返す(5000円札×1、500円玉×1、10円玉×3、1円玉×2)
- 改めて、1,2で重複している5000円札×1、1円玉×2を1から除いた払い方を生成する
→ 1000円札×4、100円玉×1、50円玉×1、5円玉×1、1円玉×2
この結果、4157円出す(→ 釣りは4157 - 3627 = 530円)のが最もムダがなく、かつ結果として財布の中身がコンパクトになる払い方であることがわかる。
釣銭をコンパクトな構成でもらえるという条件(店側が釣銭の紙幣・貨幣を切らさない限り、通常は成り立つ)のもとでは、上記のような払い方を常に行っていれば財布の中身はコンパクトに保たれる。
