The Change Will Do You Good Puzzle - Solution
The Puzzle:
Sugary Sue runs a small shop which sells sweets which run in price from 1p to 1 Pound with every value in between. One day Hungry Horace came in to spend some of his 1 Pound pocket money.
What is the smallest number of coins that Sue needs to set aside to guarantee having exactly the right change for whatever Horace will buy?
Type of coin available: 1p, 2p, 5p, 10p, 20p, 50p
Sue needs to be able to make any amount between 1p and 99p.
Our Solution:
Sugary Sue only needs to set aside 8 coins to guarantee being able to give any amount of change to Hungry Horace. There are several ways this can be done:
1p, 2p, 2p, 5p, 10p, 20p, 20p, 50p
1p, 1p, 2p, 5p, 10p, 20p, 20p, 50p
1p, 2p, 2p, 5p, 10p, 10p, 20p, 50p
1p, 1p, 2p, 5p, 10p, 10p, 20p, 50p
In each case it is possible to use just a selection of the 8 coins to make up any amount between 1p and 99p, as required.
Horace gets his change!