要旨
額を払うのに、硬貨を大きい順に払えるだけ払う方法(貪欲法)を、最少枚数(動的計画法で全額を数えたもの)と比べる。どの硬貨の組で外れ、外れるときは何が起きているかを数える。新しい定理も法則も主張しない。
第一に、円では外れない。円の硬貨($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. 点呼と結び
- 円の硬貨と札は外れない(計算 2.1):$20000$ まで全額で。
- 大きい二枚の和より前に外れる(観察 2.2):だから全額について言える。
- 旧英貨+$30$ は $48$ で外れる(計算 3.1):三枚対二枚。
- $1,3,4$ は $6$、$1,5,10,20,25$ は $40$(計算 3.1):同じ外れ方。
- 外れても一枚多いだけ(計算 3.1):$20000$ まで。
- 大きい硬貨が割り込む(観察 3.2):$30$ が $24+24$ を壊す。
- 外れない組に一枚足すと外れうる(計算 4.1):三つの例。
- 円に札を足しても外れない(計算 4.1):$2000$・$5000$・$10000$。
- 一点の判定=全額の判定(観察 4.2):本稿の芯。
- 問題でなく組が成否を分ける(観察 5.2):論文348。
結び:硬貨を大きい順に払う貪欲法は、円の硬貨と札、米国の硬貨では、$20000$ までのどの額でも最少枚数になり、外れるなら大きい二枚の和より前に外れるので、全額について外れない。旧英貨の $1$・$3$・$6$・$12$・$24$ ペンスに半クラウン $30$ を足すと、$48$ ペンスを $30+12+6$ の三枚で払い、$24+24$ の二枚より多くなる。外れるかどうかは、足した一枚が前の組に合うかで決まり、$m$ 倍した前の最大の一点で分かる。六つの足し方で、一点の判定が全額の判定と一致した。分離子は、足した一枚が前の組に合うかどうかである。既刊との位置、論文348 では問題が貪欲法の成否を分けたが、ここでは同じ問題の中で硬貨の組が分ける。正直に言えば、一点の判定の証明にも、硬貨の組の設計にも入っていない。
参考文献
- Kozen, D., & Zaks, S. (1994). Optimal bounds for the change-making problem. Theoretical Computer Science.
- Magazine, M. J., Nemhauser, G. L., & Trotter, L. E. (1975). When the greedy solution solves a class of knapsack problems. Operations Research.
- 山岸勇輝 (2026). 『同じグラフで、繋ぐのは安く、並べるのは高い』[論文348]. Zenodo. 10.5281/zenodo.22683555
作成にあたって:本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI(大規模言語モデル)の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。
書誌
山岸勇輝(2026)「大きい硬貨から払う両替は、円なら必ず最少枚数だが、旧英貨では 48 ペンスで一枚多くなる」[論文633]. Zenodo.
DOI: 10.5281/zenodo.23014568
日付の証拠(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.pdf4c57795b7f84ff7a2dbd4e6eae2c9c9f6eff4a52e6ba5e0292d8dad9ffac1bc3 yamagishi_yoi633_v1_en.pdfPDF と .ots を同じ場所に保存し、opentimestamps.org に .ots、続けて PDF を落とすと、記録された日時が表示されます。PDF が 1 バイトでも変わっていれば通りません。