How Many Ways to Make a Pound?
The puzzle
British coins are 1p, 2p, 5p, 10p, 20p, 50p and £1. In how many different ways can £1 be made up?
Two ways count as the same if they use the same coins in a different order. Listing them is not practical, so find a way to count them.
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
Work up from small amounts, and bring the coins in one denomination at a time.
Hint 2
Let W(v) be the ways to make v using only the coins allowed so far. Adding a new coin c updates every W(v) by adding W(v − c).
Show the answer Hide the answer
4,563 ways.
How to get there
Count amounts from 0 to 100 and introduce the coins one at a time. Start with only 1p available: every amount has exactly one way. Now allow 2p: the ways to make v either use no 2p, which is the old count, or use at least one, which is the count for v − 2.
So W(v) becomes W(v) + W(v − 2), applied upwards from v = 2. Repeat for 5, 10, 20, 50 and 100. Bringing the coins in one at a time rather than all at once is what stops the same combination being counted in several orders.
After all seven passes, W(100) = 4,563. Dropping the £1 coin gives 4,562, since it contributes exactly one way - itself. Adding a 25p coin, which Britain does not have, would take it past 6,000.
The technique worth keeping
Count combinations by building a table upwards and introducing the choices one at a time. Doing it in a fixed order counts each combination once; doing it all at once counts every ordering separately.