Coin Denominations
by Tom Temple
2 February 2009
In a desperate effort to stem inflation President Imajarhead of Iran is issuing a new currency. For whatever reason, it is very important to him that he can make all possible change denomitations, from one centiroentgen up to ninety-nine, using at most two coins. His first idea was to have a one cR coin and then all of the evens. Although the person who told him that this was sub-optimal has been imprisoned, he had the sense to contact you, the well known Mathematician, to determine a set of denominations that requires the fewest distinct coins. What are they?
Bonus. Impressed by your quick success on the Iran job, the government of Japan contacts you to determine a minimum set for 1 to 999 rin.
Also, I’ve posted the solution to last weeks puzzle. Congrats to Liz for solving it and retaining a shred of her previous sanity.
Feb 2, 06:21 PM
I’m much better at finding ambiguities in the statement of these puzzles than I am at solving them, Tom.
I might read this to mean that you want the smallest set of denominations that can produce every amount from 1 to 99. Which of course only requires having the 1 cR coin.
The other possibility is that you want the set of coin denominations that minimizes the number of coins needed to produce any amount of money from 1 to 99 cR. Even here I’m assuming that you intend to provide equal weight to every value from 1 to 99 cR, so that we will compare solutions by the average number of coins needed to construct each amount of money. And if that’s the case, it’s not obvious to me that this has a unique solution. Which probably just means that proving that the solution is unique should be a bonus problem.
Feb 2, 06:26 PM
I’m much better at finding ambiguities in the statement of these puzzles than I am at solving them, Tom.
I might read this to mean that you want the smallest set of denominations that can produce every amount from 1 to 99. Which of course only requires having the 1 cR coin.
The other possibility is that you want the set of coin denominations that minimizes the number of coins needed to produce any amount of money from 1 to 99 cR. But that is also silly, because then we just say that we need 99 denominations.
You need to specify the loss function for a solution. Which will be arbitrary. For instance, it might have the form (Ave # of coins to make 1-99) + lambda * # of denominations. What’s lambda?
And in any case, it’s not obvious to me that this has a unique solution for loss functions of this form. Which probably just means that proving that the solution is unique should be a bonus problem.
Feb 2, 06:54 PM
Let S be the set of coin values.
loss function: cardinality of S
constraint: for any n in 1..99 we must have n = a + b for some a and b in S, not necessarily distinct.
Better?
Feb 2, 07:53 PM
Much better. Sorry for the mult posts, I was having captcha problems.
Do I get credit for just saying “Goldbach’s conjecture?” Or can we do better than that?
Feb 2, 08:23 PM
Nope, I can do better.
I can get the 99 version down to 17 denominations, which I think is optimal. To do the 999 version I’ll need to formalize my reasoning more…
Feb 2, 08:44 PM
Jesus, I can’t count, it’s 18.
And I think the 999 version is 61.
And my solutions are not unique; I’ve found 6 for 99 and something like 9 for 999.
Feb 2, 09:39 PM
Does anyone think they can beat 18 (and 61)?
Joran, are you including a zero coin? I’m hoping no. For instance, it is just fine to make one cR with a single, 1cR coin. Imajarhead doesn’t want all numbers possible with exactly two coins, but rather with at most two coins.
Feb 2, 09:54 PM
I wasn’t including a zero coin. In particular, I was assuming that I could form, say, 97, with a single 97 cR coin.
But I don’t blame you for worrying; I’m just that nit-picky.
Feb 4, 02:13 AM
Can you have coins with negative face values?
Feb 4, 08:19 AM
Jon, I was waiting for Joran to ask that one. No, you can’t, because people would lose them.