Briefmarkenproblem – Wikipedia

Das Briefmarkenproblem ist ein Problem der Kombinatorik und additiven Zahlentheorie. Seien ${\displaystyle k}$ Briefmarken mit Werten ${\displaystyle a_{i}}$ gegeben. Dann wird nach der kleinsten Zahl gefragt, die nicht als Summe von höchstens ${\displaystyle h}$ Briefmarken aus dieser Menge dargestellt werden kann (da nur ${\displaystyle h}$ Marken auf den Briefumschlag passen). Dabei können die Briefmarken auch mehrfach verwendet werden. Das Problem ist im Allgemeinen offen.

Damit verwandt ist das Münzproblem (Frobenius-Problem). Dort gibt es allerdings keine Beschränkung durch ${\displaystyle h}$.

Das Problem geht mindestens bis auf Hans Rohrbach (1937) zurück.^[1]

Gegeben sind eine Menge positiver ganzer Zahlen ${\displaystyle A_{k}=(a_{1},\cdots ,a_{k})}$, ${\displaystyle a_{1}=1<a_{2}<a_{3}<\cdots <a_{k}}$. Gesucht wird die kleinste Zahl ${\displaystyle N_{h}(A_{k})}$, die sich nicht als Summe ${\displaystyle \sum _{j=1}^{k}x_{j}\,a_{j}}$ darstellen lässt mit ${\displaystyle \sum _{j=1}^{k}x_{j}\leq h}$ und ${\displaystyle x_{j}\in \mathbb {N} _{0}}$ für ${\displaystyle 1\leq j\leq k}$.

Die größte Zahl, für die sich alle Vorgänger und sie selbst als eine solche Summe darstellen lassen, heißt ${\displaystyle h}$-Reichweite ${\displaystyle n_{h}(A_{k})}$ von ${\displaystyle A_{k}}$ Es gilt: ${\displaystyle n_{h}(A_{k})=N_{h}(A_{k})-1}$.

Das Problem wird auch so gestellt, dass ${\displaystyle h}$ und ${\displaystyle k}$ gegeben werden, und die Menge ${\displaystyle A_{k}}$ gesucht wird, die die Reichweite ${\displaystyle n_{h}(k)=n(h,k)}$ maximiert. Diese Mengen werden ${\displaystyle (h,k)}$-optimale Mengen oder auch extremale Basen genannt. In dieser Form ist es eine globale Version des Problems, die lokale Version besteht darin die Reichweite für vorgegebene Mengen ${\displaystyle A_{k}}$ zu bestimmen.^[2]

Zum Beispiel ist für maximal drei Briefmarken (${\displaystyle h=3}$) mit Briefmarken-Werten aus ${\displaystyle A_{4}=(a_{1}=1,a_{2}=2,a_{3}=5,a_{4}=20)}$ jeder Wert bis ${\displaystyle n_{3}(A_{4})=12}$ darstellbar (Reichweite ${\displaystyle 12}$). Ein Wert von ${\displaystyle N_{3}(A_{4})=13}$ ist nicht mehr mit drei Briefmarken aus dieser Menge darstellbar, man benötigt mindestens vier. Andererseits ist das keine optimale Menge, denn ${\displaystyle n(3,4)=23}$. Optimale Mengen für diese Kombination von ${\displaystyle h}$ und ${\displaystyle k}$ sind ${\displaystyle \{1,3,6,10\}}$, ${\displaystyle \{1,4,6,15\}}$ und ${\displaystyle \{1,4,7,9\}}$.

Dabei wird stets 1 als Element von ${\displaystyle A_{k}}$ angenommen, sonst wäre die Reichweite Null. ${\displaystyle A_{k}}$ heißt bei vorgegebenem ${\displaystyle h}$ auch additive Basis der Ordnung ${\displaystyle h}$ oder ${\displaystyle h}$-Basis.

Aus elementaren Überlegungen der Kombinatorik folgt ${\displaystyle n(h,k)<{\binom {h+k}{k}}}$ (rechts steht der Binomialkoeffizient).

Exakte Lösungsformeln sind für ${\displaystyle k=2,3}$ bekannt.

Für ${\displaystyle k=2}$ sei ${\displaystyle A_{2}=(1,a)}$

Dann ist ${\displaystyle n_{h}(A_{2})=(h+3-a)\,a-2}$ für ${\displaystyle h\geq a-2}$.

Außerdem ist (A. Stöhr 1955,^[3] A. Henrici 1965, R. G. Stanton u. a. 1974)

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

Mit ${\displaystyle \left\lfloor x\right\rfloor }$ der größten ganzen Zahl kleiner gleich ${\displaystyle x}$. Die zugehörige ${\displaystyle (h,2)}$-optimale Menge ist ${\displaystyle A_{2}=\left(1,\left\lfloor {\frac {h+3}{2}}\right\rfloor \right)}$.

