Postage Stamp Problem

Consider a Set $A_k=\{a_1, a_2, \ldots, a_k\}$ of Integer denomination postage stamps with $1=a_1<a_2<\ldots<a_k$. Suppose they are to be used on an envelope with room for no more than $h$ stamps. The postage stamp problem then consists of determining the smallest Integer $N(h,A_k)$ which cannot be represented by a linear combination $\sum_{i=1}^k x_i a_i$ with $x_i\geq 0$ and $\sum_{i=1}^k x_i<h$. Exact solutions exist for arbitrary $A_k$ for $k=2$ and 3. The $k=2$ solution is

$$n(h,A_2)=(h+3-a_2)a_2-2$$

for $h\geq a_2-2$. The general problem consists of finding

$$n(h,k)=\max_{A_k} n(h,A_k).$$

It is known that

$$n(h,2)=\left\lfloor{{\textstyle{1\over 4}}(h^2+6h+1)}\right\rfloor ,$$

(Stöhr 1955, Guy 1994), where $\left\lfloor{x}\right\rfloor$ is the Floor Function, the first few values of which are 2, 4, 7, 10, 14, 18, 23, 28, 34, 40, ... (Sloane's A014616).

See also Harmonious Graph, Stamp Folding

References

Guy, R. K. ``The Postage Stamp Problem.'' §C12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 123-127, 1994.

Sloane, N. J. A. Sequence A014616 in ``The On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.

Stöhr, A. ``Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe I, II.'' J. reine angew. Math. 194, 111-140, 1955.