Coin Sums

In the United Kingdom the currency is made up of pound (£) and pence (p). There are eight coins in general circulation:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p).
It is possible to make £2 in the following way:
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any number of coins?

This is a classic problem of combinatorial integer partitioning, also known as counting the number of ways to make change. Here we want to partition the number 200 (since £2 = 200p) using the numbers {1,2,5,10,20,50,100,200}. The order in which coins are picked doesn’t matter (as it’s asked how many “different ways”), so picking £1 first and then 50p is the same as picking 50p first and then £1.

In order to solve this problem by hand, a systematic approach is required which could involve a lot of computation. Normally, this would be solved using dynamic programming, as it is a fairly common problem in computer science.

However, I can give you the general approach to solve the problem:

First, consider a simpler problem: what if there were only 1p coins available? There’s obviously just one way to make up £2: use 200 coins of 1p.

Now, consider a slightly more complex problem: imagine there are 1p and 2p coins. How many ways are there to make up £2 now? Well, we know there are exactly 101 ways to do this, ranging from 200 coins of 1p (and 0 of 2p), to 0 coins of 1p (and 100 of 2p), stepping by 2p at a time.

Then, you add coins of 5p, 10p, 20p, 50p, £1 and £2 and repeat the process for each, building up in complexity each time, until ultimately, you can answer how many ways to make £2 using any of the eight coins.

The answer to this problem, if solved programmatically, is 73682 ways. This is not something you would want to try to solve manually as it is very time-consuming and prone to error. It’s wise to study the algorithmic solution should you wish to delve a bit deeper into different strategies.

More Answers: