Postage problem

The postage stamp problem is a problem of combinatorics and additive number theory . Be given stamps with values . Then you will be asked for the smallest number that cannot be represented as the sum of at most stamps from this set (since only stamps fit on the envelope). The stamps can also be used multiple times. The problem is generally open. ${\displaystyle k}$ ${\displaystyle a_{i}}$ ${\displaystyle h}$ ${\displaystyle h}$

The coin problem (Frobenius problem) is related to this . There is no restriction there, however . ${\displaystyle h}$

The problem goes back at least to Hans Rohrbach (1937).

formulation

Are given a set of positive integers , . We are looking for the smallest number that cannot be represented as a sum with and for . ${\displaystyle A_{k}=(a_{1},\cdots ,a_{k})}$ ${\displaystyle a_{1}=1<a_{2}<a_{3}<\cdots <a_{k}}$ ${\displaystyle N_{h}(A_{k})}$ ${\displaystyle \sum _{j=1}^{k}x_{j}\,a_{j}}$ ${\displaystyle \sum _{j=1}^{k}x_{j}\leq h}$ ${\displaystyle x_{j}\in \mathbb {N} _{0}}$ ${\displaystyle 1\leq j\leq k}$

The largest number for which all predecessors and they can represent themselves as such a sum, is -Range of applies it: . ${\displaystyle h}$ ${\displaystyle n_{h}(A_{k})}$ ${\displaystyle A_{k}}$ ${\displaystyle n_{h}(A_{k})=N_{h}(A_{k})-1}$

The problem is also posed in such a way that and are given and the amount sought that maximizes the range . These amounts are called -optimal amounts or also extreme bases. In this form it is a global version of the problem, the local version consists in determining the range for given quantities . ${\displaystyle h}$ ${\displaystyle k}$ ${\displaystyle A_{k}}$ ${\displaystyle n_{h}(k)=n(h,k)}$ ${\displaystyle (h,k)}$ ${\displaystyle A_{k}}$

For example, for a maximum of three stamps ( ) with stamp values ​​from each value up to can be displayed (range ). A value of can no longer be represented with three stamps from this set, you need at least four. On the other hand, that's not an optimal amount because . Optimal quantities for this combination of and are , and . ${\displaystyle h=3}$ ${\displaystyle A_{4}=(a_{1}=1,a_{2}=2,a_{3}=5,a_{4}=20)}$ ${\displaystyle n_{3}(A_{4})=12}$ ${\displaystyle 12}$ ${\displaystyle N_{3}(A_{4})=13}$ ${\displaystyle n(3,4)=23}$ ${\displaystyle h}$ ${\displaystyle k}$ ${\displaystyle \{1,3,6,10\}}$ ${\displaystyle \{1,4,6,15\}}$ ${\displaystyle \{1,4,7,9\}}$

1 is always assumed to be the element of , otherwise the range would be zero. also means additive basis of the order or basis if given . ${\displaystyle A_{k}}$ ${\displaystyle A_{k}}$ ${\displaystyle h}$ ${\displaystyle h}$ ${\displaystyle h}$

Results

From elementary considerations of combinatorics it follows (on the right is the binomial coefficient ). ${\displaystyle n(h,k)<{\binom {h+k}{k}}}$

Exact solution formulas are known for. ${\displaystyle k=2,3}$

For be ${\displaystyle k=2}$ ${\displaystyle A_{2}=(1,a)}$

Then is for . ${\displaystyle n_{h}(A_{2})=(h+3-a)\,a-2}$ ${\displaystyle h\geq a-2}$

In addition, (A. Stöhr 1955, A. Henrici 1965, RG Stanton et al. 1974)

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

With the largest integer less than or equal . The associated -optimal amount is . ${\displaystyle \left\lfloor x\right\rfloor }$ ${\displaystyle x}$ ${\displaystyle (h,2)}$ ${\displaystyle A_{2}=\left(1,\left\lfloor {\frac {h+3}{2}}\right\rfloor \right)}$

For and : ${\displaystyle k=3}$ ${\displaystyle n_{h}(A_{3})=n(h,3)}$

${\displaystyle {\frac {4}{81}}h^{3}+{\frac {2}{3}}h^{2}+{\frac {66}{27}}h\leq n_{h}(A_{3})\leq {\frac {4}{81}}h^{3}+{\frac {2}{3}}h^{2}+{\frac {71}{27}}h-{\frac {1}{81}}}$

for ( Gerd Hofmeister ). The equality in the lower bound is fulfilled for. Hofmeister thus solved the global problem for . The local problem (determination of ) was approached by Øystein J. Rødseth, who developed a general method based on a continued fraction algorithm. Based on this, Ernst Sejersted Selmer gave asymptotic formulas that covered most cases . ${\displaystyle h\geq 34}$ ${\displaystyle h=0\mod 9}$ ${\displaystyle k=3}$ ${\displaystyle n_{h}(A_{3})}$ ${\displaystyle A_{3}}$

