Why Think About Coins?
Nobody uses coins anymore. We tap, swipe, or scan our way through daily transactions and inflation has made their values too low to be useful on their own.
That makes this exploration purely academic—a thought exercise in design, particularly given the understanding that coins were invented for convenience.
You don’t see 13¢ or 7¢ coins. Denominations are chosen so we can cover everyday amounts efficiently. This leads to an interesting puzzle:
Given a fixed number of denominations, what are the “best” coin values to minimize the maximum number of coins you’d ever need to hand over for amounts between 1¢ and 99¢?
We’ll keep this within the decimal world and ignore the far superior but now-extinct British pound–shilling–penny system with 240 pennies to the pound.
The Puzzle
At one extreme, if you had only a penny coin (1¢), you could pay any amount, but you might need 99 of them.
At the other extreme, you could mint 99 different coins, one for each value from 1¢ to 99¢, and you’d always pay with just one coin. That’s efficient for the buyer but absurd for everyone else.
The sweet spot lies somewhere in the middle.
So, if the ability to do mental math is not an issue, what are the ideal coin denominations?
A Look at the U.S. System
The U.S. has five basic coin denominations: 1, 5, 10, 25, and 50 cents. With these, the worst-case payment is eight coins. For example, 94¢ or 99¢ requires eight coins.
But could we do better?
Suppose we replaced the half-dollar (50¢) with a 2¢ coin. Still five denominations, but now the worst case drops to seven coins.
Even more interesting: with just four coins — say 1¢, 5¢, 12¢, and 28¢ — the worst case falls to six coins. We're using fewer denominations and getting better efficiency!
European Union Values
Ignoring the 1 and 2 euro coins, the European Union mints 1, 2, 5, 10, 20 and 50 cent coins, using six instead of five denominations. The worst case number of coins you would need to give someone is six. That's better than the U.S. system even if the U.S. 50¢ coin was replaced by a 2¢ coin but no better if the U.S. system also used six denominations, keeping the 50¢ coin and adding a 2¢ coin.
Chinese Values
China's renminbi coins come in six denominations: ¥0.01, ¥0.02, ¥0.05, ¥0.1, ¥0.5 and ¥1. Since we're interested in values under 1, we' will ignore the ¥1 and have five denominations. This system is less efficient for this puzzle than either the EU or U.S. systems. In the worst case, you'd need eight coins. For example 0.99 = 0.5 + 0.1 + 0.1 + 0.1 + 0.1 + 0.05 + 0.02 + 0.02.
Patterns in Optimal Sets
We can identify multiple optimal sets for given sizes. For four denominations, in addition to {1, 4, 12, 28), there are many other setts that work as well, such as:
- {1, 4, 13, 29}
- {1, 6, 15, 26}
- {1, 7, 11, 38}
Each guarantees you’ll never need more than six coins.
We can compute sets that would give us the minimum number of coins we would need to hand over for any value between 1 and 99 for various numbers of denominations.
| Number of denominations | Minimum worst-case coins | Example set |
|---|---|---|
| 1 | 99 | {1} |
| 2 | 18 | {1, 8} |
| 3 | 9 | {1, 7, 18} |
| 4 | 6 | {1, 4, 13, 29} |
| 5 | 5 | {1, 2, 5, 19, 30} |
| 6 | 4 | {1, 2, 7, 19, 29, 32} |
| 7 | 4 | {1, 2, 3, 4, 9, 27, 41} |
Adding more denominations continues to reduce the maximum number of coins, but with diminishing returns.
A Historical Aside
The U.S. once experimented with different denominations: 2¢, 3¢, and even 20¢. None lasted long. In a purely mathematical sense, such denominations might have been more efficient than the ones we kept. At the very least, minting a 2¢ coin in place of a 50¢ coin would be more efficient and not confusing to most coin-using people.
From Puzzles to Algorithms
In computer science, this puzzle is a variant of the coin change problem.
- Classic coin change problem (minimization form): Given a set of coin denominations and a target amount, what is the minimum number of coins needed to make that amount?
- Our twist: We don’t just solve the problem once for a single target. Instead, we ask: which denominations should we pick in the first place to minimize the maximum number of coins needed across all targets from 1 to 99?
This shift turns a familiar dynamic programming problem into a problem of optimizing the denominations themselves.
Formulating as an Integer Linear Program (ILP)
We can express this optimization puzzle in ILP form:
Decision variables:
- Let \(x_{i,j}\) = number of coins of denomination \(i\) used to make amount \(j\).
- Let \(M\) = the maximum number of coins needed for any amount (the quantity we want to minimize).
Constraints:
1. Cover each amount: For each target value \(j\) in \(1 \dots 99\):
\[\sum_i d_i \cdot x_{i,j} = j\]
where \(d_i\) are the denominations we select.
2. Count coins: For each amount \(j\):
\[\sum_i x_{i,j} \leq M\]
3. Integrality: All \(x_{i,j}\) are nonnegative integers.
Objective: \[\min M\]
The tricky part is that the denominations \(d_i\) themselves are also variables (with constraints like \(d_1 = 1\) to ensure pennies exist). That makes this a combinatorial optimization problem: we are searching for both the structure of the coin set and the optimal bound on coin counts.
Summary
This puzzle explores the trade-off between simplicity (fewer denominations) and efficiency (fewer coins per transaction).
There are other optimizations one can explore:
- The minimum average number of coins for any value between 1..99.
- Denominations to minimize the number of coins you would need to carry to make any value between 1 and 99.
- If you're willing to accept change, the minimum number of coins involved in a transaction. For example. A 49¢ transaction can involve two coins: a 50¢ coin and a 1¢ coin in change.
The U.S. and European systems are familiar and functional, but are not isn’t mathematically optimal. If we were to redesign coinage from scratch and mathematical ability wasn't an issue, we could do better. Not that it matters, since coins are nearly obsolete.