1. はじめに

1
2014 年 11 月 19 日

財布の中の小銭の最適化について
新潟工科大学 情報電子工学科 竹野茂治

1

はじめに

消費税などのため財布には常に小銭がかなり入っていて、その小銭での支払いに気を使う人が多いのか、どのように支払えば小銭を増やさずに済むか、という記事を最近
Web 上でいくつか目にした。
しかし、それらには数学的な証明がついていないようだったので、基本的な話から数学的に考察してみた。それをここにまとめておく。

2

設定

最初に、問題を考察する上での目標や設定、仮定などを上げておく。
本稿では、財布の中の小銭を減らすことを考え、そこに関係するいくつかの基本的な問題を数学的に考察することを目標とする。

仮定 1.

小銭を減らす、というのは、代金の支払いにおいて、おつりの枚数を減らすだけではなく、その代金に使用する小銭の枚数も同時に考えることとし、すなわち個々の代金に対して、(支払いに使う小銭の枚数) − (お釣りでもらう小銭の枚数)を最大化することを考える。

仮定 2.

お札の枚数は考えない。よって、代金は 1000 円未満の小銭部分だけを考えればよい。ただし、財布持ち金は代金を払うには十分あるとし、よって、その小銭を払うために 1000 円札も 1 枚は使えるとする。

仮定 3.

財布には無駄な小銭はないとする。すなわち、1 円、10 円、100 円硬貨は最大で 4 枚まで、5 円、50 円、500 円硬貨は最大で 1 枚しかないとする。

これは、代わりに次のような設定もありうるだろう。

3. 記号2

仮定 30 .

財布の小銭は、表現が一意な形で入っているとする。すなわち、5 円玉がなければ 1 円玉は 9 枚まで持てるとし、さらに 10 円玉もなければ 1 円玉は49 枚まで持てる等々。

さらに、次のような設定もありうる。

仮定 300 .

財布の小銭には上限等の条件は特に設けない。

普段から気をつけて小銭を使っていれば、財布の小銭を仮定 3 の状態に維持することはそれほど難しくはない。よって、しばらくは仮定 3 のもとで考えることにする。

仮定 4.

おつりを返す店側には、すべての種類の硬貨が常に必要な枚数揃っているとし、店員もおつりの枚数が最も少なくなるように返してくれるものとする。

個々の代金について、財布の中からの支払い方 (支払う貨幣の組) を解 と呼び、仮定 1を満たす解を 最適解 と呼ぶことにするが、そのような最適解が一通りであるかどうかは明らかではない。もし一通りではない場合、最適解のうち、例えば少額の硬貨がなるべく少なくなるような解を望ましいとする立場もあるかもしれないが、とりあえずそこまでは考えないし、むしろ最適解が一意的かどうかを先に検討したい。

仮定 5.

支払う硬貨の一部が、そのままおつりの一部として戻ってくる払い方は解とはしない。

これは、もちろんその重なる部分を最初から除いて払えばそれがおつりからも除外されるし、そのように払っても最終的な硬貨の枚数も同じであるので、そのような無駄(非本質的な多重性) を排除するための仮定である。
なお、私もたまに間違えて仮定 5 を満たさないような支払い方をすることがあり、その場合通常店員に変な顔をされたり指摘されたりするが、最近のコンビニなどでは何事もなくもレジを打って普通に返してくれることもある。

3

記号

手持ちの小銭や、おつりの小銭などの硬貨の集まりは、数学ではなんとなく「集合」を使えば表せそうに思うかもしれないが、「集合」では同じ要素が複数あることを表現できないので、ここではベクトルを使って表すことにする:

A = (n1 , n5 , n10 , n50 , n100 , n500 )(1)

3. 記号

3

この各成分の nj は 0 以上の整数で、その j 円の硬貨の枚数を表す。
なお、後でより一般の硬貨系の考察も可能なように、以下のように (1) を一般化しておく:A = (nj1 , nj2 , . . . , njm )(2)

ここで、jk は、

j1 = 1 < j2 < · · · < jm

(3)

で、使用する各硬貨の額を意味し、その硬貨の集合を

K = {j1 , j2 , . . . , jm }(4)とする。また、(2) を簡単に

A = (njk )k(5)のように書くことも許す。
このようなベクトル全体の集合を U0 とし、そのうち仮定 3 を満たすベクトル全体をU1 と書くこととする:

U0 = {(njk )k ; njk ≥ 0},

U1 = {(njk )k ; 0 ≤ njk < Njk }(6)

ここで Njk は、仮定 3 の各硬貨 jk の上限枚数 + 1 で、通常の硬貨系では、

N1 = N10 = N100 = 5,N5 = N50 = N500 = 2となる。
ひとつの小銭の集まり (ベクトル) A に対して、各硬貨の枚数 (各成分) njk が A の成分であることを明示するときは

njk = njk (A)のように書くことにする。
小銭の集まり A ∈ U0 に対して、その小銭の表す合計金額を Tot(A)、その小銭の合計枚数を Num(A) とする:

Tot(A) =m∑
k=1

jk · njk (A) =∑j∈Kj · nj (A),

Num(A) =∑j∈Knj (A)(7)

4. 硬貨系

41000 円 (=Mc とする) 未満の金額 x に対して、その金額を U1 のベクトルとして一意に表現する小銭の集まりを FM (x) と書くことにする:
Tot(FM (x)) = x (FM (x) ∈ U1 )U1 では、Mc 円未満の金額に対して、それを与える小銭の集まりが一意に決まることはほぼ自明と思われるが、のちに一般の硬貨系のために命題 1 でそれを示す。
U0 に大小関係  () を、次のように導入する:
A  B (または B  A) ⇐⇒ すべての j ∈ K に対して nj (A) ≤ nj (B)もちろん、これは全順序ではない。
これら以外にも必要な記号があれば、適宜導入していく。

4

硬貨系

