Yamagishi Complexity Torus Lab山岸勇輝ラボ

【論文633】大きい硬貨から払う両替は、円なら必ず最少枚数だが、旧英貨では 48 ペンスで一枚多くなる

要旨

額を払うのに、硬貨を大きい順に払えるだけ払う方法(貪欲法)を、最少枚数(動的計画法で全額を数えたもの)と比べる。どの硬貨の組で外れ、外れるときは何が起きているかを数える。新しい定理も法則も主張しない。

第一に、円では外れない。円の硬貨($1$・$5$・$10$・$50$・$100$・$500$)に札($1000$・$2000$・$5000$・$10000$)を加えても、米国の硬貨($1$・$5$・$10$・$25$)でも、$1$ から $20000$ までのどの額でも最少枚数になった。外れるなら最初の外れは大きい二枚の和より前に来ること(コーゼンとザクス)が知られており、円の札まで入れても $15000$ なので、全額について外れない(第2節)。

第二に、旧英貨に半クラウンを足すと、$48$ ペンスで外れる。十進法より前の英国の $1$・$3$・$6$・$12$・$24$ ペンスは外れないが、半クラウン $30$ ペンスを足すと、$48$ ペンスを $30+12+6$ の三枚で払い、$24+24$ の二枚より多い。$20000$ までに $3993$ 通りの額で外れ、どれも一枚多いだけだった。$1$・$3$・$4$ の組は $6$ で、$1$・$5$・$10$・$20$・$25$ の組は $40$ で外れる(第3節)。

第三に、これが本稿の芯である。外れない組に一枚足すと、外れる組になりうる。$1$・$3$ に $4$ を、旧英貨に $30$ を、$1$・$5$・$10$・$20$ に $25$ を足すと、どれも外れる組になった。円に $2000$・$5000$・$10000$ の札を順に足しても、外れないままだった(第4節)。

第四に、外れるかどうかは一点で分かる。足す硬貨 $c$ を前の組の最大で割って切り上げた数を $m$ とし、$m$ 倍した前の最大の額だけを貪欲法で払ってみる。$m$ 枚を超えれば外れる組、超えなければ外れない組である(マガジン、ネムハウザー、トロッターの一点の判定)。六つの足し方すべてで、この一点の判定が $20000$ までの全額の判定と一致した(第4節)。

キーワード:両替問題、貪欲法、最少枚数、硬貨の体系、旧英貨。

射程(何を示さないか)

新しい定理も法則も主張しない。貪欲法が最少枚数から外れる硬貨の組があること、外れるなら最初の外れが大きい二枚の和より前に来ること(コーゼンとザクス、$1994$)、一枚足すときの一点の判定(マガジン、ネムハウザー、トロッター、$1975$)は、いずれも既知である。一点の判定を証明しない。六つの足し方で全額の判定と突き合わせただけである。硬貨の組の設計の是非や、硬貨の歴史は論じない。既刊との関係:論文348 は、同じグラフの上で、全域木では貪欲法が最適になり、巡回路では外れることを示した。そこでは問題が成否を分けた。ここでは同じ両替の問題の中で、硬貨の組が成否を分ける。加えたのは、九つの組を $20000$ まで全額で調べたこと、外れる組の外れ方(数と、一枚多いだけであること)を数えたこと、一点の判定を全額の判定と突き合わせ、分離子を「足した一枚が前の組に合うか」に置いたことである。

1. 記法と問い

設定:硬貨の組を決め、額 $n$ を払う。貪欲法は、硬貨を大きい順に、払えるだけ払う。その枚数を $G(n)$、最少枚数を $M(n)$ とする。$M(n)$ は、小さい額から順に「一枚使って残りを最少で払う」を積み上げる動的計画法で、$1$ から $20000$ までのすべての額について求めた。$G(n)>M(n)$ となる額を「外れ」と呼ぶ。

問い:どの組で外れるか。外れるとき、何が起きているか。

2. 外れない組

計算 2.1:$1$ から $20000$ までのすべての額で、$G(n)$ と $M(n)$ を比べた。

硬貨の組 外れる額 大きい二枚の和
円の硬貨 $1,5,10,50,100,500$ $0$ 通り $600$
円の硬貨と札($1000,2000,5000,10000$ まで) $0$ 通り $15000$
米国 $1,5,10,25$ $0$ 通り $35$
$1,3$ $0$ 通り $4$
旧英貨 $1,3,6,12,24$ $0$ 通り $36$
$1,5,10,20$ $0$ 通り $30$

