おつりでフラクタル

この記事は 明日話したくなる数学豆知識アドベントカレンダー の 18日目の記事です。(17日目:正十七角形は作れる )

たしか2年くらい前にこんなコピペが流行った(おそらく初出はこれ?):

コンビニで代金が777円だったとき。
777円の表示を見たバイトの兄ちゃんが「おーっ」とか言ってるので、
すかさず1332円出した。
キョトンとしてるので、「まあいいからレジ売ってみな」言ってやった。
レジには釣り555円の表示。
バイトの兄ちゃん絶叫してた。

さすがにここまできれいなおつりのもらい方をしたことはないが,財布の小銭が少なくなるような支払いはほとんどの人が日常的に行っているのではないだろうか.このようなおつりの計算方法は欧米では困惑されるという話をよく聞くが,この違いは等価交換の考え方の違いによるらしい(日本と西洋のお釣りの計算方法と等価交換).

それはさておき,今から2年前の2012年,現在中央大学理工学部の山本健氏の"Fractal behind coin-reducing payment"という論文が Chaos, Solitons & Fractals という学術雑誌に掲載された.日本語にすると「硬貨を減少させる支払い方でのフラクタル」となる.実はお金の支払い方にフラクタルが潜んでいるのである.

小銭支払の達人が,1000円未満の買い物を延々と繰り返すことを考える.ただし,所持金が足りない時は1000円札がどこからともなく現れるとする.小銭支払の達人なので,おつりの数字を時系列に見ていくと,500円,あるいは100円といったきりのいい数字が多くなる.そこで, n回目の買い物でのおつりを横軸に, n+1回目の買い物でのおつりを縦軸にして赤いしるしを打っていくと,なんと次のようになる(図は論文より):

f:id:End01nojo:20141218131501p:plain

図の右上には典型的なフラクタル図形であるシェルピンスキーのギャスケットが示されているが,そっくりである.

ではなぜこのようなフラクタル図形になるかを説明しよう.まず,最適支払手法は次の2ステップで表される:

(1) 会計後の所持金を最小枚数の小銭で表す.

(2) 最小枚数で表した会計後の小銭を現在の小銭と比較し,減る硬貨が会計で使用する硬貨に,増える硬貨はおつりに対応する.

一つ例を挙げよう.今682円持っているとし,117円の買い物をしたとする.会計後の所持金は682-117=565円である.565円を500円玉,100円玉,50円玉,10円玉,5円玉,1円玉の枚数で表すと,

( 1, 0, 1, 1, 1, 0)

となる.一方,現在の所持金682円は枚数で表すと

( 1, 1, 1, 3, 0, 2)

である.比較すると

( 0,-1, 0,-2,+1,-2)

である.よって122円支払って5円玉1枚を受け取るのが最適支払となる.

おつりの時系列をもう少し詳しく見るため,10円玉の枚数に着目しよう. t回目の会計前の10円玉の枚数を n(t)とし, t回目の会計でもらうおつりを c(t)とする.上のアルゴリズムより,

 c(t) = \mathrm{max} \{ n(t) - n(t-1), 0 \}

である. c(t)+c(t+1)を考えると,

 \begin{eqnarray} c(t)+c(t+1) &=& \mathrm{max} \{ n(t) - n(t-1), 0 \} + \mathrm{max} \{ n(t+1) - n(t) , 0 \} \\ &=& \mathrm{max} \{ n(t+1) - n(t-1), n(t)-n(t-1), n(t+1)-n(t), 0 \} \end{eqnarray}

となる.最適支払を続けている限り,10円玉の枚数は4枚を超えない.つまり各 t 0 \le n(t) \le 4である.これと上の式を考えると

 0 \le c(t)+c(t+1) \le 4

となる.この条件を図で示すと,連続するおつりの組み合わせは図の赤色のマスでなくてはならないことになる:

f:id:End01nojo:20141218134819p:plain

今の話は10円玉を1円玉,100円玉に置き換えても全く同じである.5円玉,50円玉,500円玉の場合には,それぞれの最大枚数は1枚,つまり 0 \le n(t) \le 1であるので,

 0 \le c(t)+c(t+1) \le 1

となる.図で示すと次のようになる:

f:id:End01nojo:20141218135601p:plain

これでフラクタル図形の準備はできた.連続するおつりのプロットでは,横軸も縦軸も0円から999円までである.これを500円玉の枚数で見ると,0円から499円までが0枚,500円から999円までが1枚となる.これに今示した条件を重ねると次のようになる:

f:id:End01nojo:20141218141439p:plain

次に,100円玉の枚数で見ると,金額100円ごとに1枚増え,0枚,1枚,2枚,3枚,4枚,0枚,1枚,2枚,3枚,4枚となっている.全体を4分割すると上で見たマスの塗り方が適用できる.この条件は全ての硬貨で成り立っていないといけないのですでに500円玉の条件で除外された領域は外す.ごちゃごちゃ言うよりも結果を見る方が早い:

f:id:End01nojo:20141218141843p:plain

すでにその形が見えてきた.今度は50円玉の条件を適用してみる:

f:id:End01nojo:20141218142004p:plain

これにさらに10円玉,5円玉,1円玉のルールを適用すると論文の図になる.キーポイントは硬貨を価格順に並べたとき,整数倍になっていることである.このおかげで一つ下の硬貨のルールを適用する際にきれいな分割ができることになる.逆に言うと,この硬貨の倍数性が成り立っていない貨幣体系ではフラクタルにならない.例えばドルの場合の硬貨は50セント,25セント,10セント,5セント,1セントであるが,25セントは10セントの整数倍ではない.連続おつりプロットを書くと,微妙に崩れた形になってしまう(図は論文より):

f:id:End01nojo:20141218142542p:plain

一時日本で2000円札と言うものがあったが,これがあると札の系列が10000円,5000円,2000円,1000円となって倍数性が崩れてしまう.やはり廃れて正解だったようだ.