# Münzen/Mathematische Argumentation/Motivation/Textabschnitt

Wir betrachten die Euromünzen und Euroscheine (Bargeldmittel), die bekanntlich die Werte
    $1,2,5,10,20,50,100,200,500$
haben (um nicht immer von Münzen bzw. Scheinen sprechen zu müssen, nennen wir diese Zahlen schlicht Eurozahlen). Einen zu zahlenden vollen Betrag, beispielsweise $37$ Euro, kann man auf viele verschiedene Weisen (ohne Rückgeld) begleichen, etwa durch $37$ $1$-Euro Münzen oder durch
    $37=1\cdot 10+4\cdot 5+2\cdot 2+3\cdot 1\,$
oder durch
    $37=20+10+5+2\,.$
Wir fragen uns, ob es stets eine „optimale“ Art gibt, einen gegebenen Betrag zu begleichen, ob sie eindeutig ist und wie man sie finden kann. Ein naheliegender Ansatz ist es, diejenige Bezahlung als optimal anzusehen, bei der die wenigsten Münzen bzw. Scheine verwendet werden. Im Beispiel kommt die zuletzt genannte Möglichkeit mit vier Münzen/Scheinen aus. Gibt es eine bessere Möglichkeit? Wie kann man an eine solche Frage herangehen? Wenn jemand eine Darstellung mit nur zwei oder drei Münzen/Scheinen finden würde, wäre die Frage direkt negativ entschieden, denn dann gäbe es eine bessere Möglichkeit. Wenn man ein bisschen rumprobiert und keine bessere Möglichkeit findet, so sagt das relativ wenig, wenn man sich nicht sicher sein kann, dass man alle Möglichkeiten systematisch überprüft hat. Ein solches systematisches und nachvollziehbares Überprüfen ist eine mathematische Argumentation. Wenn die mathematische Argumentation eine präzise formulierte Aussage begründet, so spricht man von einem Beweis (für diese Aussage). Unsere Aussage ist also
„Die Zahl $37$ lässt sich nicht als eine Summe (wobei Wiederholungen erlaubt sind) von weniger als vier Zahlen aus den Eurozahlen $1,2,5,10,20,50,100,200,500$ darstellen“.
Wie kann man das systematisch begründen? Grundsätzlich könnte man alle Summen mit einer Eurozahl, alle Summen mit zwei Eurozahlen und alle Summen mit drei Eurozahlen ausrechnen und dann feststellen, dass nie $37$ rauskommt. Das ist durchführbar, aber sehr aufwändig. Zu einer guten mathematischen Argumentation gehört auch, dass sie geschickt und ökonomisch ist, dass sie abwegige Situationen schnell ausschließt und sich auf wesentliche Gesichtspunkte konzentriert. Im Beispiel heißt das, dass man Summen, in denen ein Schein mit einem Wert von mindestens $50$ vorkommt, gar nicht betrachten muss, da eine solche Summe immer größergleich $50$ und somit größer als der Zielbetrag $37$ sein wird. Hier fällt sofort eine typische Eigenschaft einer mathematischen Argumentation auf: Sie nimmt Bezug auf schon etablierte oder bekannte oder allgemein anerkannte Eigenschaften, hier nämlich die Eigenschaft, dass eine Summe von natürlichen Zahlen größergleich jedem Summanden der Summe ist. In einer mathematischen Argumentation geht man nicht immer „zurück auf Los“, sondern man verwendet Bekanntes, das seinerseits irgendwann durch eine mathematische Argumentation begründet worden ist.
Eine weitere Beobachtung, die das rechnerische Überprüfen von sehr vielen Summen erübrigt, geht folgendermaßen: Man betrachtet den $20$-Euro-Schein. Das ist der größte Schein, von dem man noch nicht weiß, ob und wie oft er verwendet wird. Wie oft kann/könnte er verwendet werden? Zunächst darf er höchstens einmal verwendet werden, da ja
    $2\cdot 20=40>37\,$
