Briefmarkenproblem

Das Briefmarkenproblem ist ein Problem der Kombinatorik und additiven Zahlentheorie. Seien $k$ Briefmarken mit Werten $a_{i}$ gegeben. Dann wird nach der kleinsten Zahl gefragt, die nicht als Summe von höchstens $h$ Briefmarken aus dieser Menge dargestellt werden kann (da nur $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 $h$.

Das Problem geht mindestens bis auf Hans Rohrbach (1937) zurück.

Formulierung

Gegeben sind eine Menge positiver ganzer Zahlen $A_{k}=(a_{1},\cdots ,a_{k})$, $a_{1}=1<a_{2}<a_{3}<\cdots <a_{k}$. Gesucht wird die kleinste Zahl $N_{h}(A_{k})$, die sich nicht als Summe $\sum _{j=1}^{k}x_{j}\,a_{j}$ darstellen lässt mit $\sum _{j=1}^{k}x_{j}\leq h$ und $x_{j}\in \mathbb {N} _{0}$ für $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 $h$-Reichweite $n_{h}(A_{k})$ von $A_{k}$ Es gilt: $n_{h}(A_{k})=N_{h}(A_{k})-1$.

Das Problem wird auch so gestellt, dass $h$ und $k$ gegeben werden, und die Menge $A_{k}$ gesucht wird, die die Reichweite $n_{h}(k)=n(h,k)$ maximiert. Diese Mengen werden $(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 $A_{k}$ zu bestimmen.

Zum Beispiel ist für maximal drei Briefmarken ($h=3$) mit Briefmarken-Werten aus $A_{4}=(a_{1}=1,a_{2}=2,a_{3}=5,a_{4}=20)$ jeder Wert bis $n_{3}(A_{4})=12$ darstellbar (Reichweite $12$). Ein Wert von $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 $n(3,4)=23$. Optimale Mengen für diese Kombination von $h$ und $k$ sind $\{1,3,6,10\}$, $\{1,4,6,15\}$ und $\{1,4,7,9\}$.

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

Ergebnisse

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

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

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

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

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

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

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

Für $k=3$ und $n_{h}(A_{3})=n(h,3)$:

${\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 $h\geq 34$ (Gerd Hofmeister). Die Gleichheit in der unteren Schranke ist für $h=0\mod 9$ erfüllt. Hofmeister löste damit das globale Problem für $k=3$. Das lokale Problem (Bestimmung von $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 $A_{3}$ abdeckten.

S. Mossige zeigte für $k=4$, dass asymptotisch

$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. Kirfel zeigte, dass der Grenzwert $c_{k}=\lim _{h\to \infty }{\frac {n(h,k)}{{({\frac {h}{k}})}^{k}}}$ für alle $k\geq 1$ existiert. Er gab auch den Wert von $c_{5}$ an.

Asymptotische Grenzen für festes $h$ und große $k$ fand Hans Rohrbach 1937:

$\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 $\left({\frac {h}{k}}\right)^{k}\leq n(h,k)$. Die beste untere Schranke für große $k$ und feste $h$ stammt von Hofmeister unter Verwendung von Ergebnissen von R. Windecker. Die beste obere Schranke für festes k stammt von Rødseth:

$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 $h=2$ fand Rohrbach:

$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 $d_{1}=1,d_{2}=1{,}9968$. A. Mrose verbesserte auf $d_{1}={\frac {8}{7}}$ und W. Klotz auf $d_{2}=1{,}9208$.

Richard Guy vermutete, dass für große $h$ die $n(h,k)$ durch eine endliche Anzahl von Polynomen in $h$ vom Grad $k$ gegeben sind.

Sonstiges

Für variable $h$ ist das Problem NP-schwer. Bei festem $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.

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