Fewest coins, step by step
Take the biggest coin that fits, then the next, then the next.
A basket comes to 26c. What is the fewest coins that pay it exactly?
The obvious way to pay is not the fewest
- Everything hangs on which coins exist here — 1c, 7c, 12c and nothing else — and on paying 26c with no change given. These are not the coins in anyone's pocket, so nothing you know about paying transfers.
- Try the way everybody pays: take the biggest that fits, again and again. That gives 12 + 12 + 1 + 1 — 4 coins. It works, so it is a real answer, and the question did not ask for a real answer.
- The trouble is that a big coin can leave a remainder the other coins fit badly, and a slightly smaller one can leave a remainder they fit exactly. So taking the biggest is a guess, not a method.
- 12 + 7 + 7 makes 26c in 3 coins, which is 1 fewer. And 3 is genuinely the fewest: work out the best way to pay 1c, then 2c, then 3c and so on up to 26c, and each amount only needs the answer to a smaller one you have already done.
How it works.
- 01
Everything hangs on which coins exist here — 1c, 7c, 12c and nothing else — and on paying 26c with no change given. These are not the coins in anyone's pocket, so nothing you know about paying transfers.
- 02
Try the way everybody pays: take the biggest that fits, again and again. That gives 12 + 12 + 1 + 1 — 4 coins. It works, so it is a real answer, and the question did not ask for a real answer.
- 03
The trouble is that a big coin can leave a remainder the other coins fit badly, and a slightly smaller one can leave a remainder they fit exactly. So taking the biggest is a guess, not a method.
- 04
12 + 7 + 7 makes 26c in 3 coins, which is 1 fewer. And 3 is genuinely the fewest: work out the best way to pay 1c, then 2c, then 3c and so on up to 26c, and each amount only needs the answer to a smaller one you have already done.