Lexikon der Mathematik: Briefmarkenproblem
das folgende zahlentheoretische Problem:
Zu einer gegebenen Teilmenge A ⊂ ℕ0 und einer gegebenen Anzahl h ist die sogenannte h-Reichweite von A gesucht, d.i. die größte Zahl n = n(h, A) so, daß sich alle ganzen Zahlen k mit 0 ≤ k ≤ n als Summe von höchstens h Zahlen aus A darstellen lassen.
Der Name kommt von folgendem Aufgabentyp: Gegeben seien z. B. Briefmarken der Werte 10 Pf, 50 Pf und 60 Pf. Welche Beträge kann man mit höchstens vier (nicht notwendig verschiedenen) Marken zusammenstellen? Antwort: Jedes ganzzahlige Vielfache von 10 Pf zwischen 0 und 240 Pf.
In der abstrakten Formulierung setzt man meist 0 ∈ A voraus und fragt nach der Menge derjenigen Zahlen, die als Summe von genau h (nicht notwendig verschiedenen) Zahlen aus A darstellbar sind. Ist 1 ∉ A, so ist n(h, A) = 0; also kann man o. B. d. A. auch 1 ∈ A voraussetzen. Für die h-Reichweite einer Menge A ⊂ ℕ0 mit k Elementen > 0 gilt die Abschätzung
\begin{eqnarray}n(h,A)\lt (h+k\\ k).\end{eqnarray}
Interessant sind Mengen A mit k positiven Elementen und möglichst großer Reichweite; solche Mengen nennt man (h, k)-optimal. Für k = 2 ist die Menge
\begin{eqnarray}A=\{0,1,\lfloor \frac{h+3}{2}\rfloor \}\end{eqnarray}
(h, 2)-optimal; sie hat die Reichweite\begin{eqnarray}n(h,A)=\lfloor \frac{{h}^{2}+6h+1}{4}\rfloor .\end{eqnarray}
Für die Reichweite einer (h, k)-optimalen Menge gibt es Abschätzungen; die präzise Bestimmung der Reichweiten und dazugehöriger (h, k)-optimaler Mengen ist ein offenes Problem.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.