まずは、一般の硬貨系 (2), (3), (4) とその上限 (+1) である Nj について考察する(Nj ≥ 2)。本稿では、Mc 未満の金額をすべて一意的に表せる硬貨系を扱うことにする。
硬貨 j1 だけを使って作れる最大額は、(Nj1 − 1)j1 = N1 − 1
であり、これが (j2 − 1) 以上でないと (j2 − 1) 円が表せないし、逆にこれが j2 以上だと j2 を 2 通りで表せてしまうので、この硬貨系ですべての金額を一意に表せるためには

j2 = N1 = Nj1(8)であることが必要になる。
同様に硬貨 j1 , j2 の 2 枚で作れる最大額は、(8) より、(Nj1 − 1)j1 + (Nj2 − 1)j2 = (j2 − 1) + (Nj2 − 1)j2 = Nj1 Nj2 − 1
であり、上と同じ理由で、この値は j3 − 1 に等しい必要がある。よって、

j3 = Nj1 Nj2(9)5. 基本的な事実5となる。この議論を繰り返せば、結局すべての k (≥ 2) に対し、

jk = Nj1 Nj2 · · · Njk−1 =

k−1
∏

Nji

(10)

i=1

となり、またこの硬貨系で表せる最大の金額 +1 である Mc 円は

Mc =

m
∏
k=1

Njk =

∏

Nj

(11)

j∈K

となる。

0 ≤ x < Mc の金額 x に対して、(10) を満たす硬貨系 (2), (3), (4) では、x を表現する U1 の硬貨の集まりが必ず存在し、その硬貨の集まりは一意的
に定まる。

命題 1.

証明
(10) より、Tot(A) は、

Tot(A) = nj1 + Nj1 (nj2 + Nj2 (nj3 + · · ·))(12)のように表されることに注意する。

Tot(A) = x とすると、nj1 (A) は、(12) より x を Nj1 で割った余りとすればよい。また nj2 (A) は、(x − j1 · nj1 (A))/Nj1 を Nj2 で割った余りとすればよい。これを繰り返していくことで仮定 3 を満たす A (∈ U1 ) が構成される。
一意性は、もし Tot(A) = Tot(B) = x (A, B ∈ U1 ) であるとすると、nj1 成分の一意性(nj1 (A) = nj1 (B)) は、Nj1 で割った余りを考えればそれが成立することはわかるし、
nj2 成分の一意性も、上と同じように (x − j1 · nj1 (A))/Nj1 を Nj2 で割った余りを考えればよい。以下同様にして繰り返せば、すべての j ∈ K に対して、nj (A) = nj (B) であることがわかる。
この一般の硬貨系では、必要なときに使用できるお札は Mc 円札であることになる。

5

基本的な事実

この節では、硬貨系の支払いとおつり等に関する基本的な事実をいくつか取り上げていく。

5. 基本的な事実

6

A ∈ U0 , B ∈ U1 が Tot(A) = Tot(B) であれば、Num(A) ≥ Num(B) となる。さらに、この等号が成り立つのは A = B のときのみである。

命題 2.

これは、同じ額では、A のように仮定 3 を満たさない硬貨の集まりよりも、仮定 3 を満たす集まりの方が硬貨の枚数は少なくなることを意味する。
例えば、同じ 552 円を表す組は、U0 でなら 10 円玉 5 枚以上も使えるし、100 円玉も5 枚以上使えるので色々あるが、その枚数が最小になるのは、U1 の 500 円玉 1 枚、50円玉 1 枚、1 円玉 2 枚、になることを意味する。
命題 2 の一般の場合を証明する前に、簡単な例として 1 円玉、5 円玉、10 円玉の 3 種
類だけの場合を考える。この場合命題 2 は、

a + 5b + 10c = a0 + 5b0 + 10c0 ,
0

(13)
0

0

(a ≥ 0, b ≥ 0, c ≥ 0, 0 ≤ a < 5, 0 ≤ b < 1, 0 ≤ c < 5)のときに、

a + b + c ≥ a0 + b 0 + c 0(14)であることを意味する。

(13) を 5 で割った余りを考えれば、a ≡ a0 (mod 5)となり、a ≥ 0, 0 ≤ a0 < 5 より

a = a0 + 5r1(15)となる 0 以上の整数 r1 が存在することになる。これは、すなわち a のうち 5r1 円分の 1 円玉は r1 個の 5 円玉で置きかえられることを意味する。

(15) を (13) に代入して整理すれば、
a0 + 5r1 + 5b + 10c = a0 + 5b0 + 10c0 ,r1 + b + 2c = b0 + 2c0となるので、最後の式を 2 で割った余りで考えれば、上と同様にして

r1 + b ≡ b0 (mod 2)

5. 基本的な事実

7より

r1 + b = b0 + 2r2(16)となる 0 以上の整数 r2 が存在する。これは、b 個の 5 円玉と、r1 個の 5 円玉分の 1 円
玉の集まりのうち、5 × 2r2 円分は r2 個の 10 円玉で置きかえられることを意味する。

(16) を上の式に代入すれば、
b0 + 2r2 + 2c = b0 + 2c0
より

r2 + c = c0(17)となる。これは、c 個の 10 円玉と r2 個の 10 円玉分の下からの繰り上がりが c0 個の10 円玉に等しいことを意味する。

(15), (16), (17) を辺々加えると、
r1 + r2 + a + b + c = a0 + b0 + c0 + 5r1 + 2r2となるので、a + b + c = a0 + b0 + c0 + 4r1 + r2 ≥ a0 + b0 + c0
であることがわかる。しかも、等号が成り立つのは r1 = r2 = 0 のときであるから、(15), (16), (17) より a = a0 , b = b0 , c = c0 のときであることがわかる。
一般の場合も、これと同様の考察を行えば、命題 2 が証明できる。
証明 (命題 2)Tot(A) = Tot(B) より
m∑
k=1

njk (A) · jk =m∑njk (B) · jk

(njk (A) ≥ 0, 0 ≤ njk (B) < Njk )

(18)