Für ${\displaystyle k=3}$ und ${\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}}}$

für ${\displaystyle h\geq 34}$ (Gerd Hofmeister).^[4] Die Gleichheit in der unteren Schranke ist für ${\displaystyle h=0\mod 9}$ erfüllt. Hofmeister löste damit das globale Problem für ${\displaystyle k=3}$. Das lokale Problem (Bestimmung von ${\displaystyle n_{h}(A_{3})}$) wurde von Øystein J. Rødseth angegangen, der eine allgemeine Methode basierend auf einem Kettenbruch-Algorithmus entwickelte. Ernst Sejersted Selmer gab darauf aufbauend asymptotische Formeln, die die meisten Fälle ${\displaystyle A_{3}}$ abdeckten.^[5]

S. Mossige zeigte für ${\displaystyle k=4}$, dass asymptotisch

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

Wobei rechts ein Landau-Symbol verwendet wurde. Mit Kirfel zeigte er auch, dass die Abschätzung bestmöglich ist.^[6] Kirfel zeigte, dass der Grenzwert ${\displaystyle c_{k}=\lim _{h\to \infty }{\frac {n(h,k)}{{({\frac {h}{k}})}^{k}}}}$ für alle ${\displaystyle k\geq 1}$ existiert. Er gab auch den Wert von ${\displaystyle c_{5}}$ an.

Asymptotische Grenzen für festes ${\displaystyle h}$ und große ${\displaystyle k}$ fand Hans Rohrbach 1937:^[7]

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

Dabei gilt die untere Schranke allgemein und es gilt auch ${\displaystyle \left({\frac {h}{k}}\right)^{k}\leq n(h,k)}$. Die beste untere Schranke für große ${\displaystyle k}$ und feste ${\displaystyle h}$ stammt von Hofmeister^[8] unter Verwendung von Ergebnissen von R. Windecker. Die beste obere Schranke für festes k stammt von Rødseth:^[9][10]

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

Speziell für ${\displaystyle h=2}$ fand Rohrbach:

${\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)}$

mit ${\displaystyle d_{1}=1,d_{2}=1{,}9968}$. A. Mrose verbesserte auf ${\displaystyle d_{1}={\frac {8}{7}}}$ und W. Klotz auf ${\displaystyle d_{2}=1{,}9208}$.

Richard Guy vermutete, dass für große ${\displaystyle h}$ die ${\displaystyle n(h,k)}$ durch eine endliche Anzahl von Polynomen in ${\displaystyle h}$ vom Grad ${\displaystyle k}$ gegeben sind.^[11]

Für variable ${\displaystyle h}$ ist das Problem NP-schwer^[12]. Bei festem ${\displaystyle h}$ ist es dagegen in polynomialer Zeit lösbar.

Anwendungen fand das Problem zum Beispiel bei der optimalen Zuteilung von Index-Registern bei Computern oder optimalen Verkabelungsmustern in assoziativen Cache-Speichern.^[13]

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

• Eric Weisstein: Postage stamp problem, mathworld
• Briefmarkenproblem, Spektrum Lexikon der Mathematik

1. ↑ Guy, Unsolved problems in number theory, S. 123.
2. ↑ Guy, Unsolved problems in number theory, S. 123
3. ↑ Stöhr, Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe, 2 Teile, J. Reine Angew. Math., Band 194, 1955, S. 40–65, 111–140
4. ↑ Hofmeister, Asymptotische Abschätzungen für dreielementige Extremalbasen in natürlichen Zahlen, J. Reine Angew. Math., Band 232, 1968, S. 77–101
5. ↑ Selmer, The local postage stamp problem, 3 Teile, Universität Bergen 1986, 1990
6. ↑ Guy, Unsolved problems in number theory, S. 123
7. ↑ Rohrbach, Ein Beitrag zur additiven Zahlentheorie, Math. Z., Band 42, 1937, S. 1–30
8. ↑ Hofmeister, Endliche additive Zahlentheorie, Kapitel 1, Das Reichweitenproblem, Universität Mainz 1976. Nach Alter, Barnett, American Mathematical Monthly, Band 87, 1980, S. 206f
9. ↑ Guy, Unsolved problems in number theory, S. 124
10. ↑ Rødseth, An upper bound for the h-range of the post-stamp problem, Acta Arithmetica, Band 54, 1990, S. 301–306
11. ↑ Alter, Barnett, American Mathematical Monthly, 87, 1980, S. 207, mit expliziter Darstellung der Vermutung für k=2,3
12. ↑ Jeffrey Shallit, The computational complexity of the local postage stamp problem. SIGACT News, Band 33, März 2002, S. 90–94
13. ↑ Alter, Barnett, American Mathematical Monthly, 87, 1980, S. 207