Article 6S450 The Postage Stamp Problem

The Postage Stamp Problem

by
John
from John D. Cook on (#6S450)

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.

stamps.jpg

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.
External Content
Source RSS or Atom Feed
Feed Location http://feeds.feedburner.com/TheEndeavour?format=xml
Feed Title John D. Cook
Feed Link https://www.johndcook.com/blog
Reply 0 comments