Münzproblem
Das Münzproblem (auch als Frobenius-Problem bekannt) aus dem Gebiet der Zahlentheorie stellt die Frage, welche natürliche Zahlen sich in der Form <math>m = x_1 a_1 + x_2 a_2 + \dots + x_n a_n</math> schreiben lassen, wobei <math>a_1</math> bis <math>a_n</math> vorgegebene teilerfremde Zahlen sind und die Koeffizienten <math>x_1</math> bis <math>x_n</math> 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 <math>a_1</math> bis <math>a_n</math> bezahlen lassen. Den Fall <math>n = 2</math> 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 <math>a_1</math> bis <math>a_n</math> nicht teilerfremd, sondern besitzen einen gemeinsamen Teiler <math>d</math>, so sind alle Zahlen, die als <math>m = x_1 a_1 + \dots + x_n a_n</math> geschrieben werden können, ebenfalls durch <math>d</math> 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 <math>a_1</math> bis <math>a_n</math> dagegen wie gefordert teilerfremd, so gibt es nach dem Lemma von Bézout eine Darstellung <math>1 = x_1 a_1 + \dots + x_n a_n</math> mit ganzen Zahlen <math>x_1</math> bis <math>x_n</math>. Multipliziert man diese Gleichung mit <math>m</math>, so erhält man eine Darstellung für jede natürliche Zahl, allerdings mit ganzen Koeffizienten statt natürlichen. Ist jedoch <math>m</math> hinreichend groß, so können alle Koeffizienten als natürliche Zahlen gewählt werden. Die Frage, wie groß <math>m</math> sein muss, ist gerade das Münzproblem. Die größte Zahl, die sich für gegebene <math>a_1</math> bis <math>a_n</math> nicht mit nicht-negativen Koeffizienten schreiben lässt, wird häufig mit <math>g(a_1, \dots, a_n)</math> bezeichnet und Frobenius-Zahl genannt.
Satz von Sylvester[Bearbeiten]
Für den Fall <math>n = 2</math> liefert der folgende Sylvester zugeschriebene Satz die Antwort: Sind <math>a</math> und <math>b</math> zwei teilerfremde natürliche Zahlen, so ist die größte Zahl, die sich nicht in der Form <math>m = xa + yb</math> mit nicht-negativen ganzen Zahlen <math>x</math> und <math>y</math> schreiben lässt, <math>m = g(a, b) = ab - a - b</math>.
Der Beweis besteht aus zwei Teilen: Zum einen muss gezeigt werden, dass sich alle Zahlen größer als <math>ab - a - b</math> in der gewünschten Form schreiben lassen, zum anderen ist nachzuweisen, dass <math>ab - a - b</math> keine solche Darstellung besitzt.
Sei also zunächst <math>m > ab - a - b</math>. Nach der Vorbemerkung gibt es zumindest ganze Zahlen <math>x</math> und <math>y</math> mit <math>m = xa + yb</math>. Setzt man <math>x' := x + tb</math> und <math>y' := y - ta</math>, so ist auch <math>m = x'a + y'b</math> eine Darstellung. Bei geeigneter Wahl von <math>t</math> kann also o. B. d. A. <math>0 \leq x < b</math> angenommen werden. Für das zugehörige <math>y</math> gilt:
- <math>yb = m - xa \geq ab - a - b + 1 - (b - 1)a = -b + 1 > -b</math>
Da <math>yb</math> durch <math>b</math> teilbar ist, gilt somit <math>yb \geq 0</math>, folglich ist <math>y</math> wie gewünscht nicht negativ.
Der zweite Teil ist ein Widerspruchsbeweis: Wäre <math>ab - a - b = xa + yb</math> eine solche Darstellung, so wäre <math>ab = a(x + 1) + b(y + 1)</math>. Die linke Seite und der erste Summand der rechten Seite sind durch <math>a</math> teilbar, daher muss auch der zweite Summand ein Vielfaches von <math>a</math> sein. Da <math>a</math> und <math>b</math> teilerfremd sind, müsste <math>y + 1</math> ein Vielfaches von <math>a</math> und als positive Zahl damit mindestens <math>a</math> sein. Analog wäre <math>x + 1 \geq b</math>, die rechte Seite hätte damit mindestens die Größe <math>2ab</math>, was einen Widerspruch darstellt. Folglich kann <math>m = ab - a - b</math> nicht mit nicht-negativen Koeffizienten dargestellt werden.
Darstellungen mit mehr als zwei Zahlen[Bearbeiten]
Für <math>n > 2</math> ist keine einfache Formel bekannt, die die größte nicht darstellbare Zahl liefert, und es ist wahrscheinlich, dass es auch keine einfache geschlossene Formel gibt. Es gibt eine Reihe von Abschätzungen, Formeln für Spezialfälle und Algorithmen unterschiedlichen Laufzeitverhaltens. Für <math>n = 3</math> wurde 2017 eine Formel veröffentlicht, die die Frobenius-Zahl <math>g(a_1, a_2, a_3) </math> für die verschiedenen Fälle von <math>a_1 </math>, <math>a_2 </math> und <math>a_3 </math> abdeckt.<ref>Amitabha Tripathi: Formulae for the Frobenius number in three variables. In: Journal of Number Theory. Band 170, 1. Januar 2017, ISSN 0022-314X, S. 368–389, doi:10.1016/j.jnt.2016.05.027 (sciencedirect.com [abgerufen am 22. April 2025]).</ref> Zudem gibt es ähnlich zu Willans Primzahl-Formel Möglichkeiten, algorithmisch arbeitende Formeln zu generieren, welche zwar für ein beliebiges <math>n</math> funktionieren, jedoch im Allgemeinen nicht sehr effizient sind.<ref>Janosch Meier: Algorithmic Formula for the Frobenius Numbers. Februar 2025 (hal.science [abgerufen am 22. April 2025]).</ref>
Abschätzungen[Bearbeiten]
Für den Fall <math>n = 3</math> ist die Abschätzung <math>g(a_1, a_2, a_3) \geq \sqrt{3 a_1 a_2 a_3} - a_1 - a_2 - a_3</math> als untere Schranke bekannt.<ref>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</ref>
Von Issai Schur stammt die Abschätzung <math>g(a_1, \dots, a_n) \leq \min(a_i) \max(a_i) - \min(a_i) - \max(a_i)</math>, die eine obere Schranke liefert.<ref name="beihoffer">Dale Beihoffer, Jemimah Hendry, Albert Nijenhuis, Stan Wagon: Faster algorithms for Frobenius numbers. In: Electronic Journal of Combinatorics. Vol 12, 2005. (online)</ref>
Spezialfälle[Bearbeiten]
Für den Fall <math>n = 3</math> und <math>a_1 = ab</math>, <math>a_2 = bc</math> und <math>a_3 = ac</math> mit paarweise teilerfremden Zahlen <math>a</math>, <math>b</math> und <math>c</math> gilt <math>g(a_1, a_2, a_3) = 2abc - ab - bc - ac</math>. Dies war eine Aufgabe bei der Internationalen Mathematik-Olympiade 1983.<ref>3. Aufgabe der IMO 1983 (online)</ref>
Ebenfalls bekannt ist die Frobenius-Zahl für arithmetische und geometrische Folgen beliebiger Länge. Sind <math>a</math> und <math>d</math> teilerfremd, so gilt:<ref>Jorge Ramírez Alfonsín: The Diophantine Frobenius problem. Oxford University Press, 2005. S. 59f.</ref>
- <math>g(a, a + d, a + 2d, \dots, a + (n - 1)d) = \left(\left\lfloor\frac{a - 2}{n - 1}\right\rfloor + 1\right) a + (d - 1) (a - 1) - 1</math>
Für teilerfremde Zahlen <math>p</math> und <math>q</math> gilt für die geometrische Folge mit Quotient <math>\tfrac{p}{q}</math>:<ref>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)</ref>
- <math>g(q^{n - 1}, q^{n - 2} p, q^{n - 3} p^2, \dots, p^{n - 1}) = p^{n - 2} (pq - p - q) + \frac{(p - 1) q^2 (q^{n - 2} - p^{n - 2})}{q - p}</math>
Algorithmen[Bearbeiten]
Viele Algorithmen für das Münzproblem basieren auf Graphen. Dazu wird die Gleichung modulo <math>a_1</math> betrachtet, also <math>m \equiv x_2 a_2 + \dots + x_n a_n \mod a_1</math>. Auf den Knoten <math>0, 1, \dots, a_1 - 1</math> wird ein gewichteter Digraph konstruiert, wobei es einen Bogen vom Knoten <math>u</math> zum Knoten <math>v</math> genau dann gibt, wenn es ein <math>a_i</math> gibt (<math>1 < i \leq n</math>) mit <math>u + a_i \equiv v \mod a_1</math>, das Gewicht des Bogens ist <math>a_i</math>. Man kann zeigen, dass man die Frobenius-Zahl dadurch erhalten kann, dass man für alle Knoten <math>v</math> nach dem kürzesten Pfad von 0 nach <math>v</math> sucht und die Länge <math>D</math> des längsten dieser Pfade bestimmt. Dann ist die Frobenius-Zahl <math>D - a_1</math>. 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.<ref name="beihoffer" />
Ravi Kannan entwickelte einen Algorithmus, der für jedes feste <math>n</math> in polynomialer Zeit (bezogen auf <math>\log a_1</math> bis <math>\log a_n</math>) die Frobenius-Zahl berechnet. Das allgemeine Problem, also wenn auch <math>n</math> variabel ist, ist dagegen NP-schwer.<ref>Ravi Kannan: Lattice translates of a polytope and the Frobenius problem. In: Combinatorica. Vol. 12, 2. S. 161–177. doi:10.1007/BF01204720</ref>
Beispiel[Bearbeiten]
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 <math>\sqrt{3 \cdot 6 \cdot 9 \cdot 20} - 6 - 9 - 20 \approx 19 \leq g(6, 9, 20) \leq 94 = 6 \cdot 20 - 6 - 20</math> 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 <math>20 + 20 + 9 = 49</math>)
- 0 → 2 (Länge 20)
- 0 → 3 (Länge 9)
- 0 → 2 → 4 (Länge <math>20 + 20 = 40</math>)
- 0 → 2 → 5 (Länge <math>20 + 9 = 29</math>)
Der längste dieser Wege hat damit die Länge <math>D = 49</math>, folglich gilt <math>g(6, 9, 20) = 49 - 6 = 43</math>. Der Graph liefert auch zu jeder darstellbaren Zahl eine mögliche Darstellung. Will man etwa 47 Chicken McNuggets, so sucht man wegen <math>47 \equiv 5 \mod 6</math> 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]
<references />
Weblinks[Bearbeiten]
- Eric W. Weisstein: Coin Problem. In: MathWorld (englisch).