観察 2.2 外れるなら、最初の外れは大きい二枚の和より前に来る(コーゼンとザクス)。どの組も、この和は $20000$ より小さいので、$20000$ まで外れないことは、どの額でも外れないことを意味する。円の硬貨と札は、全額について最少枚数で払える。

3. 外れる組

計算 3.1:同じ比べ方で、三つの組が外れた。

硬貨の組 最初の外れ 貪欲法 最少 $20000$ までの外れ
$1,3,4$ $6$ $4+1+1$(三枚) $3+3$(二枚) $4999$ 通り
旧英貨 $1,3,6,12,24,30$ $48$ $30+12+6$(三枚) $24+24$(二枚) $3993$ 通り
$1,5,10,20,25$ $40$ $25+10+5$(三枚) $20+20$(二枚) $3995$ 通り

最初の外れは、どれも大きい二枚の和($7$・$54$・$45$)より前に来た。外れる額で貪欲法が最少より多く使うのは、どの組でも最大で一枚だった。旧英貨では $48$ から $53$ ペンスまで続けて外れる。

観察 3.2 貪欲法は、一番大きい硬貨を取ったせいで、あとの払い方を悪くする。$48$ ペンスでは、まず $30$ を取ると、残り $18$ に当たる硬貨は無いので、どう払っても二枚は要り、合わせて三枚になる。$30$ を取らなければ、$24$ が二枚でちょうど払える。大きい硬貨が、二枚で一組の小さい硬貨の間に割り込んでいる。

4. 一枚足す

計算 4.1:外れない組に一枚足し、一点の判定(足す硬貨 $c$、前の最大 $c_k$、$m=\lceil c/c_k\rceil$ として、$mc_k$ を貪欲法で払った枚数が $m$ 以下か)と、$20000$ まで(小さい組は $2000$ まで)の全額の判定を比べた。

前の組に足す硬貨 $m$ 見る額 貪欲法の枚数 判定(一点・全額)
$1,3$ に $4$ $2$ $6$ $3$ 外れる・外れる
旧英貨 $1,\ldots,24$ に $30$ $2$ $48$ $3$ 外れる・外れる
$1,5,10,20$ に $25$ $2$ $40$ $3$ 外れる・外れる
円($1000$ まで)に $2000$ $2$ $2000$ $1$ 外れない・外れない
円($2000$ まで)に $5000$ $3$ $6000$ $2$ 外れない・外れない
円($5000$ まで)に $10000$ $2$ $10000$ $1$ 外れない・外れない

観察 4.2 これが本稿の芯である。外れるかどうかは、足した一枚が前の組に合うかで決まり、それは一点で分かる。旧英貨の $30$ は $24$ の二倍の $48$ より手前にあり、$48$ を $30$ から払い始めさせて三枚にする。円の $5000$ は $2000$ の三倍の $6000$ を $5000+1000$ の二枚で払わせ、三枚より少ない。同じ「大きい順」が、足した一枚の置き場所で、正しくも誤りにもなる。

5. 分離子

観察 5.1 分離子は、足した一枚が前の組に合うかどうかである。合えば貪欲法は全額で最少、合わなければ外れる額が現れる。合うかどうかは、$mc_k$ の一点で決まる。硬貨の枚数や額の大きさではなく、組の合わせ目が効く。

観察 5.2 論文348 と並べる。348 では、同じグラフで、全域木は貪欲法で最適になり、巡回路は外れた。成否を分けたのは問題の種類だった。ここでは同じ両替の問題で、成否を分けるのは硬貨の組である。そして外れても一枚多いだけだった。

観察 5.3 言わないこと。硬貨の組の設計の是非や、硬貨の歴史は論じない。一点の判定も証明しない。示したのは、九つの組の全額の比べと、六つの足し方での一点の判定と全額の判定の一致である。

