Münzproblem

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 $m=x_{1}a_{1}+x_{2}a_{2}+\dots +x_{n}a_{n}$ schreiben lassen, wobei $a_{1}$ bis $a_{n}$ vorgegebene teilerfremde Zahlen sind und die Koeffizienten $x_{1}$ bis $x_{n}$ 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 $a_{1}$ bis $a_{n}$ bezahlen lassen. Den Fall $n=2$ 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

Sind die Zahlen $a_{1}$ bis $a_{n}$ nicht teilerfremd, sondern besitzen einen gemeinsamen Teiler $d$, so sind alle Zahlen, die als $m=x_{1}a_{1}+\dots +x_{n}a_{n}$ geschrieben werden können, ebenfalls durch $d$ 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 $a_{1}$ bis $a_{n}$ dagegen wie gefordert teilerfremd, so gibt es nach dem Lemma von Bézout eine Darstellung $1=x_{1}a_{1}+\dots +x_{n}a_{n}$ mit ganzen Zahlen $x_{1}$ bis $x_{n}$. Multipliziert man diese Gleichung mit $m$, so erhält man eine Darstellung für jede natürliche Zahl, allerdings mit ganzen Koeffizienten statt natürlichen. Ist jedoch $m$ hinreichend groß, so können alle Koeffizienten als natürliche Zahlen gewählt werden. Die Frage, wie groß $m$ sein muss, ist gerade das Münzproblem. Die größte Zahl, die sich für gegebene $a_{1}$ bis $a_{n}$ nicht mit nicht-negativen Koeffizienten schreiben lässt, wird häufig mit $g(a_{1},\dots ,a_{n})$ bezeichnet und Frobenius-Zahl genannt.

Satz von Sylvester

Für den Fall $n=2$ liefert der folgende Sylvester zugeschriebene Satz die Antwort: Sind $a$ und $b$ zwei teilerfremde natürliche Zahlen, so ist die größte Zahl, die sich nicht in der Form $m=xa+yb$ mit nicht-negativen ganzen Zahlen $x$ und $y$ schreiben lässt, $m=g(a,b)=ab-a-b$.

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

Sei also zunächst $m>ab-a-b$. Nach der Vorbemerkung gibt es zumindest ganze Zahlen $x$ und $y$ mit $m=xa+yb$. Setzt man $x':=x+tb$ und $y':=y-ta$, so ist auch $m=x'a+y'b$ eine Darstellung. Bei geeigneter Wahl von $t$ kann also o. B. d. A. $0\leq x<b$ angenommen werden. Für das zugehörige $y$ gilt:

$yb=m-xa\geq ab-a-b+1-(b-1)a=-b+1>-b$

Da $yb$ durch $b$ teilbar ist, gilt somit $yb\geq 0$, folglich ist $y$ wie gewünscht nicht negativ.

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

Darstellungen mit mehr als zwei Zahlen

Für $n>2$ 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

Für den Fall $n=3$ ist die Abschätzung $g(a_{1},a_{2},a_{3})\geq {\sqrt {3a_{1}a_{2}a_{3}}}-a_{1}-a_{2}-a_{3}$ als untere Schranke bekannt.

Von Issai Schur stammt die Abschätzung $g(a_{1},\dots ,a_{n})\leq \min(a_{i})\max(a_{i})-\min(a_{i})-\max(a_{i})$, die eine obere Schranke liefert.

Spezialfälle

Für den Fall $n=3$ und $a_{1}=ab$, $a_{2}=bc$ und $a_{3}=ac$ mit paarweise teilerfremden Zahlen $a$, $b$ und $c$ gilt $g(a_{1},a_{2},a_{3})=2abc-ab-bc-ac$. Dies war eine Aufgabe bei der Internationalen Mathematik-Olympiade 1983.

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

$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$

Für teilerfremde Zahlen $p$ und $q$ gilt für die geometrische Folge mit Quotient ${\tfrac {p}{q}}$:

$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}}$

Algorithmen

Viele Algorithmen für das Münzproblem basieren auf Graphen. Dazu wird die Gleichung modulo $a_{1}$ betrachtet, also $m\equiv x_{2}a_{2}+\dots +x_{n}a_{n}\mod a_{1}$. Auf den Knoten $0,1,\dots ,a_{1}-1$ wird ein gewichteter Digraph konstruiert, wobei es einen Bogen vom Knoten $u$ zum Knoten $v$ genau dann gibt, wenn es ein $a_{i}$ gibt ($1<i\leq n$) mit $u+a_{i}\equiv v\mod a_{1}$, das Gewicht des Bogens ist $a_{i}$. Man kann zeigen, dass man die Frobenius-Zahl dadurch erhalten kann, dass man für alle Knoten $v$ nach dem kürzesten Pfad von 0 nach $v$ sucht und die Länge $D$ des längsten dieser Pfade bestimmt. Dann ist die Frobenius-Zahl $D-a_{1}$. 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.

Ravi Kannan entwickelte einen Algorithmus, der für jedes feste $n$ in polynomialer Zeit (bezogen auf $\log a_{1}$ bis $\log a_{n}$) die Frobenius-Zahl berechnet. Das allgemeine Problem, also wenn auch $n$ variabel ist, ist dagegen NP-schwer.

Beispiel

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 ${\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$ 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 $20+20+9=49$)
• 0 → 2 (Länge 20)
• 0 → 3 (Länge 9)
• 0 → 2 → 4 (Länge $20+20=40$)
• 0 → 2 → 5 (Länge $20+9=29$)

Der längste dieser Wege hat damit die Länge $D=49$, folglich gilt $g(6,9,20)=49-6=43$. Der Graph liefert auch zu jeder darstellbaren Zahl eine mögliche Darstellung. Will man etwa 47 Chicken McNuggets, so sucht man wegen $47\equiv 5\mod 6$ 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.

Weblinks

• Eric W. Weisstein: Coin Problem. In: MathWorld (englisch).