Münzproblem

Problem aus dem Gebiet der Zahlentheorie
(Weitergeleitet von Frobenius-Problem)

Das Münzproblem (auch als Frobenius-Problem bekannt) aus dem Gebiet der Zahlentheorie stellt die Frage, welche natürliche Zahlen sich in der Form schreiben lassen, wobei bis vorgegebene teilerfremde Zahlen sind und die Koeffizienten bis als natürliche Zahlen (einschließlich 0) gewählt werden sollen. Genauer wird nach der größten Zahl gefragt, die sich nicht in dieser Form schreiben lässt, sie wird als Frobenius-Zahl bezeichnet.

Ein Haufen von Münzen
Mit nur 2- und 5-Cent-Münzen lässt sich ohne Wechselgeld ein Preis von 3 Cent nicht bezahlen, jeder höhere Preis dagegen schon.

Das Problem geht auf Ferdinand Georg Frobenius zurück, der Name kommt von der anschaulichen Formulierung der Fragestellung, welche Preise sich mit einem vorgegebenen Satz an Münzen mit den Werten bis bezahlen lassen. Den Fall konnte James Joseph Sylvester 1884 vollständig lösen, für mehr Zahlen scheint es dagegen keine einfache Formel zu geben.

Verwandt damit ist das Briefmarkenproblem.

Hintergrund

Bearbeiten

Sind die Zahlen   bis   nicht teilerfremd, sondern besitzen einen gemeinsamen Teiler  , so sind alle Zahlen, die als   geschrieben werden können, ebenfalls durch   teilbar. In diesem Fall kann es also keine größte Zahl geben, die sich nicht in der gewünschten Form schreiben lässt.

Sind die Zahlen   bis   dagegen wie gefordert teilerfremd, so gibt es nach dem Lemma von Bézout eine Darstellung   mit ganzen Zahlen   bis  . Multipliziert man diese Gleichung mit  , so erhält man eine Darstellung für jede natürliche Zahl, allerdings mit ganzen Koeffizienten statt natürlichen. Ist jedoch   hinreichend groß, so können alle Koeffizienten als natürliche Zahlen gewählt werden. Die Frage, wie groß   sein muss, ist gerade das Münzproblem. Die größte Zahl, die sich für gegebene   bis   nicht mit nicht-negativen Koeffizienten schreiben lässt, wird häufig mit   bezeichnet und Frobenius-Zahl genannt.

Satz von Sylvester

Bearbeiten

Für den Fall   liefert der folgende Sylvester zugeschriebene Satz die Antwort: Sind   und   zwei teilerfremde natürliche Zahlen, so ist die größte Zahl, die sich nicht in der Form   mit nicht-negativen ganzen Zahlen   und   schreiben lässt,  .

Der Beweis besteht aus zwei Teilen: Zum einen muss gezeigt werden, dass sich alle Zahlen größer als   in der gewünschten Form schreiben lassen, zum anderen ist nachzuweisen, dass   keine solche Darstellung besitzt.

Sei also zunächst  . Nach der Vorbemerkung gibt es zumindest ganze Zahlen   und   mit  . Setzt man   und  , so ist auch   eine Darstellung. Bei geeigneter Wahl von   kann also o. B. d. A.   angenommen werden. Für das zugehörige   gilt:

 

Da   durch   teilbar ist, gilt somit  , folglich ist   wie gewünscht nicht negativ.

Der zweite Teil ist ein Widerspruchsbeweis: Wäre   eine solche Darstellung, so wäre  . Die linke Seite und der erste Summand der rechten Seite sind durch   teilbar, daher muss auch der zweite Summand ein Vielfaches von   sein. Da   und   teilerfremd sind, müsste   ein Vielfaches von   und als positive Zahl damit mindestens   sein. Analog wäre  , die rechte Seite hätte damit mindestens die Größe  , was einen Widerspruch darstellt. Folglich kann   nicht mit nicht-negativen Koeffizienten dargestellt werden.

Darstellungen mit mehr als zwei Zahlen

Bearbeiten

Für   ist keine Formel bekannt, die die größte nicht darstellbare Zahl liefert, und es ist wahrscheinlich, dass es auch keine geschlossene Formel gibt. Stattdessen gibt es eine Reihe von Abschätzungen, Formeln für Spezialfälle und Algorithmen unterschiedlichen Laufzeitverhaltens.

Abschätzungen

Bearbeiten

Für den Fall   ist die Abschätzung   als untere Schranke bekannt.[1]

Von Issai Schur stammt die Abschätzung  , die eine obere Schranke liefert.[2]

Spezialfälle

Bearbeiten