k=1

(10) より、j2 = Nj1 で割った余りを考えると、
nj1 (A) ≡ nj1 (B) (mod Nj1 )より、

nj1 (A) = nj1 (B) + r1 Nj1(19)

5. 基本的な事実8となる 0 以上の整数 r1 が存在する。これを (18) に代入し、両辺から nj1 (B) を引き、Nj1 で割ると、(12) より

r1 + nj2 (A) + Nj2 (. . .) = nj2 (B) + Nj2 (. . .)のような形になるので、これを Nj2 で割った余りを考えると、

r1 + nj2 (A) ≡ nj2 (B) (mod Nj2 )なので、

r1 + nj2 (A) = nj2 (B) + r2 Nj2となる 0 以上の整数 r2 が存在する。この作業を繰り返すと、結局 2 ≤ k < m の k に対し

rk−1 + njk (A) = njk (B) + rk Njk(20)となるような 0 以上の整数 rk が存在し、さらにrm−1 + njm (A) = njm (B)

(21)

となる。

(19), (20), (21) を辺々加えると、
m−1
∑
k=1

rk +

m
∑

njk (A) =

k=1

m
∑

njk (B) +

k=1

m−1
∑

rk Njkk=1となるので、よってNum(A) = Num(B) +m−1∑

rk (Njk − 1)

(22)

k=1

となるので、Num(A) ≥ Num(B) が成り立つ。
さらに、Num(A) = Num(B) となるのは、Njk ≥ 2 よりすべての rk が 0 になることと同値で、それは、(19), (20), (21) よりすべての j に対して nj (A) = nj (B) であることと同じ、すなわち A = B と同じであることがわかる。
以後、主に H ∈ U1 を財布の小銭全部、x > 0 を代金、P ∈ U1 を支払う小銭 (必要な場合はこれに Mc 円の額のお札を追加する場合もある)、R ∈ U1 をおつりの小銭、とする。

5. 基本的な事実

9

P と R は仮定 5 を満たさなければいけないので、各硬貨成分 nj に対して、nj (P ) とnj (R) のいずれかが必ず 0 でなければならない。すなわち、すべての j ∈ K に対してnj (P )nj (R) = 0 となるので、通常のベクトルと同じように内積を
∑

A・B =

nj (A)nj (B)

(23)

j∈K

と定めると、この仮定 5 の条件は、簡単に P ・R = 0 と書くことができる。
逆に、P , R がP, R ∈ U1 , Tot(P ) > Tot(R), P ・R = 0(24)

を満たしているとき、y = Tot(P ) − Tot(R) とすると、R は代金 y に対して P を支払っ
たおつりと見ることができる。実際、R ∈ U1 より R は仮定 4 を満たすし、P ・R = 0
より仮定 5 も満たされていて、金額的にも適合する。すなわち、支払いとおつりは (24)の関係を満たすことが互いの条件であることがわかる。

命題 3.

x (< Mc ) が代金、P (∈ U1 ) が支払い、R (∈ U1 ) がおつりの場合、
X = FM (x) とすると、Num(X) ≥ Num(P ) − Num(R)(25)

が成り立つ。等号成立は Tot(R) = 0 のときで、かつこのときに限る。
これは例えば、代金が 72 円で、支払いが 122 円、おつりが 50 円の場合を考えると、Num(X) は 50 円玉 1 枚、10 円玉 2 枚、1 円玉 2 枚より 5 枚、Num(P ) は 100 円玉
1 枚、10 円玉 2 枚、1 円玉 2 枚より 5 枚、Num(R) は 50 円玉 1 枚なので、Num(X) = 5,

Num(P ) − Num(R) = 5 − 1 = 4となり、(25) が成り立つ。
この命題 3 からすぐに次の系が得られる。

系 4.

丁度の代金を払える場合はそれが最適解であり、それは一意的である。
すなわち、おつりをもらう場合は、丁度の代金の場合の小銭の枚数よりも必ず減らせる小銭の枚数は少なくなる。

命題 3 は、命題 2 から容易に示されるが、その証明のため、次の記号を導入する:(A, B ∈ U0 ),A ⊕ B = (njk (A) + njk (B))k
(A, B ∈ U0 , A  B),A B = (njk (A) − njk (B))kA ∧ B = (min{njk (A), njk (B)})k (A, B ∈ U0 )

6. 札を使う場合

10

証明 (命題 3)
X ⊕ R ∈ U0 の定義から明らかに、Tot(X ⊕ R) = Tot(X) + Tot(R) = x + Tot(R) = Tot(P )であるから、命題 2 より、Num(X ⊕ R) ≥ Num(P ) となるが、定義より明らかに
Num(X ⊕ R) = Num(X) + Num(R) なので、Num(X) + Num(R) ≥ Num(P )となり、(25) が成り立つ。
また、等号が成り立つのは、命題 2 より X ⊕ R = P となる場合であるが、(24) より
P ・R = 0 でなければいけないので、R の成分はすべて 0 でなければならない。よって、Tot(R) = 0 となる。
逆に Tot(R) = 0、すなわちおつりがなければ、もちろん等号となる。

6

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

命題 5.

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

これは、例えば、財布の中の小銭が 500 円玉 1 つと 1 円玉 1 つで、代金が 496 円であった場合、• 1000 円札 1 枚と 1 円の 1001 円を払っておつりを 505 円もらう → 小銭は 1 枚
減って 2 枚増える
• 500 円玉 1 枚払っておつりを 4 円もらう → 小銭は 1 枚減って 4 枚増えるという例があるので、「常に」小銭で支払う方が小銭の枚数が減る、ということではな
く、小銭で払う方が小銭の枚数が減るような小銭での支払い方が「少なくとも 1 つは」存在する、という話である。例えば上の例でも、501 円の支払いをすれば、小銭は 2 枚
減って、おつりは 5 円玉 1 枚であり、これが札を使う場合よりも小銭が減る最適解になる。

6. 札を使う場合