schon zu groß ist. Muss er in einer minimalen Darstellung verwendet werden? Hier begegnen wir einer typischen Denkfigur im Rahmen einer mathematischen Argumentation: Wir zeigen, dass in einer minimalen Darstellung der $37$ mit Eurozahlen die $20$ vorkommen muss, indem wir zeigen, dass eine Darstellung ohne den $20$-Schein nicht minimal sein kann. Man spricht von einem Beweis durch Widerspruch. Dabei formuliert man eine Annahme, die dann durch die mathematische Argumentation als unhaltbar erwiesen wird, also als widersprüchlich zu den gegebenen Voraussetzungen der Aussage. Wir machen also die Annahme:
Es ist möglich, die $37$ als eine Summe mit maximal drei Summanden aus den Zahlen $1,2,5,10$ (also ohne die $20$!) darzustellen.
Durch die Abschätzung, die ihrerseits auf Rechengesetze der natürlichen Zahlen Bezug nimmt,
    $a\cdot 1+b\cdot 2+c\cdot 5+d\cdot 10\leq (a+b+c+d)10\leq 3\cdot 10=30<37\,$
sieht man aber schnell, dass dies nicht möglich ist. Die Annahme ist also falsch und eine jede Darstellung der $37$ mit maximal drei Eurozahlen muss die $20$ verwenden, und zwar genau einmal.
An dieser Stelle tritt eine weitere wichtige Strategie bei einer mathematischen Argumentation auf, die Vereinfachung der Situation unter Verwendung des schon Gezeigten. Wir wissen bereits, dass $20$ genau einmal vorkommt. Wir ziehen daher $20$ ab und gelangen zur Fragestellung, ob es möglich ist, die $17$ als Summe von maximal zwei der Zahlen $1,2,5,10$ darzustellen. In einem gewissen Sinn sind wir jetzt wieder in der Ausgangssituation, wobei allerdings die Zahlen einfacher (geworden) sind. Mit der schon verwendeten Strategie kann man hier weiterargumentieren: Man zeigt, dass die $10$ genau einmal in einer solchen minimalen Darstellung vorkommen muss, zieht es wieder ab und gelangt zur Frage, ob man die $7$ als Summe von Eurozahlen mit nur einem Summanden darstellen kann, was offenbar nicht möglich ist.
Hier, wie häufig in der Mathematik, hängt also die Gültigkeit einer mathematischen Aussage mit der Gültigkeit einer anderen mathematischen Aussage von gleichem oder ähnlichem Typ zusammen. Von daher ist es sinnvoll, eine möglichst allgemeine mathematische Aussage zu formulieren und diese zu beweisen, wobei man im Beweis zeigt, dass man kompliziertere (größere Zahlen) auf einfachere Situationen (kleinere Zahlen) zurückführen kann. Ein wichtiges Beweisprinzip entlang dieses Schemas ist der Beweis durch Induktion.
Wir haben also gezeigt (bewiesen, durch eine mathematische Argumentation begründet), dass man mindestens vier Eurozahlen braucht, um die $37$ als Summe darzustellen: Mit weniger als vier ist es nicht möglich, und die eingangs beschriebene Zerlegung
    $37=20+10+5+2\,$
zeigt, dass es mit vier Eurozahlen möglich ist.
Die $37$ ist eine Zahl unter vielen, wir hätten gerne zu einer jeden natürlichen Zahl eine entsprechende Aussage. Zunächst gibt es zu jedem vollen Eurobetrag $w$ eine minimale Anzahl an Eurozahlen, mit der man den Betrag als Summe erhalten kann, aus den drei einfachen Gründen, dass (1) überhaupt jeder Betrag darstellbar ist (beispielsweise als hinreichend große Summe der $1$ mit sich selbst), dass (2) es zu jeder Anzahl an Summanden grundsätzlich die beiden Möglichkeiten gibt, dass der Betrag durch eine Summe aus Eurozahlen mit $k$ Summanden darstellbar ist oder nicht, und dass (3) das Minimum einer nichtleeren Menge aus natürlichen Zahlen existiert. Wenn wir den Betrag mit $w$ bezeichnen, so kann man die minimale Summandenanzahl als
    $m(w)={\min {\left(k\in \mathbb {N} ,w{\text{ lässt sich als eine Summe mit }}k{\text{ Summanden aus Eurozahlen darstellen}}\right)}}\,$
