Yamagishi Complexity Torus LabYamagishi Lab

[Paper 633] Paying Largest Coins First Always Uses the Fewest Coins in Yen, but One Too Many at 48 Pence in Old British Coins

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.

Scope (what is not claimed)

No new theorem or law is claimed——that some coin sets make the greedy method miss the fewest coins, that the first miss comes before the sum of the two largest coins (Kozen and Zaks, $1994$), and the one-point test for adding a coin (Magazine, Nemhauser and Trotter, $1975$) are all known. The one-point test is not proved——it is only matched against the check of every amount for six additions. The design of coin sets and the history of coins are not discussed. Relation to earlier papers: Paper 348 showed that on the same graph the greedy method is optimal for spanning trees and misses for tours——there the problem decided success; here, within the same change-making problem, the set of coins decides it. What is added is checking nine sets at every amount up to $20000$, counting how the missing sets miss (how often, and by only one coin), and matching the one-point test with the check of every amount, placing the separator on whether the added coin fits the earlier set.

1. Notation and the Question

Setting: a set of coins is fixed and an amount $n$ is paid. The greedy method takes the largest coin as often as possible, then the next. Its count is $G(n)$ and the fewest coins $M(n)$. $M(n)$ was found for every amount from $1$ to $20000$ by dynamic programming, building up from small amounts “one coin plus the fewest for the rest”. An amount with $G(n)>M(n)$ is called a miss.

Question: which sets miss, and what happens when they do?

2. Sets That Never Miss

Computation 2.1: $G(n)$ and $M(n)$ were compared at every amount from $1$ to $20000$.

set of coinsmissessum of two largest
yen coins $1,5,10,50,100,500$$0$$600$
yen coins and notes (up to $1000,2000,5000,10000$)$0$$15000$
US $1,5,10,25$$0$$35$
$1,3$$0$$4$
old British $1,3,6,12,24$$0$$36$
$1,5,10,20$$0$$30$

Observation 2.2 if a set misses, its first miss comes before the sum of its two largest coins (Kozen and Zaks). Every sum here is below $20000$, so not missing up to $20000$ means not missing at any amount——yen coins and notes pay every amount with the fewest coins.

3. Sets That Miss

Computation 3.1: by the same comparison, three sets missed.

set of coinsfirst missgreedyfewestmisses up to $20000$
$1,3,4$$6$$4+1+1$ (three)$3+3$ (two)$4999$
old British $1,3,6,12,24,30$$48$$30+12+6$ (three)$24+24$ (two)$3993$
$1,5,10,20,25$$40$$25+10+5$ (three)$20+20$ (two)$3995$

Each first miss came before the sum of the two largest coins ($7$, $54$ and $45$). Wherever it missed, the greedy method used at most one coin more than the fewest, in every set. The old British set misses at every amount from $48$ to $53$ pence.

Observation 3.2 the greedy method spoils what follows by taking the largest coin. At $48$ pence, taking $30$ first leaves $18$, for which there is no single coin, so it needs at least two, three in all. Without the $30$, two $24$s pay it exactly——the larger coin cuts in between a pair of smaller coins.

4. Adding One Coin

Computation 4.1: one coin was added to a set that never misses, and the one-point test (with added coin $c$, earlier largest $c_k$ and $m=\lceil c/c_k\rceil$, whether the greedy count for $mc_k$ is at most $m$) was compared with the check of every amount up to $20000$ (up to $2000$ for the small sets).

coin added to the earlier set$m$amount checkedgreedy countverdict (one point, every amount)
$4$ to $1,3$$2$$6$$3$misses, misses
$30$ to old British $1,\ldots,24$$2$$48$$3$misses, misses
$25$ to $1,5,10,20$$2$$40$$3$misses, misses
$2000$ to yen (up to $1000$)$2$$2000$$1$never, never
$5000$ to yen (up to $2000$)$3$$6000$$2$never, never
$10000$ to yen (up to $5000$)$2$$10000$$1$never, never

Observation 4.2 this is the core: whether a set misses is decided by whether the added coin fits the earlier set, and that shows at one point. The British $30$ sits below $48$, twice $24$, and makes $48$ start with $30$ and take three coins. The yen $5000$ pays $6000$, three times $2000$, as $5000+1000$, two coins, fewer than three——the same “largest first” is right or wrong depending on where the added coin sits.

5. The Separator

Observation 5.1 the separator is whether the added coin fits the earlier set. If it fits, the greedy method gives the fewest at every amount; if not, missing amounts appear. Whether it fits is decided at the single point $mc_k$——not the number of coins or the size of amounts, but the joint of the set is what matters.

Observation 5.2 beside Paper 348. In Paper 348, on the same graph, spanning trees were optimal by the greedy method and tours were missed; the kind of problem decided success——here, within the same change-making problem, the set of coins decides it. And even when it missed, it was by only one coin.

Observation 5.3 what is not said. The design of coin sets and the history of coins are not discussed, and the one-point test is not proved——what is shown is the check of every amount for nine sets, and the agreement of the one-point test with it for six additions.

6. Roll Call and Closing

  1. yen coins and notes never miss (Computation 2.1): at every amount up to $20000$.
  2. misses come before the sum of the two largest (Observation 2.2): so it holds at every amount.
  3. old British with $30$ misses at $48$ (Computation 3.1): three coins against two.
  4. $1,3,4$ at $6$, $1,5,10,20,25$ at $40$ (Computation 3.1): the same kind of miss.
  5. missing by only one coin (Computation 3.1): up to $20000$.
  6. the large coin cuts in (Observation 3.2): $30$ breaks $24+24$.
  7. adding one coin can make a set miss (Computation 4.1): three examples.
  8. adding notes to yen never misses (Computation 4.1): $2000$, $5000$ and $10000$.
  9. one point agrees with every amount (Observation 4.2): the core.
  10. the set, not the problem, decides (Observation 5.2): Paper 348.

Closing: Paying the largest coins first gave the fewest coins at every amount up to $20000$ for yen coins and notes and for US coins, and since a set that misses does so before the sum of its two largest coins, these never miss at any amount. Adding the half crown of $30$ to the old British $1$, $3$, $6$, $12$ and $24$ pence pays $48$ pence as $30+12+6$, three coins, more than the two of $24+24$. Whether a set misses is decided by whether the added coin fits the earlier set, and shows at the single point of $m$ times the earlier largest coin——for six additions, the one-point test agreed with the check of every amount. The separator is whether the added coin fits the earlier set. Placed among the earlier papers——in Paper 348 the problem decided the success of the greedy method; here, within one problem, the set of coins decides it. To be honest——neither the proof of the one-point test nor the design of coin sets is entered.

References

  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. Yamagishi, Y. (2026). On the Same Graph, Connecting Is Cheap and Ordering Is Not [Paper 348]. Zenodo. 10.5281/zenodo.22683555

Reference

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
ORCID: 0009-0006-8587-3450

PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS

The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 633. This paper is a preprint and has not been peer reviewed.