Author |
Topic: Question of Denominations (Read 872 times) |
|
irrational
Junior Member
Gender: 
Posts: 52
|
 |
Question of Denominations
« on: Sep 25th, 2006, 10:21am » |
 Quote  Modify
|
Here is a problem, perhaps familiar to many of you, but nevertheless ...
Suppose that you have to give change for x US dollars and you want to minimize the number of bills (notes) you need to give. You follow the common strategy: you keep giving bills of highest denomination that does not make the total amount exceed x. For example, suppose that you need to give out change for $17 and the denominations available are $1, $5, $10, $20 and $50. Thus first you give $10, then $5 and then two $1 bills.
The question: Is this strategy always optimal? If yes, please prove it so.
A secondary question is: What is the most general condition the set of denominations should satisfy so that greedy always gives the optimal? (With proof, of course)
I culled this from another forum, since I felt that this needs interesting brains to think on it.
Again if this has already been asked my apologies, I tried to search and couldn't find anything like it.
Moderators, please feel free to move this to any forum you choose fit. 
|
|
 IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Question of Denominations
« Reply #1 on: Sep 25th, 2006, 10:38am » |
Quote Modify
|
I think I have seen this problem posted ont his forum before.. maybe mods can find it and post link to the discussion thread!!!
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Question of Denominations
« Reply #2 on: Sep 25th, 2006, 11:04am » |
Quote Modify
|
Note that in the given sequence of denominations every value is at least twice as big as the previous.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Question of Denominations
« Reply #3 on: Sep 25th, 2006, 3:31pm » |
Quote Modify
|
on Sep 25th, 2006, 10:38am, Sameer wrote:| I think I have seen this problem posted ont his forum before.. maybe mods can find it and post link to the discussion thread!!! |
|
I vaguely remember something similar, though it may not be the same puzzle. But either way, I'd just as soon have a new discussion, instead of linking back to an old unremembered one.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
irrational
Junior Member
Gender:
Posts: 52
|
|
Re: Question of Denominations
« Reply #5 on: Sep 26th, 2006, 8:18am » |
Quote Modify
|
After messing with this for a while and 2 advil's later....
I came to the conclusion that google.com and ask.com are my friends. So after innumerable scannings later:
for 4 bills in the currency or 4 coins in the coinage:
The optimum denomination is given by:
http://www.splkpark.k12.mn.us/mainsite/schools/SR/math/coinage.pdf
After that, I just gave up and went to bed!! 
Barukh... If you are onto something can you please elaborate.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Question of Denominations
« Reply #6 on: Sep 26th, 2006, 10:03am » |
Quote Modify
|
on Sep 26th, 2006, 8:18am, irrational wrote:| Barukh... If you are onto something can you please elaborate. |
|
After positing my remark, I realized it is of no use…  My apologies.
on Sep 25th, 2006, 10:21am, irrational wrote:| Moderators, please feel free to move this to any forum you choose fit. |
|
I think it should be moved to the Hard section.
|
|
IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Question of Denominations
« Reply #7 on: Sep 26th, 2006, 11:59am » |
Quote Modify
|
Are we only considering finite sets of denominations?
If so, it's good to note that in determining whether a set of denominations is greedy optimal (GO) for all values, it suffices to check a finite number of values.
Let L be the largest denomination. Then as long as the denomination set is GO for all values between L and 2L, then it is GO for all other amounts.
Proof:
| hidden: | Let's suppose our set is GO for all values between L and 2L.
Could there be a value, v<L which is non-GO? No, because then v+L would also be non-GO, which is contradicted by the premise, since L < v+L < 2L.
Could there be a value v>2L which is non-GO? If so, choose the smallest such v. Let m be the largest denomination possibly used in the optimal change-making for v. Then v-m is GO, and also larger than L. Thus the optimal change-making for v-m includes an L denomination, which means that m=L. But then this means that change can be made for v optimally by being greedy for v-m, and then adding an L, which is precisely the greedy algorithm for v, hence v is GO after all.
|
So for example, it suffices using the 1, 2, 5, 10, 20, 50 denominations to prove GO for 50 through 100.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Question of Denominations
« Reply #8 on: Sep 27th, 2006, 5:04am » |
Quote Modify
|
on Sep 26th, 2006, 11:59am, joefendel wrote:
Nice! The upper bound may be tightened to L+M, where M is the second largest denomination.
Besides: There are reasons to loosen the lower bound to n+1, where n is the third smallest denomination.
|
| « Last Edit: Sep 27th, 2006, 5:04am by Barukh » |
IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Question of Denominations
« Reply #9 on: Sep 29th, 2006, 12:56pm » |
Quote Modify
|
A few other observations:
1. If it's the case that every denomination is divisible by all smaller denominations, then the set is clearly GO. Thus {1, 5, 10, 20} is GO, eg. This applies to infinite sets as well as finite ones.
2. Every set of 2 denominations is GO, because one of the denominations must be a 1, and thus we're in case 1.
3. A set of 3 denominations is not GO if and only if it consists of {1, a, b} where b = ka - n, and a > n >= k >= 2. The "if" direction is easy to prove:
| hidden: |
First, notice that since k >= 2, we have b >= 2a - n > a, so b is indeed the largest denomination.
Let's make change for v=ka the greedy way. Since ka = b + n, we can use a b bill. Since n < a, the remaining bills must all be 1's. Thus greedy uses n+1 bills.
We could also use k a-bills. Since k <= n, this is better than n+1.
|
The "only if" direction is only a bit harder:
| hidden: |
Suppose we have a non-GO set {1, a, b}, where b > a. From case 2 above, the smallest non-GO value must be greater than b. We also know from our discussion earlier that the smallest non-GO value must be less than b+a. Thus let's call this value v = b + n, which uses n+1 bills using the greedy algorithm.
The optimal change-making cannot use a b-bill, since then greedy would clearly be optimal. Thus the optimal change-making uses k a-bills and j 1-bills. But if j > 0, we would have v-1 also being non-GO, which contradicts v being smallest. Thus j=0, so v = ka.
We then have almost all the elements described earlier: b = v - n = ka - n. Since b + n = v < b+a, we have a > n. Since v is a non-GO value, we have k < n+1, so k <= n. Finally, since b > a, k > 1, so k >= 2.
|
This then gives us a clear way to produce all non-GO sets of 3 denominations. {1, 3, 4}, {1, 4, 5}, {1, 4, 6}, {1, 4, 9}, ...
And that's as far as I got before the weekend.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print