11

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

j=j

0


 j <j

0

ならば
ならば
ならば

nj (P ) = nj (X),nj (P ) = nj (X) + 1,
nj (P ) = 0(26)

なお、この P が解であるためには、1 ≤ j < j0 で nj (X) > 0 であるような j がなければならず、そしてこの場合必ず Tot(R) > 0 になる。
また、この極小解は、x, H に対して一意的ではない。例えば、x = 120 円、H が 500
円玉 1 つ、100 円玉 1 つ、50 円玉 1 つ (650 円) の場合、500 円玉 1 つのみの支払いも極小解 (j0 = 500) だし、100 円玉 1 つと 50 円玉 1 つの支払いも極小解 (j0 = 50)となるが、500 円玉 1 つと 50 円玉 1 つの支払いは極小解ではない。

Tot(H) ≥ x の場合、丁度支払える解か極小解のいずれかが必ず存在

補題 6.
する。

証明 (補題 6)
X = FM (x) とする。このとき、すべての j ∈ K に対し nj (X) ≤ nj (H) であれば、
X  H なので 丁度 X を支払う解が存在する。
そうでない場合は、ある j ∈ K に対して nj (X) > nj (H) となるが、そのような j の一番大きいものを ja とすると、nja (X) > nja (H) で、かつすべての j > ja に対してnj (X) ≤ nj (H) となる。
このとき、jb > ja で njb (X) < njb (H) となる jb が少なくとも一つ存在する。それは、もしそうでないとすると、すべての j > ja で nj (X) = nj (H) ということになるが、それだと nja (X) > nja (H) より x > Tot(H) となってしまうからである。
この jb を j0 とすれば、(26) を満たすような P  H が作れることになる。
極小解は、ある意味では単純な支払い方法で、必ずしもおつりの枚数を減らすことにはつながらないが、命題 5 の証明には利用できる。
命題 5 よりも少し強い形の命題も紹介しよう。

命題 7.

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

より詳しく述べると、H の jn (n < m) 以下の硬貨のみからなるものを Ĥ とす
ると、Tot(Ĥ) ≥ x であるとき、Ĥ  P ではない支払い P ( H) とそのおつ
り R に対して、

Num(P̂ ) − Num(R̂) > Num(P ) − Num(R)(27)

6. 札を使う場合

12となるような支払い P̂ ( Ĥ) とそのおつり R̂ が存在する。
この命題 7 を用いれば命題 5 を証明することは容易である。すなわち、命題 5 の札
(Mc 円札) を Mc 円の硬貨だと思えば、それは命題 7 そのものになり、それにより (27)が言えれば、Mc 円の硬貨を元の札に戻せば、(27) の右辺の Num(P ) の硬貨はさらに1 枚減ることになるから、命題 5 が示されることになる。
よって、以下ではより強い命題 7 を証明する。
証明 (命題 7)
Step 1. まず P が簡単な場合に帰着できることを示す。

Tot(Ĥ) の小銭で x 円が丁度払える場合は、系 4 よりそれが唯一の最適解であるので、この場合はその解が (27) を満たすことがわかる。
よって、以後は丁度は払えない場合を考えるが、もし jn より大きな額の硬貨が複数 Pに含まれれば、少なくとも一つ以外はおつりにも返されてしまうことになるので仮定5 に反する。よって、jn より大きな額の硬貨は 1 枚のみ P に含まれることになる。
また、その硬貨は jn+1 でかつ njn (X) > 0 である場合のみ考えればよい。それは、もしその硬貨 jk が jn+1 より大きい額の硬貨である場合 (k > n + 1) は、P の jk を jn+1
で置き換えたものを P 0 とすると、P で X を払ったおつりは、P 0 で X を払ったおつりに jk で jn+1 を払ったおつりを加えたものになるので、払う枚数は両者で変わらな
いが、もらうおつりは P よりも P 0 の方が少なくなる。よって P よりも P 0 の方が小銭は確実に少なくなるので、もし P 0 に対してこの命題が成り立てば、P に対してもこの命題が成り立つことになる。

Step 2. P̂ を構成するため、小さい額の方を除いた金額の極小解 P2 を作る。
P から jn+1 の硬貨 1 枚を取り除いたものを P1 ( Ĥ) とする。もし Tot(P1 ) ≥ x だと jn+1 の硬貨そのものがおつりとして返却されてしまうことになるので、Tot(P1 ) < x
でなければならない。
x̄ = x − Tot(P1 ) (> 0) とし、P1  Ĥ より H̄ = ĤP1 とすると、

Tot(H̄) = Tot(Ĥ) − Tot(P1 ) ≥ x − Tot(P1 ) = x̄となるが、jn+1 円 + P1 の x 円の代金のおつりが Tot(R) 円で、これは jn+1 円に x̄
円の代金のおつりと等しいので、このおつりも R となる。よって、X̄ = FM (x̄) とし、
R の一番少額の硬貨を js とすると、
 js < j ≤ jn


j=j

s


 j < j ,j > jsn

ならば nj (X̄) = Nj − nj (R) − 1,
ならば nj (X̄) = Nj − nj (R),ならば nj (X̄) = 0(28)

6. 札を使う場合

13であることがわかる。
一方、もし H̄ で x̄ が丁度払えるとすると、それに Tot(P1 ) を合わせれば元の x の丁度の解になってしまうので、仮定より H̄ で x̄ を丁度払うことはできない。よって、補題 6 により、H̄ 内で x̄ の代金に対する極小解 P2 とそのおつり R2 が存在する(Tot(P2 ) > 0)。極小解 P2 の定義 (26) の j0 (≤ jn ) を考えると、
 j0 < j ≤ jn

j=j

0


 j < j ,j > j
0n

ならば nj (P2 ) = nj (X̄),
ならば nj (P2 ) = nj (X̄) + 1,
ならば nj (P2 ) = 0(29)であり、かつ j < j0 で nj (X̄) > 0 となる j が少なくとも一つある。よって、(28) より js < j0 であることがわかる。

