But this is not the problem I want to talk about. I want to think about countries that are moderately less silly. They will always have coins to make any amount of change (this is equivalent to always having 1 cent pieces). But the observation I seek to generalize is the following:
With [common] US coins, it is possible to have $1.19 in change, but not be able to make change for a dollar (i.e., 3 quarters, 4 dimes, and 4 pennies).
I want to imagine a country where a dollar is worth d pennies, and to investigate the worst choice of denominations for coins, so that a person can have a lot of money in coins, but not make change for a dollar. I also impose the following restrictions:
1. The country has at most 4 denominations of coin.
2. Each denomination of coin divides the value of a dollar.
I wrote a short Python script to solve this. It turns out that as long as you have 4cent and 25cent pieces, you can hold $1.71 without being able to make change for a dollar.
The first time you get over $5 in coins is when 1 dollar = 210 cents, then if you have pennies, 30, 35, and 42 cent pieces, you can have $5.23 in coins without being able to break a dollar. Similarly, if 1 dollar = 396 cents, you can have $10.09 in coins, if coins have value 1,36,44 and 99.
I have put a plot below. It reminds me vaguely of the plot of Euler’s totient function, and certainly a thorough description of a solution to this should have to do with how many factors the denominations of coins have, but I certainly do not have a rigorous explanation for why these two plots look similar. The points along the bottom correspond to prime numbers, where condition 2 requires that we only have pennies.