How Many Ways to Make a Pound?

  • Medium
  • Mathematical puzzles
  • Tests: Counting combinations without listing them

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.