Münzproblem

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Frobenius-Problem)
Zur Navigation springen Zur Suche springen
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 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.

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.

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 | Quelltext 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 | Quelltext 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.

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]

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]

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]

Der Graph zeigt die Zahlen von 0 bis 5, die durch Pfeile miteinander verbunden sind: Von 0 führt ein roter Pfeil zur 2, von dort einer zur 4, von dort zurück zur 0. Ebenso gibt es von 1 nach 3, von 3 nach 5 und von 5 nach 1 rote Pfeile. Zwischen 0 und 3 befindet sich ein blauer Doppelpfeil, ebenso zwischen 1 und 4, sowie zwischen 2 und 5.
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 | Quelltext 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