Hispanopedia Wiki
Articulo de referencia

Postage stamp problem

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 tha...

Hispanopedia WikiContenido en espanolLectura gratuita
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.[1]

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 v1 + v2 + ··· + vk 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.[1]

See also

References

  1. 12Jeffrey Shallit (2001), The computational complexity of the local postage stamp problem. SIGACT News 33 (1) (March 2002), 90-94. Accessed on 2009-12-30.
  • 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, RL ; Sloane, NJA (1980). "Sobre bases aditivas y grafos armónicos". SIAM J. Algebr. Discrete Methods . 1 (4): 382– 404. CiteSeerX 10.1.1.70.5521 . doi : 10.1137/0601045 . 
  • Challis, MF (1993). "Dos nuevas técnicas para calcular h -bases extremales A k " . Comput. J . 36 (2): 117– 126. doi : 10.1093/comjnl/36.2.117 .
  • Kohonen, J.; Corander, J. (2013). "Cadenas de suma se encuentran con sellos postales: reduciendo el número de multiplicaciones". arXiv : 1310.7090 [ math.NT ].
  • Kohonen, Jukka (2014). "Un algoritmo de encuentro en el medio para encontrar 2-bases aditivas restringidas extremales". arXiv : 1403.5945 [ math.NT ].
  • Weisstein, Eric W. "Problema del sello postal" . MundoMatemático .
  • Secuencia OEIS A001212 (Solución al problema de los sellos postales con n denominaciones y 2 sellos)