Postage stamp problem
From Wikipedia, the free encyclopedia
 |
This article needs additional citations for verification. Please help improve this article by adding reliable references. Unsourced material may be challenged and removed. (January 2008) |
The postage stamp problem is the following:
Consider that an envelope is able to hold a limited number of postage stamps. Then, consider the set of the values of the stamps -- positive integers only. Then, what is the smallest total postage which *cannot* be put onto the envelope?
For example, if the envelope can hold three stamps, and the possible stamp values are the set {1, 4, 6}, solutions for the totals 1 through 14 can be found. But to get a total of 15: three 6's would be too much; two 6's cannot be used, since there is no 3; using just one 6 will not work, because there is no combination to make 9 with two stamps; but with no 6's, the largest total (three 4's) would only be 12. So the answer to the problem is 15.
Generalized formulas for the answer have been investigated, but it has been determined that "There's no one simple algorithm that works for all systems of stamps." [1]
