The Postage Stamp Problem
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 (Bezout'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.
Related postsThe post The Postage Stamp Problem first appeared on John D. Cook.