// Workers AI · dad joke modeWhat did the postage stamp problem say? It was stuck.

13 is the smallest total that cannot fit on an envelope with space for only three stamps of possible values 1, 2, 5 and 20

The postage stamp problem is a mathematical riddle that asks what is the smallest postage value which cannot be placed on an envelope, if the latter can hold only a limited number of stamps, and these may only have certain specified face values.

For example, suppose the envelope can hold only three stamps, and the available stamp values are 1 cent, 2 cents, 5 cents, and 20 cents. Then the solution is 13 cents; since any smaller value can be obtained with at most three stamps (e.g. 4 = 2 + 2, 8 = 5 + 2 + 1, etc.), but to get 13 cents one must use at least four stamps.

Mathematical definition

Mathematically, the problem can be formulated as follows:

Given an integer m and a set V of positive integers, find the smallest integer z that cannot be written as the sum v₁ + v₂ + ··· + v_k of some number k ≤ m of (not necessarily distinct) elements of V.

Complexity

This problem can be solved by brute force search or backtracking with maximum time proportional to |V |^m, where |V | is the number of distinct stamp values allowed. Therefore, if the capacity of the envelope m is fixed, it is a polynomial time problem. If the capacity m is arbitrary, the problem is known to be NP-hard.

See also

• Coin problem
• Knapsack problem
• Subset sum problem

External links

• Lunnon, W. F. (1969). "A postage stamp problem". Comput. J. 12 (4): 377–380. doi:10.1093/comjnl/12.4.377.
• Alter, R.; Barnett, J. A. (1980). "A postage stamp problem". Amer. Math. Monthly. 87 (3): 206–210. doi:10.2307/2321610. JSTOR 2321610.
• Graham, R. L.; Sloane, N. J. A. (1980). "On additive bases and harmonious graphs". SIAM J. Algebr. Discrete Methods. 1 (4): 382–404. CiteSeerX 10.1.1.70.5521. doi:10.1137/0601045.
• Challis, M. F. (1993). "Two new techniques for computing extremal h-bases A_k". Comput. J. 36 (2): 117–126. doi:10.1093/comjnl/36.2.117.
• Kohonen, J.; Corander, J. (2013). "Addition chains meet postage stamps: reducing the number of multiplications". arXiv:1310.7090 [math.NT].
• Kohonen, Jukka (2014). "A meet-in-the-middle algorithm for finding extremal restricted additive 2-bases". arXiv:1403.5945 [math.NT].
• Weisstein, Eric W. "Postage Stamp Problem". MathWorld.
• OEIS sequence A001212 (Solution to the postage stamp problem with n denominations and 2 stamps)