Step 3. x̄ の代金に対して、jn+1 の支払いに対するおつり R と、P2 の支払いに対する
おつり R2 との関係を考える。
今、y = jn+1 − Tot(P2 ) (> 0), Y = FM (y) とすると、Tot(Y ) + Tot(R2 ) = jn+1 − Tot(P2 ) + Tot(R2 ) = jn+1 − x̄ = Tot(R)であり、nj (Y ) は、j < j0 では nj (Y ) = 0, j = j0 では、(28), (29) より、

nj (Y ) = Nj − nj (P2 ) = Nj − nj (X̄) − 1 = Nj − (Nj − nj (R) − 1) − 1= nj (R)j0 < j ≤ jn では、
nj (Y ) = Nj − nj (P2 ) − 1 = Nj − nj (X̄) − 1 = Nj − (Nj − nj (R) − 1) − 1= nj (R)なので、結局、

j0 ≤ j ≤ jn ならば nj (Y ) = nj (R), j < j0 , j > jn ならば nj (Y ) = 0となり、よって Y  R であることがわかる。

Tot(R) − Tot(Y ) = jn+1 − x̄ − (jn+1 − Tot(P2 )) = Tot(P2 ) − x̄ = Tot(R2 )なので、よって R2  R であり、y > 0 より Num(Y ) > 0 で、

R2 = RY, Num(R2 ) = Num(R) − Num(Y )(30)

6. 札を使う場合

14となることがわかる。

Step 4. 最後に P̂ , R̂ を構成する。
さて、P3 = P1 ⊕ P2 とすると、H̄ = ĤP1  P2 より P3  Ĥ で、

Num(P3 ) = Num(P1 ) + Num(P2 )

(31)

となる。

Tot(P3 ) − x = Tot(P1 ) + Tot(P2 ) − (x̄ + Tot(P1 )) = Tot(P2 ) − x̄ = Tot(R2 )なので、P3 で x を支払うおつりは R2 になる。ただし、P3 には P1 も含まれていて、そこに R2 と共通の硬貨が含まれる可能性も考慮し、P3 と R2 から共通の硬貨
B = P3 ∧ R2 を取り除く。B は B  P3 , B  R2 で、P̂ = P3 B, R̂ = R2 B とすれば、P̂ ・R̂ = 0 となり、P̂  P3  Ĥ で、

Num(P̂ ) − Num(R̂) = (Num(P̂ ) + Num(B)) − (Num(R̂) + Num(B))= Num(P3 ) − Num(R2 )となる。
よって、P̂ で x を支払ったおつりは R̂ で、(30), (31) より

Num(P̂ ) − Num(R̂) = Num(P3 ) − Num(R2 )= Num(P1 ) + Num(P2 ) − (Num(R) − Num(Y ))= (Num(P1 ) − Num(R)) + (Num(P2 ) + Num(Y ))= (Num(P ) − Num(R)) + (Num(P2 ) + Num(Y ) − 1)となるが、Num(P2 ) > 0, Num(Y ) > 0 より、

Num(P̂ ) − Num(R̂) ≥ Num(P ) − Num(R) + 1(32)となり、よって P̂ , R̂ により (27) が成り立つことになる。
証明がだいぶ長くてわかりにくいかもしれないが、jn+1 = 500 円、Ĥ が 372 円、x = 247
円、P が 552 円の例で考えると、R は 552 − 247 = 305 円、P1 は 552 − 500 = 52円、x̄ と H̄ は x と H からこの P1 の 52 円を除いて、x̄ = 247 − 52 = 195 円、H̄ は372 − 52 = 320 円となる。

P2 は H̄ での x̄ に対する極小解なので、この場合は必然的に 200 円となり、おつり R2
は 5 円、Y は 500 − 200 = 300 円となる。よって P3 は 52 + 200 = 252 円で、これはR2 とは交わらないので、B は 0 円、P̂ = P3 で 252 円、R̂ = R2 で 5 円となる。

7. 上位と下位の分解15

この場合、Num(P ) − Num(R) = 4 − 4 = 0、Num(P̂ ) − Num(R̂) = 5 − 1 = 4 であるが、その差 4 は Num(P2 ) + Num(Y ) − 1 = 2 + 3 − 1 に等しくなっていることが確認できる。
なお、一般に B が 0 であることが証明できるのか、それとも B が正の金額となるよ
うな例があるのかはよくわからないが、それは上の命題の証明には直接影響はない。

上位と下位の分解

7

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

