What the Post Office Cannot Make

A shop sells stamps in only two values, $15$ pence and $22$ pence. Using any number of each, many totals can be made exactly, but not all: you cannot make $1$p, or $7$p, or $30$p. What is the largest amount that cannot be made exactly?

Solution

The answer is $293$ pence. Beyond it, every amount can be made; $293$ itself cannot, and it is the last that defeats you.

The reason such a largest value exists at all is that $15$ and $22$ share no common factor. Once you can make some run of $15$ consecutive amounts, you can make everything above it, simply by adding more $15$p stamps to climb in steps of fifteen. For two coprime values $m$ and $n$ the largest unreachable total works out to $$mn - m - n = 15 \times 22 - 15 - 22 = 330 - 37 = 293,$$ a tidy formula worth knowing.

That $293$ really cannot be made is worth proving outright. Suppose $293 = 15a + 22b$ with $a, b$ whole numbers, none negative. Add $15 + 22$ to both sides: the right becomes $15(a+1) + 22(b+1)$, and the left becomes $293 + 37 = 330 = 15 \times 22$. So $$15(a+1) + 22(b+1) = 15 \times 22.$$ Now $15(a+1)$ is a multiple of $15$, and the right side $15 \times 22$ is too, so the remaining term $22(b+1)$ must also be a multiple of $15$. Since $22$ and $15$ share no common factor, it is $b + 1$ that has to supply the factor of $15$, so $b + 1$ is at least $15$. Swapping the roles of $15$ and $22$, the same reasoning forces $a + 1$ to be at least $22$. But then the left side is at least $15 \times 22 + 22 \times 15 = 2 \times 330$, far more than the $330$ it is supposed to equal. The contradiction shows no such $a, b$ exist, so $293$ is unreachable.

Everything past it, on the other hand, is reachable. The next fifteen totals can each be made, for instance $294 = 15 \times 2 + 22 \times 12$ and $295 = 15 \times 5 + 22 \times 10$, and once fifteen consecutive totals are in hand, adding one more $15$p stamp to each climbs through everything beyond in steps of fifteen.