Author |
Topic: Change (Read 453 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
In how many different ways can we make change for 50 cents?
|
|
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
 |
Re: Change
« Reply #1 on: Jan 1st, 2005, 2:33pm » |
 Quote  Modify
|
1. what are the available coins?
2. are solutions like give 1 euro and return 50 cents ok? (assuming they are cents of an euro)
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Change
« Reply #2 on: Jan 1st, 2005, 4:09pm » |
Quote Modify
|
Using only the US coins of 1, 5, 10, 25, and 50 cents.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Change
« Reply #3 on: Jan 2nd, 2005, 2:11am » |
Quote Modify
|
I assume PCs are not allowed? Otherwise, look here.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Change
« Reply #4 on: Jan 2nd, 2005, 8:39am » |
Quote Modify
|
on Jan 2nd, 2005, 2:11am, Barukh wrote:| I assume PCs are not allowed? Otherwise, look here. |
|
Yes, perhaps I should have put this in CS.
Although it's not a very interesting problem, the answer is slightly interesting.
|
| « Last Edit: Jan 2nd, 2005, 9:25pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Change
« Reply #5 on: Jan 3rd, 2005, 2:50am » |
Quote Modify
|
It happens to be ::50::
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Change
« Reply #6 on: Jan 3rd, 2005, 5:23am » |
Quote Modify
|
I found it here.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Change
« Reply #7 on: Jan 3rd, 2005, 6:43am » |
Quote Modify
|
As the numbers here are well chosen, it can be solved analytically...
Let the number of 1,5,10,25,50 cent coins be represented by a,b,c,d,e respectively.
We shall consider the two cases, where e=0 or e=1.
e=1 is trivial as a=b=c=d=0 (1 solution).
If e=0, 0[le]d[le]2, and we shall consider each of the three cases.
If d=2 we get the trivial solution, a=b=c=e=0 (1 solution).
If d=0 the 50 cents must be made up of 1,5,10, and we can see that 0[le]c[le]5.
If c=0 the 50 cents must be made up of 1 and 5, therefore 0[le]b[le]10 and there are 11 solutions, as the number of 1 cent coins (a) is fixed for each of these values of b. In the same way,
c=1, 40 cents remaining, so 0[le]b[le]8 (9 solutions)
c=2, 30 cents remaining, so 0[le]b[le]6 (7 solutions)
c=3, 20 cents remaining, so 0[le]b[le]4 (5 solutions)
c=4, 10 cents remaining, so 0[le]b[le]2 (3 solutions)
c=5, 0 cents remaining, so b=0 (1 solution)
If d=1 the remaining 25 cents must be made up of 1,5,10 and 0[le]c[le]2.
c=0, 25 cents remaining, so 0[le]b[le]5 (6 solutions)
c=1, 15 cents remaining, so 0[le]b[le]3 (4 solutions)
c=2, 5 cents remaining, so 0[le]b[le]1 (2 solutions)
Hence the total number of solutions is 1+1+9+7+5+3+1+6+4+2=50.
In general, how many ways can n cents be made up of 1 and 5 cent coins? [easy]
I've not been able to find the number of ways that n cents can be made from 1, 5, and 10 cent coins; that is, a single formula and not a sum. But it can be done for the three smallest British denominations of coins...
Find the number of ways of making up n pence from 1, 2, and 5 pence coins. [hard]
I wonder how far this can be generalised.
[e]Edited because I made an oversight in my generalisation, and the second extension question has been rephrased.[/e]
|
| « Last Edit: Jan 3rd, 2005, 2:56pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print