� Shopping Advice | Main | Does Not Compute �
October 08, 2003
Homework Help
Marianne is six. This week's maths homework goes as follows.
"How many ways can you make 78p from smaller coins (1,2,5,10,20,50)? You can use them more than once."
Any offers? I'd really like a good strategy for finding the solution too (my way was very slow), and a general approach for f(n) for arbitrary amounts of money (if you go for that, then there are also £1 and £2 coins in general circulation).
I probably ought to add that Marianne's answer was 6, and she did write them out. I am pretty sure that was the sort of answer Mr Simpson was looking for; I would be very worried about the sort of six-year-old who can answer that question.
Extra credit: Solve for US coins.
Extra, extra credit: Solve for Wingdingian coins, which are arbitrary denominations of 1, a, b, c, d, and e Wingdingian centimes.
Posted by Alison Scott at October 8, 2003 08:50 PM
Trackback Pings
TrackBack URL for this entry:
http://www.kittywompus.com/cgi-sys/cgiwrap/illyria/mt/mt-tb.cgi/98
Comments
I make it 92 different ways. I'm afraid I couldn't find a shortcut either. I had to do it longhand. You've intrigued me now.
Posted by: David Stewart at October 13, 2003 10:53 PM
I take that back. There are an awful lot more.
Posted by: David Stewart at October 14, 2003 03:01 PM
There are, I think, 1869 ways; the solution is an iterative function.
Posted by: Alison Scott at October 17, 2003 07:31 PM
First time out, take the largest coin, add the second largest coin, carry on adding any coins you can until you reach the total you need.
1)50+20+5+2+1
Then take this solution an start replacing each coin with a group of smaller coins.
(50 = 20+20+10)
2)20+20+10+20+5+2+1
take that solution and break it down again.
When you've taken each solution and broken it down into every subsolution (and sub-subsolution), then start again from the beginning, but without one of the coins. Then without two of the coins, and so on.
Is that the iterative solution you went for?
Posted by: Andrew Ducker at December 17, 2003 08:13 AM
Not really; that approach will generate all solutions, but you'll have a big pile of duplicates to weed. I did it two different ways;
First, by looking at all the solutions that included a 50p, and then all the solutions with 3 20ps, 2 20ps, 1 20p, and so on...
Second (after I blogged about it), by defining some intermediate functions:
A(n)= the number of ways of making n pence from 1p and 2p pieces
B(n)= the number of ways of making n pence from 1p, 2p and 5p pieces...
and so on. So E(78) is the number we want, and it equals D(78) + D(28), which equals C(78) + C(58) + C(38) + C(18) +C(28) + C(8)... and so on until you find the solution, which is, I think, about 1800 or so.
Posted by: Alison Scott at December 17, 2003 10:19 PM