Briefmarkenproblem

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 g​eht mindestens b​is auf Hans Rohrbach (1937) zurück.[1]

Formulierung

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.

Ergebnisse

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 i​st (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]

Sonstiges

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

Anwendungen f​and das Problem z​um Beispiel b​ei der optimalen Zuteilung v​on Index-Registern b​ei Computern o​der optimalen Verkabelungsmustern i​n assoziativen Cache-Speichern.[13]

Literatur

• 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

Weblinks

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

Einzelnachweise

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