KA-0010Money and change
3 points, difficulty 1 of 3Level 3–4about 75sSam has only 2-cent and 5-cent coins. What is the largest amount under 15 cents that he cannot make exactly?
Hints
Take them one at a time. The first gives nothing away.
1A nudge
List every amount from 1 to 14 and test it.
2The strategy
Go through the amounts in order and ask whether each can be built from twos and fives. Once you can make two amounts in a row, everything after them follows by adding twos.
3The full solution
1 no, 2 yes, 3 no, 4 yes, 5 yes, 6 yes, 7 = 2 + 5 yes, and from 4 onwards every amount works because you can add twos. So the largest impossible amount is 3.
Solution
The reliable way
Test the amounts in order: 1 no, 2 yes, 3 no, 4 yes (2+2), 5 yes, 6 yes, 7 yes (2+5), 8 yes, 9 yes (2+2+5). Once 4 and 5 are both possible, every larger amount is possible too, because you can keep adding 2. So the largest amount that cannot be made is 3 cents. The transferable idea: once two consecutive amounts work, all larger ones do.
The elegant way
With coins of 2 and 5 the only unreachable amounts are 1 and 3, because every number from 4 upwards is 4 or 5 plus a multiple of 2.
Why this is on the test: It looks like a coin question but is really systematic listing with a stopping argument, which is the skill being tested.