A friend posed this to me today:
Devise an alternate set of denominations for coins and bank notes requiring a minimum number of denominations and such that any amount from $0.01 to $100 could be paid with four units of currency.
I’ve looked at this from another perspective before after it was discussed on Freakonomics but that has to do with minimizing the average number of coins needed and doesn’t go too much into the math.
What’s remarkable is that my friend nearly instantly came to an upper bound that isn’t huge and after hours five of us have failed to improve upon it. I’ll avoid stating that bound here for now, but will come back and add it to the comments in a bit if there is no traction.
Another interesting tidbit is that unlike U.S. denominations where a greedy algorithm can verify a minimal number of units that are required (take as many of the largest as you can, then as many of the next largest, etc.) denominations where the denominations aren’t multiples of each other don’t allow this. Making 15 in 12-5-1 shouldn’t be 12-1-1-1 — it should be 5-5-5. Even doing verification requires dynamic programming solutions.