I recently stumbled upon the Postage Stamp Problem. Given two relatively prime positive numbers a and b, show that any sufficiently large number N, there exists nonnegative integers x and y such that
ax + by = N.
I initially missed the constraint that x and y must be positive, in which result is well known (Bézout’s lemma) and there’s no requirement for N to be large. The positivity constraint makes things more interesting.
The problem is called the Postage Stamp Problem because it says that given any two stamps whose values are relatively prime, say a 5¢ stamp and a 21¢ stamp, you can make any sufficiently large amount of postage using just those two stamps.
A natural question is how large is “sufficiently large,” and the answer turns out to be all integers larger than
ab − a − b.
So in our example, you cannot make 79¢ postage out of 5¢ and 21¢ stamps, but you can make 80¢ or any higher amount.
If you’ve been reading this blog for a while, you may recognize this as a special case of the Chicken McNugget problem, which you can think of as the Postage Stamp problem with possibly more than two stamps.
In some post-apocalyptic future, an old man is telling an attentive horde of youngsters huddled around a camp fire about the good old days, when he was working at a drive-through. Especially about the fall of 2024, when a bunch of mathematicians showed up ordering weird numbers of chicken nuggets and insisting to pay with carefully prepared packages of even weirder postage stamps.
If you include 0, there’s a really nice symmetry in those values up to the maximum you can’t make too, in that they pair off into ones you can and can’t make nicely. Proving this isn’t too hard, proving the pairing one way is trivial to show the relationship holds, and then you can count the lattice points on ax+by=N to show the 50/50 split.