Three-Penny and Five-Penny Stamps

  • Medium
  • Mathematical puzzles
  • Tests: Finding where a gap sequence stops

The puzzle

A post office sells only 3p and 5p stamps. You may use as many of each as you like.

Which postage amounts cannot be made exactly? And what is the largest of them?

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

Work up from 1p: which small amounts fail?

Hint 2

Once you can make three consecutive amounts, you can make everything above them - just add 3p stamps.

Show the answer Hide the answer

Only 1p, 2p, 4p and 7p are impossible. The largest is 7p, which is 3 x 5 - 3 - 5.

How to get there

Checking upwards: 1 no, 2 no, 3 yes, 4 no, 5 yes, 6 = 3+3, 7 no, 8 = 3+5, 9 = 3+3+3, 10 = 5+5.

Now 8, 9 and 10 are all makeable, and they are three consecutive amounts. Adding a 3p stamp to each gives 11, 12, 13; again gives 14, 15, 16; and so on forever. So every amount of 8p or more can be made, and 7p is the largest that cannot.

The general result for two coprime values a and b is that the largest unmakeable amount is ab - a - b: here 15 - 3 - 5 = 7. If the two values share a factor, as 4 and 6 do, then no odd amount is ever makeable and there is no largest - which is why coprimality is the condition.

The technique worth keeping

To show everything above some point is reachable, find a run of consecutive reachable values as long as your smallest step. Everything beyond follows by adding that step, which turns an infinite claim into a finite check.