6. 点呼と結び

  1. 円の硬貨と札は外れない(計算 2.1):$20000$ まで全額で。
  2. 大きい二枚の和より前に外れる(観察 2.2):だから全額について言える。
  3. 旧英貨+$30$ は $48$ で外れる(計算 3.1):三枚対二枚。
  4. $1,3,4$ は $6$、$1,5,10,20,25$ は $40$(計算 3.1):同じ外れ方。
  5. 外れても一枚多いだけ(計算 3.1):$20000$ まで。
  6. 大きい硬貨が割り込む(観察 3.2):$30$ が $24+24$ を壊す。
  7. 外れない組に一枚足すと外れうる(計算 4.1):三つの例。
  8. 円に札を足しても外れない(計算 4.1):$2000$・$5000$・$10000$。
  9. 一点の判定=全額の判定(観察 4.2):本稿の芯。
  10. 問題でなく組が成否を分ける(観察 5.2):論文348。

結び:硬貨を大きい順に払う貪欲法は、円の硬貨と札、米国の硬貨では、$20000$ までのどの額でも最少枚数になり、外れるなら大きい二枚の和より前に外れるので、全額について外れない。旧英貨の $1$・$3$・$6$・$12$・$24$ ペンスに半クラウン $30$ を足すと、$48$ ペンスを $30+12+6$ の三枚で払い、$24+24$ の二枚より多くなる。外れるかどうかは、足した一枚が前の組に合うかで決まり、$m$ 倍した前の最大の一点で分かる。六つの足し方で、一点の判定が全額の判定と一致した。分離子は、足した一枚が前の組に合うかどうかである。既刊との位置、論文348 では問題が貪欲法の成否を分けたが、ここでは同じ問題の中で硬貨の組が分ける。正直に言えば、一点の判定の証明にも、硬貨の組の設計にも入っていない。

参考文献

  1. Kozen, D., & Zaks, S. (1994). Optimal bounds for the change-making problem. Theoretical Computer Science.
  2. Magazine, M. J., Nemhauser, G. L., & Trotter, L. E. (1975). When the greedy solution solves a class of knapsack problems. Operations Research.
  3. 山岸勇輝 (2026). 『同じグラフで、繋ぐのは安く、並べるのは高い』[論文348]. Zenodo. 10.5281/zenodo.22683555

作成にあたって:本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI(大規模言語モデル)の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。

書誌

山岸勇輝(2026)「大きい硬貨から払う両替は、円なら必ず最少枚数だが、旧英貨では 48 ペンスで一枚多くなる」[論文633]. Zenodo.
DOI: 10.5281/zenodo.23014568

YOI 633第1版・2026年9月ビットコインに記録済み

日付の証拠(OpenTimestamps):日本語版の .ots・英語版の .ots・SHA256SUMS

予備の置き場所(ミラー。中身は上と同じです):PDF 日本語・PDF English・SHA256SUMS

住所:https://www.yamagishiyuuki.com/yoi/633・DOI 10.5281/zenodo.23014568・CC BY 4.0・プレプリント(査読を経ていません)・ORCID 0009-0006-8587-3450

引用するとき

山岸勇輝 (2026). 大きい硬貨から払う両替は、円なら必ず最少枚数だが、旧英貨では 48 ペンスで一枚多くなる [論文633]. YOI: https://www.yamagishiyuuki.com/yoi/633 ・ DOI: 10.5281/zenodo.23014568

Yamagishi, Y. (2026). Paying Largest Coins First Always Uses the Fewest Coins in Yen, but One Too Many at 48 Pence in Old British Coins [Paper 633]. YOI: https://www.yamagishiyuuki.com/yoi/633; DOI: 10.5281/zenodo.23014568

@misc{yamagishi2026yoi633,
  author = {Yamagishi, Yuuki},
  title = {Paying Largest Coins First Always Uses the Fewest Coins in Yen, but One Too Many at 48 Pence in Old British Coins},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/633},
  doi = {10.5281/zenodo.23014568},
  note = {Preprint, edition 1}
}
指紋(SHA-256)と確かめ方
7ada1c331d2d9b1a2495396ef04e12d93589b4ff9ad19ab05835772bea9a5067 yamagishi_yoi633_v1_jp.pdf
4c57795b7f84ff7a2dbd4e6eae2c9c9f6eff4a52e6ba5e0292d8dad9ffac1bc3 yamagishi_yoi633_v1_en.pdf

PDF と .ots を同じ場所に保存し、opentimestamps.org に .ots、続けて PDF を落とすと、記録された日時が表示されます。PDF が 1 バイトでも変わっていれば通りません。