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\le h$ und $x_j\in {\mathbb{N}}_0$ für $1\le j\le 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)<(\genfrac{}{}{0ex}{}{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\ge a-2$.

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

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

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

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\le n_h(A_3)\le \frac{4}{81}{h}^3+\frac{2}{3}{h}^2+\frac{71}{27}h-\frac{1}{81}$

für $h\ge 34$ (Gerd Hofmeister). Die Gleichheit in der unteren Schranke ist für $h=0mod9$ 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)\ge 2,008{\left(\frac{h}{4}\right)}^4+𝒪(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=\underset{h\to \mathrm{\infty }}{\lim }\frac{n(h,k)}{{(\frac{h}{k})}^k}$ für alle $k\ge 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\le n(h,k)\le \frac{k^h}{h!}+𝒪(k^{h-1})$

Dabei gilt die untere Schranke allgemein und es gilt auch ${\left(\frac{h}{k}\right)}^k\le 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)\le \frac{{(k-1)}^{k-2}}{(k-2)!}{\left(\frac{h}{k}\right)}^k+𝒪(h^{k-1})$

Speziell für $h=2$ fand Rohrbach:

$d_1{\left(\frac{k}{2}\right)}^2+𝒪(k)\le n(2,k)\le d_2\frac{k^2}{2}+𝒪(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