Some numbers look impossible only because we are still too low. With two suitable stamp values, there comes a point after which impossibility disappears forever.
The Impossible Stamps
Riddle statement
A post office only has 5-cent and 7-cent stamps.
You may use as many stamps of each type as you want.
What is the largest number of cents that you cannot form exactly?
Show solution
Solution
The answer is:
First, let us see that 23 cannot be formed with 5-cent and 7-cent stamps.
Try the possible numbers of 7-cent stamps:
0 stamps of 7 leave 23, which is not a multiple of 5. 1 stamp of 7 leaves 16, which is not a multiple of 5. 2 stamps of 7 leave 9, which is not a multiple of 5. 3 stamps of 7 leave 2, which is not a multiple of 5.
So 23 is impossible.
Now we need to see that every number greater than 23 can be formed.
It is enough to find five consecutive possible amounts, because from that point on we can always add another 5-cent stamp.
And we have:
Since we can form 24, 25, 26, 27, and 28, we can also form:
29 by adding 5 to 24; 30 by adding 5 to 25; 31 by adding 5 to 26; and so on.
From 24 onward, every amount can be formed.
Answer: the largest amount that cannot be formed is 23 cents.