{{more citations needed|date=June 2017}} thumb|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.<ref name=arxiv>Jeffrey Shallit (2001), [https://arxiv.org/abs/math.NT/0112257 ''The computational complexity of the local postage stamp problem'']. SIGACT News 33 (1) (March 2002), 90-94. Accessed on 2009-12-30.</ref>
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''<sub>1</sub> + ''v''<sub>2</sub> + ··· + ''v''<sub>''k''</sub> 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'' |<sup>''m''</sup>, 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.<ref name=arxiv/>
==See also== * Coin problem * Knapsack problem * Subset sum problem
== References == {{reflist}}
==External links== *{{cite journal| first1=W. F. | last1=Lunnon| title= A postage stamp problem |journal = Comput. J. | number=4 | year= 1969| pages=377–380|volume=12|doi=10.1093/comjnl/12.4.377| doi-access=free}} *{{cite journal| first1=R. | last1=Alter | first2=J. A. | last2=Barnett| title=A postage stamp problem |journal = Amer. Math. Monthly | year=1980 | volume=87 | issue=3 | pages=206–210 | doi=10.2307/2321610| jstor=2321610 }} *{{cite journal|first1=R. L. | last1=Graham |author1-link=Ronald Graham | first2=N. J. A. | last2=Sloane |author2-link=N. J. A. Sloane |title=On additive bases and harmonious graphs| journal=SIAM J. Algebr. Discrete Methods |year =1980|volume=1 | issue=4 | pages=382–404|doi=10.1137/0601045|citeseerx=10.1.1.70.5521}} *{{cite journal|first1=M. F. | last1=Challis| title=Two new techniques for computing extremal ''h''-bases ''A''<sub>''k''</sub> |journal=Comput. J. | volume=36|number=2 | pages=117–126| year=1993 |doi=10.1093/comjnl/36.2.117| doi-access=free}} * {{cite arXiv| first1=J. | last1=Kohonen| first2=J. | last2=Corander | eprint=1310.7090 |title=Addition chains meet postage stamps: reducing the number of multiplications| year=2013| class=math.NT}} *{{cite arXiv|first1=Jukka | last1=Kohonen| title=A meet-in-the-middle algorithm for finding extremal restricted additive 2-bases |year=2014 | class=math.NT| eprint=1403.5945}} * {{MathWorld | urlname=PostageStampProblem | title=Postage Stamp Problem}} * {{OEIS el|A001212|Solution to the postage stamp problem with ''n'' denominations and 2 stamps}}
Category:Additive number theory Category:Recreational mathematics Category:Applied mathematics Category:Mathematical problems