Direkt zum Inhalt

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 ≤ kn 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.
  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

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.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.