schreiben. Wir fragen uns:
* Ist die minimale Darstellung eines Betrages $w$ eindeutig?
* Wie kann man sie charakterisieren?
* Wie kann man sie finden?
Dabei suchen wir nicht nur nach einer Antwort, sondern diese Fragen sind stets so zu verstehen, wie man mathematisch begründen kann, dass die Antwort auch richtig ist. Solche mathematischen Fragen können im Allgemeinen sehr schwierig sein, und es ist von vornherein nicht klar, ob man eine Lösung finden wird. Wir listen einige Herangehensweisen auf.
* Probieren.
* Systematischer Probieren.
* Extremfälle betrachten.
* Hypothese formulieren.
* Voraussetzungen leicht abändern, um mögliche Gründe und Schwierigkeiten zu erkennen.
* Hypothese präziser formulieren.
* Hypothese unter stärkeren zusätzlichen Voraussetzungen beweisen.
* Die Perspektive ändern.
* Reduktionsmöglichkeiten erkennen.
* Hypothese beweisen.
Wir erläutern dies an der ersten Frage, ob es eine eindeutig bestimmte minimale Darstellung gibt.
* Nehmen wir die $37$. Es fällt uns keine weitere Darstellung mit vier Eurozahlen ein. Man kann die obige Argumentation, bei der wir gezeigt haben, dass es keine Darstellung mit drei Eurozahlen gibt, etwas abwandeln, und erhält so eine Begründung, dass die minimale Darstellung für die $37$ eindeutig ist. Welche Zahl probieren wir als nächstes? Die $146$?
* Es ist systematischer, erstmal die kleinsten Zahlen durchzugehen, die $1,2,3=1+2,4=2+2,5,6=5+1$, bei denen man recht schnell erkennen kann, dass die optimalen Darstellungen eindeutig sind.
* Extremfälle sind beispielsweise die einzelnen Eurozahlen selbst, diese sind offenbar durch sich selbst eindeutig minimal darstellbar. Wie sieht es mit der Summe von zwei Eurozahlen aus, kann es für sie eine weitere Darstellung als Summe von zwei Eurozahlen geben? Warum nicht?
* Nach diesen Beobachtungen bzw. Überlegungen formulieren wir die optimistische Hypothese, dass die minimale Darstellung eindeutig ist.
* Wie allgemein könnte eine solche Aussage stimmen? Betrachten wir die gleiche Fragestellung für eine Währung, für die die Bargeldmittel gleich sind. Das sieht auf den ersten Blick nicht so anders aus. Allerdings gibt es hier die beiden verschiedenen Darstellungsmöglichkeiten die beide minimal sind, da man die $6$ sicher nicht mit einer Münze darstellen kann. Die Hypothese kann also nur stimmen aufgrund spezifischer Eigenschaften der Eurozahlen, eine grobe Argumentation wird man somit wohl nicht erwarten und eine Argumentation, die nicht direkt auf die Eurozahlen Bezug nimmt, kann nicht funktionieren. Auch wenn man die Rückgabe von Geld erlaubt, geht die Eindeutigkeit verloren, beispielsweise ist bei beiden Darstellung werden zwei Scheine bewegt.
    $1,3,5,10,30,50,100,300,500$
    $6=5+1=3+3\,,$
    $15=10+5=20-5\,,$
* Wir meinen natürlich bei eindeutig „eindeutig bis auf die Reihenfolge“, natürlich ist Es könnte sich als sinnvoll erweisen, immer mit einer bestimmten Reihenfolge der Summanden zu arbeiten, beispielsweise in absteigender Größe.
    $37=20+10+5+2=2+20+5+10\,.$
* Wir beweisen die Aussage zuerst nur für alle Beträge $\leq 10$ oder $\leq 100$ oder nur für alle Beträge, die als Summe von drei Summanden darstellbar sind.
* Wir wollen etwas über Zerlegungen aussagen. Das kann man von links, also von $w$ aus betrachten, aber auch von der rechten Seite aus. Kann man einer Darstellung ohne Bezug auf den dargestellten Wert ansehen, ob sie minimal ist? Hier gibt es viele Gesetzmäßigkeiten, z.B. kann $a$ nicht $2$ sein, da man andernfalls die beiden $1-$Euromünzen sofort durch eine $2$-Euromünze ersetzen und so mit einer kleineren Anzahl von Eurozahlen auskommen würde.
    $w=a\cdot 1+b\cdot 2+c\cdot 5+d\cdot 10+...\,$
    $a\cdot 1+b\cdot 2+c\cdot 5+d\cdot 10+...$