S. Mossige showed for that asymptotic ${\displaystyle k=4}$

${\displaystyle n(h,4)\geq 2{,}008\left({\frac {h}{4}}\right)^{4}+{\mathcal {O}}(h^{3})}$

A Landau symbol was used on the right . With Kirfel he also showed that the estimate is the best possible. Kirfel showed that the limit exists for everyone . He also stated the value of . ${\displaystyle c_{k}=\lim _{h\to \infty }{\frac {n(h,k)}{{({\frac {h}{k}})}^{k}}}}$ ${\displaystyle k\geq 1}$ ${\displaystyle c_{5}}$

Hans Rohrbach found asymptotic limits for solid and large in 1937: ${\displaystyle h}$ ${\displaystyle k}$

${\displaystyle \left({\frac {k}{h}}\right)^{h}\leq n(h,k)\leq {\frac {k^{h}}{h!}}+{\mathcal {O}}(k^{h-1})}$

The lower bound applies in general and it also applies . The best lower bound for large and solid comes from Hofmeister using results from R. Windecker. The best upper bound for fixed k comes from Rødseth: ${\displaystyle \left({\frac {h}{k}}\right)^{k}\leq n(h,k)}$ ${\displaystyle k}$ ${\displaystyle h}$

${\displaystyle n(h,k)\leq {\frac {{(k-1)}^{k-2}}{(k-2)!}}\left({\frac {h}{k}}\right)^{k}+{\mathcal {O}}(h^{k-1})}$

Especially for Rohrbach found: ${\displaystyle h=2}$

${\displaystyle d_{1}\left({\frac {k}{2}}\right)^{2}+{\mathcal {O}}(k)\leq n(2,k)\leq d_{2}{\frac {k^{2}}{2}}+{\mathcal {O}}(k)}$

with . A. Mrose improved and W. Klotz improved . ${\displaystyle d_{1}=1,d_{2}=1{,}9968}$ ${\displaystyle d_{1}={\frac {8}{7}}}$ ${\displaystyle d_{2}=1{,}9208}$

Richard Guy hypothesized that for large those are given by a finite number of polynomials in of degree . ${\displaystyle h}$ ${\displaystyle n(h,k)}$ ${\displaystyle h}$ ${\displaystyle k}$

Others

For variables the problem is NP-hard . In the case of fixed , on the other hand, it can be solved in polynomial time. ${\displaystyle h}$ ${\displaystyle h}$

The problem was used, for example, in the optimal allocation of index registers in computers or optimal cabling patterns in associative cache memories .

literature

• Richard K. Guy: Unsolved problems in number theory, Springer 1994, pp. 123-127 (Postage Stamp Problem)
• Ronald Alter, Jeffrey Barnett: A postage stamp problem, American Mathematical Monthly, Volume 87, 1980, pp. 206-210, JSTOR
• Mossige: Algorithms for Computing the h-Range of the Postage Stamp Problem, Math. Comput., Volume 36, 1981, pp. 575-582

Web links

• Eric Weisstein: Postage stamp problem, mathworld
• Postage stamp problem , spectrum lexicon of mathematics

Individual evidence

1. ↑ Guy, Unsolved problems in number theory, p. 123.
2. ↑ Guy, Unsolved problems in number theory, p. 123
3. ↑ Stöhr, Solved and Unsolved Questions about Bases of the Natural Number Series, 2 parts, J. Reine Angew. Math., Vol. 194, 1955, pp. 40-65, 111-140
4. ↑ Hofmeister, Asymptotic Estimates for Three-Element Extreme Bases in Natural Numbers, J. Reine Angew. Math., Vol. 232, 1968, pp. 77-101
5. ↑ Selmer, The local postage stamp problem, 3 parts, University of Bergen 1986, 1990
6. ↑ Guy, Unsolved problems in number theory, p. 123
7. ^ Rohrbach, A contribution to additive number theory, Math. Z., Volume 42, 1937, pp. 1-30
8. ↑ Hofmeister, Finite Additive Number Theory, Chapter 1, The Range Problem, University of Mainz 1976. After Alter, Barnett, American Mathematical Monthly, Volume 87, 1980, pp. 206f
9. ↑ Guy, Unsolved problems in number theory, p. 124
10. ↑ Rødseth, An upper bound for the hour range of the post-stamp a problem, Acta Arithmetica, Volume 54, 1990, pp 301-306
11. ^ Alter, Barnett, American Mathematical Monthly, 87, 1980, p. 207, with an explicit representation of the conjecture for k = 2.3
12. ↑ Jeffrey Shallit, The computational complexity of the local postage stamp problem. SIGACT News, Volume 33, March 2002, pp. 90-94
13. ^ Alter, Barnett, American Mathematical Monthly, 87, 1980, p. 207