Briefmarkenproblem

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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

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

Gegeben sind eine Menge positiver ganzer Zahlen , . Gesucht wird die kleinste Zahl , die sich nicht als Summe darstellen lässt mit und für .

Die größte Zahl, für die sich alle Vorgänger und sie selbst als eine solche Summe darstellen lassen, heißt -Reichweite von Es gilt: .

Das Problem wird auch so gestellt, dass und gegeben werden, und die Menge gesucht wird, die die Reichweite maximiert. Diese Mengen werden -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 zu bestimmen.[2]

Zum Beispiel ist für maximal drei Briefmarken () mit Briefmarken-Werten aus jeder Wert bis darstellbar (Reichweite ). Ein Wert von ist nicht mehr mit drei Briefmarken aus dieser Menge darstellbar, man benötigt mindestens vier. Andererseits ist das keine optimale Menge, denn . Optimale Mengen für diese Kombination von und sind , und .

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

Aus elementaren Überlegungen der Kombinatorik folgt (rechts steht der Binomialkoeffizient).

Exakte Lösungsformeln sind für bekannt.

Für sei

Dann ist für .

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

Mit der größten ganzen Zahl kleiner gleich . Die zugehörige -optimale Menge ist .

Für und :

für (Gerd Hofmeister).[4] Die Gleichheit in der unteren Schranke ist für erfüllt. Hofmeister löste damit das globale Problem für . Das lokale Problem (Bestimmung von ) 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 abdeckten.[5]

S. Mossige zeigte für , dass asymptotisch

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 für alle existiert. Er gab auch den Wert von an.

Asymptotische Grenzen für festes und große fand Hans Rohrbach 1937:[7]

Dabei gilt die untere Schranke allgemein und es gilt auch . Die beste untere Schranke für große und feste 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]

Speziell für fand Rohrbach:

mit . A. Mrose verbesserte auf und W. Klotz auf .

Richard Guy vermutete, dass für große die durch eine endliche Anzahl von Polynomen in vom Grad gegeben sind.[11]

Für variable ist das Problem NP-schwer[12]. Bei festem 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.[13]

  • 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

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  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