* Hängt die eindeutige Zerlegung für große Zahlen irgendwie mit der eindeutigen Zerlegung für kleinere Zahlen zusammen? Eine zweite Darstellung für $w$ führt zu einer Gleichheit Hier kann man links und rechts, falls eine Eurozahl auf beiden Seiten positiv vorkommt, diese Eurozahl abziehen, und erhält so eine Gleichheit für einen kleineren Ausdruck.
    $a\cdot 1+b\cdot 2+c\cdot 5+d\cdot 10+...=a'\cdot 1+b'\cdot 2+c'\cdot 5+d'\cdot 10+...\,.$
* Siehe unten.
In einem mathematischen Buch (bzw. in der Vorlesung) werden mathematische Aussagen häufig direkt bewiesen, ohne dass die Vorüberlegungen erläutert werden, die zu dem Beweis geführt haben. Dies ist von der Ökonomie her begründet, man möchte einen Beweis haben, und nicht Überlegungen dokumentieren, die für sich allein genommen ziemlich aussagelos (wie das Durchrechnen von einigen Beispielen) sind und von denen ein Großteil auch in eine falsche Richtung geht. Beim Auffinden von Beweisen und beim Lösen von Aufgaben (zwischen diesen beiden Aspekten gibt es keinen grundsätzlichen Unterschied) ist der Weg dorthin sehr wichtig, und es sollte viel probiert, Strategien entwickelt und diskutiert werden, auch wenn sich das nicht in der Dokumentation der letztlich gefundenen überprüfbaren Argumentation niederschlägt.
Nach all diesen Vorüberlegungen können wir den folgenden Satz beweisen.

## Satz

Es gelten die folgenden Aussagen.

### Beweis

Wir zeigen zuerst, dass jede minimale Darstellung von $w$ die in (2) angegebenen Koeffizientenbedingungen erfüllt. Es sei also
    $w=a_{1}\cdot 1+a_{2}\cdot 2+a_{3}\cdot 5+a_{4}\cdot 10+a_{5}\cdot 20+a_{6}\cdot 50+a_{7}\cdot 100+a_{8}\cdot 200+a_{9}\cdot 500\,$
eine minimale Darstellung. Wenn der Koeffizient vor $1$ (also $a_{1}$) größer als $1$ wäre, also mindestens $2$, so könnte man zwei $1$-Euromünzen durch eine $2$-Euromünze ersetzen und hätte eine Darstellung mit weniger Summanden im Widerspruch zur Minimalität (ebenso für den Koeffizienten vor $10$ und vor $100$). Wenn der Koeffizient vor $5$ größer als $1$ wäre, also mindestens $2$, so könnte man zwei $5$-Euroscheine durch einen $10$-Euroschein ersetzen und hätte eine Darstellung mit weniger Summanden im Widerspruch zur Minimalität (ebenso für den Koeffizient vor $50$). Wenn der Koeffizient vor $2$ größer als $2$ wäre, also mindestens $3$, so könnte man drei $2$-Euromünzen durch eine $1$-Euromünze und einen $5$-Euroschein ersetzen und hätte eine Darstellung mit weniger Summanden im Widerspruch zur Minimalität (ebenso für den Koeffizienten vor $20$ und vor $200$). Wenn eine $2$-Euromünze doppelt und eine $1$-Euromünze einfach vorkommt, so kann man dies durch einen $5$-Euroschein ersetzen im Widerspruch zur Minimalität der Darstellung, ebenso bei einem doppelten Vorkommen von $20$ oder $200$.
Wir zeigen nun die Eindeutigkeit der minimalen Darstellung und nehmen an, dass zwei Zerlegungen
    ${\begin{aligned}w&=a_{1}\cdot 1+a_{2}\cdot 2+a_{3}\cdot 5+a_{4}\cdot 10+a_{5}\cdot 20+a_{6}\cdot 50+a_{7}\cdot 100+a_{8}\cdot 200+a_{9}\cdot 500\\&=b_{1}\cdot 1+b_{2}\cdot 2+b_{3}\cdot 5+b_{4}\cdot 10+b_{5}\cdot 20+b_{6}\cdot 50+b_{7}\cdot 100+b_{8}\cdot 200+b_{9}\cdot 500\end{aligned}}$