Für den Fall   und  ,   und   mit paarweise teilerfremden Zahlen  ,   und   gilt  . Dies war eine Aufgabe bei der Internationalen Mathematik-Olympiade 1983.[3]

Ebenfalls bekannt ist die Frobenius-Zahl für arithmetische und geometrische Folgen beliebiger Länge. Sind   und   teilerfremd, so gilt:[4]

 

Für teilerfremde Zahlen   und   gilt für die geometrische Folge mit Quotient  :[5]

 

Algorithmen

Bearbeiten

Viele Algorithmen für das Münzproblem basieren auf Graphen. Dazu wird die Gleichung modulo   betrachtet, also  . Auf den Knoten   wird ein gewichteter Digraph konstruiert, wobei es einen Bogen vom Knoten   zum Knoten   genau dann gibt, wenn es ein   gibt ( ) mit  , das Gewicht des Bogens ist  . Man kann zeigen, dass man die Frobenius-Zahl dadurch erhalten kann, dass man für alle Knoten   nach dem kürzesten Pfad von 0 nach   sucht und die Länge   des längsten dieser Pfade bestimmt. Dann ist die Frobenius-Zahl  . Mit Hilfe des Dijkstra-Algorithmus lässt sich somit die Frobenius-Zahl leicht berechnen. Nutzt man zusätzlich die besonderen Symmetrie-Eigenschaften des Graphen aus, so kann man schnellere Algorithmen entwickeln.[2]

Ravi Kannan entwickelte einen Algorithmus, der für jedes feste   in polynomialer Zeit (bezogen auf   bis  ) die Frobenius-Zahl berechnet. Das allgemeine Problem, also wenn auch   variabel ist, ist dagegen NP-schwer.[6]

Beispiel

Bearbeiten
 
Der Graph zum McNugget-Problem. Die blauen Bögen haben ein Gewicht von je 9, die roten von je 20.

Ein häufig verwendetes Beispiel sind die McNugget-Zahlen. Gefragt ist, welche Anzahlen Chicken McNuggets man kaufen kann, wenn man sie aus den klassischen Verpackungsgrößen zu 6, 9 und 20 Stück zusammenstellt. Die Abschätzungen liefern, dass   gilt. Die exakte Zahl lässt sich leicht bestimmen, hier soll exemplarisch die Methode mit Hilfe des Graphen verwendet werden. Dieser hat sechs Knoten. Die Bögen, die zur Zahl 9 gehören, sind in der Darstellung blau gezeichnet und teilen die Knoten in drei Paare ein, die roten Bögen gehören zur Zahl 20 und bilden zwei Dreiergruppen. Insgesamt ist der Graph stark zusammenhängend, da die Zahlen teilerfremd sind. Als kürzeste Wege vom Knoten 0 aus ergeben sich (von mehreren Möglichkeiten ist immer nur eine angegeben):

  • 0 → 2 → 4 → 1 (Länge  )
  • 0 → 2 (Länge 20)
  • 0 → 3 (Länge 9)
  • 0 → 2 → 4 (Länge  )
  • 0 → 2 → 5 (Länge  )

Der längste dieser Wege hat damit die Länge  , folglich gilt  . Der Graph liefert auch zu jeder darstellbaren Zahl eine mögliche Darstellung. Will man etwa 47 Chicken McNuggets, so sucht man wegen   nach dem kürzesten Weg von 0 nach 5. Dieser besteht aus einem blauen und einem roten Bogen, sodass man zunächst eine Packung zu 9 und eine zu 20 Chicken McNuggets kaufen sollte. Für die restlichen 18 nimmt man drei 6-Packungen.

Einzelnachweise

Bearbeiten
  1. Matthias Beck, Shelemyahu Zacks: Refined upper bounds for the linear Diophantine problem of Frobenius. In: Advances in Applied Mathematics. Vol. 32, 2004. S. 454–467. doi:10.1016/S0196-8858(03)00055-1
  2. a b Dale Beihoffer, Jemimah Hendry, Albert Nijenhuis, Stan Wagon: Faster algorithms for Frobenius numbers. In: Electronic Journal of Combinatorics. Vol 12, 2005. (online)
  3. 3. Aufgabe der IMO 1983 (online)
  4. Jorge Ramírez Alfonsín: The Diophantine Frobenius problem. Oxford University Press, 2005. S. 59f.
  5. Darren C. Ong, Vadim Ponomarenko: The Frobenius Number of Geometric Sequences. In: INTEGERS: the Electronic Journal of Combinatorial Number Theory Vol. 8, 1, 2008. (online)
  6. Ravi Kannan: Lattice translates of a polytope and the Frobenius problem. In: Combinatorica. Vol. 12, 2. S. 161–177. doi:10.1007/BF01204720
Bearbeiten