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]

Formulierung

Bearbeiten

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.

Ergebnisse

Bearbeiten

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]

Sonstiges

Bearbeiten

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]

Literatur

Bearbeiten
  • 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
Bearbeiten

Einzelnachweise

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