vorliegen. Da beide Darstellungen minimal sind, müssen nach der bisherigen Überlegung die Koeffizienten jeweils die Koeffizientenbedingungen erfüllen. Wir werden zeigen, dass es überhaupt nur eine Darstellung gibt, die die Koeffizientenbedingungen erfüllt. Wir müssen also zeigen, dass
    $a_{i}=b_{i}\,$
für alle $i=1,\ldots ,9$ gilt. Wenn für ein bestimmtes $i$ die Koeffizienten $a_{i}$ und $b_{i}$ beide $\geq 1$ sind, so kann man beidseitig die zugehörige Eurozahl (eventuell zweimal) abziehen und erhält dann eine kleinere Zahl $w'$, für die zwei Darstellungen vorliegen, die ebenfalls die Koeffizientenbedingungen erfüllen. Da man diese Überlegung für jedes $i$ durchführen kann, gelangt man zu einer Gleichheit, bei der jeweils mindestens einer der Koeffizienten $a_{i},b_{i}$ gleich $0$ ist. Es ist dann zu zeigen, dass auch der andere Koeffizient gleich $0$ ist. Dies zeigen wir absteigend, beginnend mit $a_{9}$ bzw. $b_{9}$. Da die Situation symmetrisch ist, können wir annehmen, dass $a_{9}=0$ ist. Aufgrund der Koeffizientenbedingungen ist (die Klammern sind suggestiv und sollen die verwendeten Abschätzungen verdeutlichen, die erste ist echt)
    ${\begin{aligned}(a_{1}\cdot 1+a_{2}\cdot 2+a_{3}\cdot 5)+(a_{4}\cdot 10+a_{5}\cdot 20+a_{6}\cdot 50)+(a_{7}\cdot 100+a_{8}\cdot 200)&<10+90+400\\&=500.\end{aligned}}$
Daher kann $b_{9}$ nicht größergleich $1$ sein und ist ebenfalls $0$. So zeigt man absteigend, dass alle Koeffizienten $0$ sind und dass die Darstellung also eindeutig ist.
Wir zeigen nun die andere Richtung aus Teil (2), dass eine Darstellung mit den gegebenen Koeffizientenbedingungen die eindeutige Darstellung sein muss. Mit der gleichen Argumentation wie eben, angewendet auf eine solche Darstellung und die minimale Darstellung, ergibt sich, dass die Darstellungen übereinstimmen.
Der dritte Teil ergibt sich daraus, dass die entstehende Darstellung die in (2) formulierten Koeffizientenbedingungen erfüllen muss.
$\Box$
Die Aufgabe zeigt, dass das Verfahren aus Fakt (3) nicht bei jeder Bargeldverteilung zur minimalen Darstellung führt.
* ↑ Eine Summe mit nur einem Summanden mag sich sonderbar anhören. In der Mathematik sind aber solche Grenzfälle wichtig und stets mitzubetrachten, da man bei einer Situationsvereinfachung häufig - wie hier - bei einer solchen Extremsituation ankommt.
* ↑ Das Induktionsprinzip werden wir in der siebten Vorlesung genau besprechen, und gelegentlich schon verwenden.
* ↑ Dies ist unmittelbar klar (?). Wir werden in Fakt diese Aussage aus dem Induktionsprinzip herleiten.
* ↑ Hier werden also die Voraussetzungen kurz abgeändert, um sie besser verstehen zu können.
* ↑ Das gilt auch für die abzugebenden Aufgaben. Geben Sie ein überzeugendes Endprodukt der Überlegungen ab, keine Dokumentation der Überlegungen.
* ↑ Dies ist ein sogenannter „gieriger Algorithmus“, da er sich bei jedem Einzelschritt daran orientiert, wie man möglichst viel von dem (verbleibenden) Geldbetrag abzahlen kann.
* ↑ Die Situation ist symmetrisch, da die beiden Darstellungen gleichberechtigt sind. In einer solchen Situation bedeutet es keine Einschränkung der Aussagekraft der Argumentation, wenn man eine Umbenennung vornimmt bzw. eine Eigenschaft, die eines der beteiligten Objekte hat, dem ersten zuweist. In einer solchen Situation finden sich häufig Formulierungen wie „wir können annehmen, dass ...“.