n < m に対して Yn+ , Yn− ∈ U1 を、{

nj (Yn+ ) =Nj − 1 (j ≥ jn ),0(j < jn ),{nj (Yn− ) =0(j > jn ),Nj − 1 (j ≤ jn )とすると、A ∈ U1 に対して、A の jn+1 以上の硬貨の部分 A+ , A の jn 以下の硬貨の部分 A− は、それぞれ+
A+ = A ∧ Yn+1,

A− = A ∧ Yn−のように書くことができることになる。

Tot(H) ≥ x (> 0), X = FM (x) を jn (0 < n < m) より大きいかそれ以下かで上位、下位に分け、

命題 8.

+
+
H + = H ∧ Yn+1
, H − = H ∧ Yn− , X + = X ∧ Yn+1
, X − = X ∧ Yn−とするとき、

1.

Tot(H − ) ≥ Tot(X − ) ならば Tot(H + ) ≥ Tot(X + ) でなくてはならない。

2.

Tot(H − ) ≥ Tot(X − ) の場合、X ± に対する H ± での最適解 P ± とそのおつ
り R± により、X の H での最適解 P , R は、P = P − ⊕ P + , R = R− ⊕ R+
により得られる。

7. 上位と下位の分解

16

これは、例えば H が 772 円で、代金 x がそれで払える額である場合、1. は 100 円未
満の部分が 72 円で払えるならば、100 円以上の方も、その 72 円の残りを使わなくても 700 円で払えるはずだ、ということを意味し、よってこちらの証明は易しい。
また 2. は、その場合最適な支払いは、72 円での 100 円未満の最適化と、700 円での100 円台の最適化に分けて考えればいいことを意味している。
証明
1. もし Tot(H + ) < Tot(X + ) ならば、少なくとも Tot(X + ) ≥ Tot(H + ) + jn+1 であるが、この硬貨系では Tot(H − ) < jn+1 であるので、Tot(H) = Tot(H + ) + Tot(H − ) < Tot(X + ) − jn+1 + jn+1 ≤ Tot(X)すなわち Tot(H) < x となり仮定に反する。

2. もし、P , R が最適解でないとすると、これとは別に最適解 P3 とそのおつり R3 があり、Num(P3 ) − Num(R3 ) > Num(P ) − Num(R)(33)となるはずである。このように仮定して矛盾を示す。
なお、命題 5 より、P3 はお札は不要のはずで、よって P3  H である。以下、2 つの場合に分けて考える。

Step 1. まず P3 の下位部分で X − が払える場合を考える。
P3 , R3 を上位、下位に分け、++P3+ = P3 ∧ Yn+1
, P3− = P3 ∧ Yn− , R3+ = R3 ∧ Yn+1
, R3− = R3 ∧ Yn−とする。

Tot(P3 ) ≥ x であるから、Tot(P3− ) ≥ Tot(X − ) の場合は、命題 8 の 1. により Tot(P3+ ) ≥Tot(X + ) となる。よって、P3± の X ± に対するおつりが R3± となり、これに関しては
X ± の最適解は P ± , R± なので、Num(P ± ) − Num(R± ) ≥ Num(P3± ) − Num(R3± )となるはずであり、よって上位、下位の式を辺々加えればNum(P ) − Num(R) ≥ Num(P3 ) − Num(R3 )となり、(33) に反する。

7. 上位と下位の分解

17

Step 2. 次に Tot(P3− ) < Tot(X − ) の場合を考える。
この場合は、Tot(P3+ ) = Tot(X + ) では Tot(P3 ) ≥ x とならないので、よって少なくとも Tot(P3+ ) ≥ Tot(X + ) + jn+1 であることになる。
この場合、P3 で X を支払ったおつり R3 は、P3+ で X + を払ったおつり R4+ に P3−を加えて、そこから X − を払ったおつりに等しい。よって、その上位部分である R3+
は、R4+ から jn+1 を引いたものであり、

R3+ = FM (Tot(R4+ ) − jn+1 ) = FM (Tot(P3+ ) − Tot(X + ) − jn+1 ) (≥ 0)(34)に等しく、R3− は、jn+1 と P3− の和 P4− = FM (jn+1 ) ⊕ P3− から X − を払ったおつりに等しい:

R3− = FM (Tot(P4− ) − Tot(X − )) = FM (jn+1 + Tot(P3− ) − Tot(X − )) (> 0)(35)

この場合、まず上位の X + に対しては、P + , R+ が最適解なので、Num(P + ) − Num(R+ ) ≥ Num(P3+ ) − Num(R4+ )(36)である。また、(34) よりTot(R3+ ⊕ FM (jn+1 )) = Tot(R4+ )であるから、命題 2 より

Num(R3+ ⊕ FM (jn+1 )) = Num(R3+ ) + 1 ≥ Num(R4+ )

(37)

となる。
最後に R3− であるが、これは P3− に jn+1 という上位の硬貨を追加して代金を払ったおつりが R3− なので、命題 7 (式 (32)) により、最適解 P − , R− との枚数の間には、Num(P − ) − Num(R− ) ≥ Num(FM (jn+1 ) ⊕ P3− ) − Num(R3− ) + 1= Num(P3− ) − Num(R3− ) + 2(38)という不等式が成り立つ。
結局、(36), (37), (38) の辺々をそれぞれ加えて整理すると、Num(P ) − Num(R) ≥ Num(P3 ) − Num(R3 ) + 1となり、よって (33) に反する。

(39)

8. 最適解

18

最適解

8

前節の命題 8 により、下の額から切り分け、ある額以下の硬貨で分割できる場合にはそれぞれで最適化を考えればいいことがわかった。例えば、代金 x が 337 円で、財布
H に 544 円ある場合は、• 1 円玉以下 : x は 2 円、H は 4 円なので、ここでまず分割する (x1 = 2, H1 =FM (4))。残りは x は 335 円、H は 540 円。
• 5 円玉以上で 5 円玉以下 : x は 5 円、H 0 円なので分割できない。
• 5 円玉以上で 10 円玉以下 : x は 35 円、H 40 円なので、ここで分割できる(x2 = 35, H2 = FM (40))。残りは x は 300 円、H は 500 円。
• 50 円玉以上で 50 円玉以下 : x は 0 円、H は 0 円なのでここは考えなくてよい。
• 100 円玉以上で 100 円玉以下 : x は 300 円、H は 0 円なので分割できない。
• 100 円玉以上で 500 円玉以下 : x は 300 円、H は 500 円なのでここで分割(x3 = 300, H3 = FM (500))。
これにより、x = x1 + x2 + x3 , H = H1 ⊕ H2 ⊕ H3 と分割され、そのそれぞれ Hk とxk で最適解を考えればよいことになる。
しかも、x2 と H2 、x3 と H3 は、下の方の額の硬貨がないので、その分を全体で割った硬貨系での最適化と同じことになる。すなわち、x2 = 35 円を H2 = FM (40) 円で払う問題は、全体を 5 で割った 1 円玉と 2 円玉の硬貨系で、「1 円玉 1 枚と 2 円玉 3 枚の 7 円」を、「2 円玉 4 枚」の中から支払う問題と同じことになるし、x3 = 300 円を
H3 = FM (500) 円で払う問題は、100 で割った 1 円と 5 円の硬貨系で、「1 円玉 3 枚の3 円」を「5 円玉 1 枚」の中から支払う問題と同じになる。
このように考えると、それぞれの分割単位での最適解を求める問題は、代金の一番低い額の硬貨成分 nj1 (X) は常に正であると仮定し、H で下から分割ができない場合のみを考えればいいことになる。

Tot(H) ≥ x, X = FM (x) で nj1 (X) > 0 のとき、命題 8 のように分割できないのは、以下の 2 つを満たす形の場合である。

命題 9.
•

nj1 (X) > nj1 (H)•

X の最高位の硬貨を jn とするとき、j1 < j < jn のすべての j に対してnj (X) ≥ nj (H)8. 最適解19

なお、最高位の njn (X) (> 0) と njn (H) との間には特に条件はない。例えば、x = 224
円で Tot(H) = 313 円の場合 (njn (X) < njn (H)) もあれば、x = 224 円で Tot(H) =513 円の場合 (njn (X) > njn (H)) もあれば、x = 224 円で Tot(H) = 713 円の場合
(njn (X) = njn (H)) もありうる。
証明
もし、nj1 (X) ≤ nj1 (H) ならば最下位 の j1 で分割ができてしまうので、nj1 (X) <nj1 (H) でなければならない。
その上の額でも、j < jn で nj (X) < nj (H) となる j があれば (nj (X) + 1) 個の j 円の H の硬貨で j 以下の X の金額を越え、やはりそこで分割できてしまうことになる
ので、j1 < j < jn のすべての j に対して nj (X) ≥ nj (H) でなければならない。
逆に、その両者が満たされていれば、下から見てどこで止めても X の額の方が H の額を上回るので分割はできないことは明らか。
よって後は命題 9 を満たす形式の x, H の場合の最適化問題を解けばよいのだが、この場合解答は容易である。

命題 10.

命題 9 を満たす x, H に対する最適化解 P は、X の最上位部分のみを一つ増やした額 x0 = (njn (X) + 1)jn に対する最適解に等しい。

この命題は、例えば x = 224 円で Tot(H) = 313 円、Tot(H) = 513 円、Tot(H) = 713
円等の場合は、いずれも x0 = 300 円に対する最適な支払いをすればよいことを意味する。すなわち Tot(H) = 313 円の場合は 300 円 (x0 丁度) が、Tot(H) = 513 円の場合
は 500 円 (x0 の極小解) が、Tot(H) = 713 円の場合は 500 円が、それぞれ最適な支払いとなる。これも、多分日常的な感覚とはそれほどずれていない自然な解だと思われる。
証明
Step 1. まず、jn より下の硬貨は払えないことを示す。

j1 の硬貨は最大でも nj1 (H) しか払えず、これは nj1 (X) より小さいので、上から借りなければ支払えない。よって、j1 のおつりは、
nj1 (R) = Nj1 + nj1 (P ) − nj1 (X) = (Nj1 − nj1 (X)) + nj1 (P )となるが、最後の右辺の最初の項は常に正なので、nj1 (R) > 0 となる。よって、仮定
5 により nj1 (P ) = 0 でなければならない。
次は j = j2 , j3 , . . . を帰納的に考えると、j の硬貨は一つ下の額の硬貨に貸しておつりを作っているので、nj (P ) (≤ nj (H) ≤ nj (X)) から一つ減ることになり、やはり nj (X)を払うことはできず、上から一つ借りなければいけない。よって、j のおつりは、

nj (R) = Nj + nj (P ) − 1 − nj (X) = (Nj − nj (X) − 1) + nj (P )

8. 最適解20となるが、この右辺の最初の項は 0 以上なので、nj (P ) > 0 だと nj (R) と nj (P ) の両者が正となり、やはり仮定 5 に反する。
よって、j < jn では nj (P ) = 0 でなければならない。

Step 2. 次に jn 以上を含めた支払いについて考える。
Step 1. により、P は jn 以上の硬貨の支払いのみが可能なことになるが、この場合は、どのように払っても jn 未満のおつりは同じであり、しかも、それは一つ jn を借りなければ支払えないので、そのおつり R1 は、jn 未満の X を jn で払ったおつりとなる。
その下位のおつりのために、P は、

Tot(P ) − jn ≥ njn (X)jn
でなければならず、よって P は、Tot(P ) ≥ njn (X)jn + jn
で、P で (njn (X)jn + jn ) を払ったおつりを R2 とすると、x を P で払ったおつり R
は R = R1 ⊕ R2 となる。

R1 は P にはよらないので、結局 P は、(njn (X)jn + jn ) の支払い (とおつり R2 ) を最適にするものになる。
お札を一枚借りる場合も同じで、命題 5 よりお札を借りなくて済むのであればそういう解が最適なはずだし、よってお札を借りる解が最適の場合は、H が x には足りない場合なので、どのような解も札を 1 枚借りることになる。よって、それを硬貨と考えて最適解を求め、それを札に戻しても、他の解との関係性 (それが最適であるという関係) に変化はない。
また、この命題 10 のいう最適解は、命題 7 より一意的であることがわかる。すなわ
ち、x0 を支払う丁度の解か、そうでなければ jn より大きくて H に含まれる最も小さい額の硬貨 1 枚の極小解が最適解だということがわかる。つまり、これにより次の命
題 11 も証明できたことになる。

命題 11.

最適解は一意的であり、それ以外の解は必ず最適解より小銭の枚数が増えることになる。

例えば、この節の最初に上げた、x = 337 円、H が 544 円の場合は、x1 = 2 円に対しては Tot(P1 ) = 2 円が最適解。x2 = 35 円に対しては Tot(P2 ) = 40 円 が x02 = 40 円の最適解。x3 = 300 円に対しては Tot(P3 ) = 500 円 が最適解となる。よって、この場合の最適解は、支払いが P = P1 ⊕ P2 ⊕ P3 の 542 円で、おつり R が 205 円、となる。

9. 他の硬貨系について

921

他の硬貨系について

4 節で述べたように、これまでに見てきた命題は、通常の 1 円、5 円、10 円、. . . の硬貨系 (5–2 硬貨系と呼ぶ) 以外の (10) の形の硬貨系でも成り立つ。例えば、1 円、2 円、4 円、8 円、. . . (Nj = 2) の 2 進数の硬貨系等の n 進数の硬貨系、あるいは、12 進数を基本とした 6–2 硬貨系 (1 円、6 円、12 円、72 円、. . . ) や 3–4 硬貨系 (1 円、3 円、12 円、36 円、. . . ) なども作ることができる。
例えばアメリカのように、基本的に 5–2 硬貨系だけれども、基本となる額の 1/4 硬貨(25 セント硬貨) を入れているところもある。それは、実際には冗長 (表現が一意にならない) でややこしいのだが、便利な場合もあるらしい。なお、日本の 5–2 硬貨系だと 25 円硬貨を入れると冗長で一意性がなくなるが、例えば 10 円硬貨等を除いて、• 1 円、5 円、25 円、50 円、100 円、500 円• 1 円、5 円、25 円、50 円、250 円、500 円のようにすれば一意性のある硬貨系となる。
さらに、イギリス (やユーロ) では、歴史的な経緯もあるらしいが、通常の 5–2 系に 2
ペンスや 20 ペンスなどの硬貨もあり、これも冗長である。例えば 1 円、2 円、5 円を考えると、1 円は 1 枚でいいが (2 枚あると冗長)、2 円は 4 円を表現するためには 2
枚なければいけない。しかし、そうすると 5 円が 2 円 2 枚と 1 円 1 枚でも表現されてしまうことになる。
さて、2 進数硬貨系などは、10 進数と 2 進数の変換をやらないといけないので、とても実用にはならないと思うかもしれないが、もし硬貨系が最初から 2 進硬貨系であれば、例えば両者での数字の併記であるとか、金額の計算には 10 進数を使わない等、2
進と 10 進の変換をやらずに生活する工夫がなされているはずだろう。だから、変換が面倒だろうから 2 進硬貨系はありえない、と考えるのは早計だと思う。

2 進硬貨系だと、1000 円未満の数字を表現するには、• 1、2、4、8、16、32、64、128、256、512の 10 種類の硬貨が必要になる。これも大変だと思うかもしれないが、2 進硬貨系では各硬貨は 2 枚以上持つ必要はなく、それぞれ 1 枚だけあればすべての金額が表現できる。つまり、財布の中の最大小銭枚数は 10 枚で済むことになる。
一方、通常の 5–2 系では、1 円、10 円、100 円は最大 4 枚、5 円、50 円、500 円は最
大 1 枚必要だから最大で合計 15 枚となり、2 進硬貨系よりむしろ 5–2 系の方が財布がふくらみやすいことになる。
ついでに他の硬貨系についても 1000 円未満の最大枚数を見てみると、

10. 最後に

22• 3 進硬貨系: 1, 3, 9, 27, 81, 243, 729
7 種類で、243 円までは 2 枚必要、729 円硬貨は 1 枚でよいので、最大 2×6+1 = 13枚。
• 6–2 硬貨系: 1, 6, 12, 72, 144, 864
6 種類で、1 円、12 円、144 円は 5 枚、6 円、72 円、864 円は 1 枚なので最大
5 × 3 + 1 × 3 = 18 枚
• 3–4 硬貨系: 1, 3, 12, 36, 144, 432
6 種類で、1 円、12 円、144 円は 2 枚、3 円、36 円は 3 枚、432 円は 1 枚でよ
いので、最大 2 × 3 + 2 × 3 + 1 = 13 枚。
• 1 円、5 円、25 円、50 円、100 円、500 円:
1 円、5 円、100 円が 4 枚、25 円、50 円、500 円は 1 枚なので、最大 4×3+3 = 15枚。
• 1 円、5 円、25 円、50 円、250 円、500 円:
1 円、5 円、50 円が 4 枚、25 円、250 円、500 円は 1 枚なので、最大 4×3+3 = 15枚。
• 10 進系: 1, 10, 100
3 種類だがそれぞれ最大 9 枚なので 27 枚。
これを見ても、2 進硬貨系の 10 枚が少ないことがわかる。もちろん、現在の 10 進数の日常から 2 進硬貨系に切りかえるのはほぼ不可能であるが、それなりに優れたところもあるように思う。
ちなみに、5–2 系の逆の 2–5 系 (1, 2, 10, 20, 100, 200 円硬貨) の場合も最大は 15 枚となるし、例えば 5 円玉だけを 2 円玉に変えるといった場合も同じになるが、便利さ
や計算しやすさ、また平均的な小銭の枚数などには、もしかしたら違いが出てくるかもしれない。

1 円玉を 1 枚作るのに、実際は 1 円以上必要だと何かで見たような気がするが、もしそうだとすると、5 円玉の代わりに 2 円玉を使うようにすると、1 円玉の流通量はずっと少なくすることができるだろう。

10

最後に

本稿で、小銭を最小化する支払い方について見てきた。結局、下の額から硬貨と値段を見比べて、命題 8 のように分割し、分割できない単位については大きな硬貨で払う、という解が最適で、しかもそれは一意的である、ということを示すことができた。

10. 最後に

23

この分割は、10 円未満や 100 円未満のような単位で発生する場合には割と考えやすいが、5 円未満、50 円未満、という単位で発生した場合にはとっさには考えにくいかもしれない。しかし、馴れてしまえばそれほどでもなく、割と容易に最適解は求められることが多い。実際、本稿に上げたような命題や方法を知らなくても、普段から無意識のうちにこのような最適解を支払っている人も少なくないだろうと思う。
なお、本稿のような話は多くの人がよく考える話題なので、私がちゃんと探していな
いだけで、本稿で述べた証明なども既にどこかにはあるのだろうと思う。また、私は数論や離散数学の専門家ではないので、本稿にある長い証明などは、本当はもっとシンプルにできるのかもしれない。