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

論文633 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/633 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。Zenodo でも公開しています（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}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969434・969435・969440・969461 に記録されました（2026年10月01日 18:16（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

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

第一に、円では外れない。円の硬貨（$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節）。

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

Abstract

Paying an amount by taking the largest coin as often as possible, then the next (the greedy method), is compared with the fewest coins (found for every amount by dynamic programming).Which sets of coins make it miss, and what happens when it does, are counted.No new theorem or law is claimed.

First, yen never misses、with yen coins ($1$, $5$, $10$, $50$, $100$, $500$) plus notes ($1000$, $2000$, $5000$, $10000$), and with US coins ($1$, $5$, $10$, $25$), every amount from $1$ to $20000$ was paid with the fewest coins. It is known that if a set misses, its first miss comes before the sum of its two largest coins (Kozen and Zaks); with the yen notes this sum is $15000$, so yen never misses at any amount (Section 2).

Second, adding the half crown to old British coins misses at $48$ pence、the pre-decimal British $1$, $3$, $6$, $12$ and $24$ pence never miss, but with the half crown of $30$ pence added, $48$ pence is paid as $30+12+6$, three coins against the two of $24+24$. Up to $20000$ it misses at $3993$ amounts, each time by just one coin. The set $1$, $3$, $4$ misses at $6$, and the set $1$, $5$, $10$, $20$, $25$ at $40$ (Section 3).

Third, and this is the core.Adding one coin to a set that never misses can make it miss、adding $4$ to $1$, $3$, adding $30$ to the old British set, and adding $25$ to $1$, $5$, $10$, $20$ all gave sets that miss. Adding the yen notes $2000$, $5000$ and $10000$ in turn kept yen from missing (Section 4).

Fourth, whether it misses shows at one point、let $m$ be the added coin $c$ divided by the earlier set’s largest coin, rounded up, and pay only $m$ times that largest coin by the greedy method. If it takes more than $m$ coins the set misses; if not, it never misses (the one-point test of Magazine, Nemhauser and Trotter). For all six additions, this one-point test agreed with the check of every amount up to $20000$ (Section 4).

Keywords: change-making problem, greedy algorithm, minimum number of coins, coin system, pre-decimal British coinage

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/633/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/633 はいつも最新の版を指します）。Zenodo の記録とは、Zenodo に上げる前の改訂のぶんだけ違うことがあります。

YOI の一覧へ