Kurs:Grundkurs Mathematik (Osnabrück 2022-2023)/Teil I/Vorlesung 2/latex

\setcounter{section}{2}

\epigraph { Die Schülerinnen und Schüler\auflistungsechs{verwenden eingeführte mathematische Fachbegriffe sachgerecht. }{beschreiben mathematische Sachverhalte mit eigenen Worten und finden dazu Fragestellungen. }{stellen Vermutungen über mathematische Sachverhalte an, begründen und überprüfen sie. }{entdecken und beschreiben mathematische Zusammenhänge. }{beschreiben und begründen eigene Lösungswege und reflektieren darüber. }{überprüfen mathematische Aussagen, kennzeichnen sie als richtig oder falsch und begründen dies.} } { Die erwarteten Kompetenzen am Ende des Schuljahrganges 4 im Kompetenzbereich Kommunizieren/Argumentieren aus dem niedersächsischen Kerncurriculum für die Grundschule (2006) }

\zwischenueberschrift{Mathematisches Argumentieren}

In einer Argumentation versucht man, eine Behauptung mittels allgemein anerkannter Prinzipien zu begründen, als wahr \zusatzklammer {oder gültig} {} {} zu erweisen. Grundsätzlich kann man mit sich selbst argumentieren, typischerweise gibt es ein Publikum, das man von der Behauptung überzeugen möchte. Argumentationen gibt es in den unterschiedlichsten Kontexten, in der Wissenschaft, in der Politik, in Beziehungen. Dabei gibt es kontextspezifische Prinzipien und Argumentationsmuster, im politischen Kontext beruft man sich gerne auf weitgehend anerkannte Grundsätze wie Menschenrechte, Grundgesetz, den Willen des Volkes, um daraus unter Berücksichtigung von Daten und Fakten eine politische Entscheidung herzuleiten. Die Erfahrung lehrt, dass dort die Argumente nicht so gut sind, um alle überzeugen zu können, und dass dort auch die Interessen von spezifischen Gruppen vertreten werden.

Auch in der mathematischen Argumentation versucht man, die Wahrheit von Behauptungen \zusatzklammer {oder die Korrektheit eines Rechenweges oder die Angemessenheit einer Modellierung} {} {} zu begründen. Die eingesetzten Mittel, die Argumentationsstrenge hängen auch da von der Zielgruppe, ihrem Vorwissen und ihrer Motivation, der Beziehung \zusatzklammer {Bindung, Vertrauen} {} {} zwischen der Person, die die Behauptung vertritt, und den Personen, die überzeugt werden sollen \zusatzklammer {beispielsweise Lehrer und Schüler} {} {,} ab.

Die mathematische Argumentation im wissenschaftlichen Kontext verfügt in mehrfacher Hinsicht über gewisse Argumentationsstandards. Eine wissenschaftliche Argumentation zeichnet sich durch \zusatzklammer {insbesondere im mathema\-tisch-naturwissenschaftlichen Kontext} {} {} folgende Punkte aus. \auflistungsechs{Die starke Präsenz von Fachbegriffen, die definiert werden müssen und gemäß ihrer Definition eingesetzt werden. }{Die Existenz weniger benennbarer Grundprinzipien\zusatzfussnote {Über die selbst wiederum reflektiert wird und wo die Grenze zwischen Wissenschaft und Philosophie verläuft} {.} {.} }{Der Einsatz von Logik zum Erschließen neuer Erkenntnisse. }{Die freie Verwendung von in der Wissenschaft bereits etabliertem Wissen. }{Die freie Zugänglichkeit und Überprüfbarkeit der Ergebnisse\zusatzfussnote {Dies ist ein großer Unterschied zur Esoterik, wo das \anfuehrung{Wissen}{} nur unter ganz speziellen Bedingungen \zusatzklammer {Verschwiegenheit, Würdigkeit, ...} {} {} von Eingeweihten weitergegeben wird} {.} {.} }{Der Anspruch, dass die \zusatzklammer {Gültigkeit der} {} {} Erkenntnisse unabhängig von subjektiven Wünschen und Empfindungen\zusatzfussnote {Das heißt keineswegs, dass die Erkenntnisse und ihre Entdeckungen nicht von Gefühlen begleitet würden. Im Gegenteil, Wissenschaft macht denen, die sie betreiben, ziemlich viel Spaß} {.} {} sind, dass sie zeitlos und kulturunabhängig sind\zusatzfussnote {Die Generierung von Wissen ist sehr stark zeit- und kulturabhängig} {.} {.} } In der mathematischen Argumentation im wissenschaftlichen Kontext treten diese Punkte besonders deutlich hervor\zusatzfussnote {Dafür fehlt der Mathematik ein entscheidender Punkt der Naturwissenschaften, die Beobachtung, die Empirie, das Experiment. Deshalb wird die Mathematik oft nicht zu den Naturwissenschaften gerechnet. Aber auch die Zuordnung zu den Geisteswissenschaften ist schwierig, so spricht man von \stichwort {Strukturwissenschaft} {}} {.} {,} was sich insbesondere schon darin niederschlägt, dass es einen eigenen Begriff für das mathematische Argumentieren gibt: \stichwort {Beweis} {.} Eine bewiesene mathematische Behauptung nennt man einen \stichwort {Satz} {} \zusatzklammer {oder Theorem oder Lemma oder Korollar} {} {.} \auflistungsechs{Die mathematischen Begriffe werden alle exakt und nur unter Verwendung von anderen mathematischen Begriffen definiert. Die Definitionen sind so angelegt, dass jedes sinnvolle mathematische Objekt entweder unter den Begriff fällt oder nicht, und zwar unabhängig davon, ob man das immer entscheiden kann\zusatzfussnote {Insbesondere sind beispielhafte Definitionen vom Typ etwas wie ... nicht zulässig} {.} {.} }{Die Mathematik wird heute \zusatzklammer {seit ca. 130 Jahren} {} {} auf Mengen aufgebaut. Sie ist axiomatisch-logisch organisiert, aber realweltlich-anschaulich motiviert. }{Die Logik ist das Handwerkszeug der Mathematik. Es gibt \zusatzklammer {im Prinzip} {} {} eine vollständige Liste von erlaubten Schlussweisen der Aussagenlogik und der Prädikatenlogik\zusatzfussnote {Dies ist Gegenstand der mathematischen Logik} {.} {.} }{Bewiesene mathematische Aussagen, also Sätze, werden weiterverwendet\zusatzfussnote {Sie sind auch nicht patentierbar} {.} {.} Für eine systematische Darstellung eines Teilgebietes der Mathematik \zusatzklammer {wie einer Vorlesung oder einem Buch} {} {} bedeutet dies, dass man die grundlegenden Sachen zuerst darstellt und darauf zunehmend komplexere Sachen aufbaut. Wenn ein zuvor bewiesener Satz dann irgendwo eingesetzt wird, wird über diesen Satz nicht nachgedacht, sondern nur, ob in der jetzigen Situation alle Voraussetzungen erfüllt sind, damit man den Satz anwenden kann. }{Mathematik wird in Zeitschriften und Büchern veröffentlicht, in Vorlesungen gelehrt, ist im Internet und in Bibliotheken zugänglich\zusatzfussnote {Einschränkung: Dies gilt nicht unbedingt für sicherheitsrelevante kryptologische Forschung, die zum Teil an regierungsnahen Forschungsinstituten durchgeführt wird} {.} {.} }{Die Mathematik wird heute in einer erdumspannenden Gemeinschaft entwickelt\zusatzfussnote {Wobei das Hauptgewicht nach wie vor auf den Industrieländern liegt. Die anderen Länder holen aber schnell auf. Die wichtigste mathematische Auszeichnung, die Fields-Medaille, ging 2014 an eine Iranerin, einen Brasilianer, einen Kanadier indischer Herkunft und einen Österreicher} {.} {.} }

\zwischenueberschrift{Geldscheine und Münzen}

Wir möchten an einem alltäglichen Beispiel typische Argumentationsmuster der Mathematik vorstellen. Grundlegende Eigenschaften der natürlichen Zahlen setzen wir hierfür voraus.

\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Euro coins and banknotes.jpg} }
\end{center}
\bildtext {} }

\bildlizenz { Euro coins and banknotes.jpg } {} {Avij} {Commons} {gemeinfrei} {}

Wir betrachten die Euromünzen und Euroscheine \zusatzklammer {Bargeldmittel} {} {,} die bekanntlich die Werte
\mathdisp {1,2,5,10,20,50,100,200, 500} { }
haben \zusatzklammer {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 \zusatzklammer {ohne Rückgeld} {} {} begleichen, etwa durch $37$ $1$-Euro Münzen oder durch
\mavergleichskettedisp
{\vergleichskette
{37 }
{ =} { 1 \cdot 10 + 4 \cdot 5 + 2 \cdot 2 +3 \cdot 1 }
{ } { }
{ } { }
{ } { }
} {}{}{} oder durch
\mavergleichskettedisp
{\vergleichskette
{37 }
{ =} {20 +10+5+2 }
{ } { }
{ } { }
{ } { }
} {}{}{.} Wir fragen uns, ob es stets eine \anfuehrung{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 \stichwort {mathematische Argumentation} {.} Wenn die mathematische Argumentation eine präzise formulierte Aussage begründet, so spricht man von einem \stichwort {Beweis} {} \zusatzklammer {für diese Aussage} {} {.} Unsere Aussage ist also

\anfuehrung{Die Zahl $37$ lässt sich nicht als eine Summe \zusatzklammer {wobei Wiederholungen erlaubt sind} {} {} von weniger als vier Zahlen aus den Eurozahlen
\mathl{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 \anfuehrung{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
\mavergleichskettedisp
{\vergleichskette
{ 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 \stichwort {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
\mathl{1,2,5,10}{} \zusatzklammer {also ohne die $20$} {!} {} darzustellen.

Durch die Abschätzung, die ihrerseits auf Rechengesetze der natürlichen Zahlen Bezug nimmt,
\mavergleichskettedisp
{\vergleichskette
{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
\mathl{1,2,5,10}{} darzustellen. In einem gewissen Sinn sind wir jetzt wieder in der Ausgangssituation, wobei allerdings die Zahlen einfacher \zusatzklammer {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\zusatzfussnote {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 \zusatzgs {wie hier} {} bei einer solchen Extremsituation ankommt} {.} {} 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 \zusatzklammer {größere Zahlen} {} {} auf einfachere Situationen \zusatzklammer {kleinere Zahlen} {} {} zurückführen kann. Ein wichtiges Beweisprinzip entlang dieses Schemas ist der \stichwort {Beweis durch Induktion} {\zusatzfussnote {Das Induktionsprinzip werden wir in der siebten Vorlesung genau besprechen, und gelegentlich schon verwenden} {.} {.}}

Wir haben also gezeigt \zusatzklammer {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
\mavergleichskettedisp
{\vergleichskette
{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 \zusatzklammer {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\zusatzfussnote {Dies ist unmittelbar klar (?). Wir werden in Lemma 10.11 diese Aussage aus dem Induktionsprinzip herleiten} {.} {.} Wenn wir den Betrag mit $w$ bezeichnen, so kann man die minimale Summandenanzahl als
\mavergleichskettedisp
{\vergleichskette
{ m(w) }
{ =} { {\min { \left( k \in \N , w \text{ lässt sich als eine Summe mit } k \text{ Summanden aus Eurozahlen darstellen} \right) } } }
{ } { }
{ } { }
{ } { }
} {}{}{} schreiben. Wir fragen uns: \aufzaehlungdrei{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. \aufzaehlungzweireihe {\itemfuenf {Probieren. }{Systematischer Probieren. }{Extremfälle betrachten. }{Hypothese formulieren. }{Voraussetzungen leicht abändern, um mögliche Gründe und Schwierigkeiten zu erkennen. } } {\itemfuenf {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. \aufzaehlungzweireihe {\itemfuenf {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\zusatzfussnote {Hier werden also die Voraussetzungen kurz abgeändert, um sie besser verstehen zu können} {.} {,} für die die Bargeldmittel gleich
\mathdisp {1,3,5,10,30,50,100,300,500} { }
sind. Das sieht auf den ersten Blick nicht so anders aus. Allerdings gibt es hier die beiden verschiedenen Darstellungsmöglichkeiten
\mavergleichskettedisp
{\vergleichskette
{6 }
{ =} {5+1 }
{ =} {3+3 }
{ } { }
{ } { }
} {}{}{,} 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
\mavergleichskettedisp
{\vergleichskette
{15 }
{ =} {10+5 }
{ =} {20-5 }
{ } { }
{ } { }
} {}{}{,} bei beiden Darstellung werden zwei Scheine bewegt. } } {\itemfuenf {Wir meinen natürlich bei eindeutig \anfuehrung{eindeutig bis auf die Reihenfolge}{,} natürlich ist
\mavergleichskettedisp
{\vergleichskette
{37 }
{ =} {20+10+5+2 }
{ =} {2+20+5+10 }
{ } { }
{ } { }
} {}{}{.} Es könnte sich als sinnvoll erweisen, immer mit einer bestimmten Reihenfolge der Summanden zu arbeiten, beispielsweise in absteigender Größe. }{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
\mavergleichskettedisp
{\vergleichskette
{ w }
{ =} { a \cdot 1 + b \cdot 2 + c \cdot 5 + d \cdot 10 + ... }
{ } { }
{ } { }
{ } { }
} {}{}{} aussagen. Das kann man von links, also von $w$ aus betrachten, aber auch von der rechten Seite aus. Kann man einer Darstellung
\mathdisp {a \cdot 1 + b \cdot 2 + c \cdot 5 + d \cdot 10 + ...} { }
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. }{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
\mavergleichskettedisp
{\vergleichskette
{ a \cdot 1 + b \cdot 2 + c \cdot 5 + d \cdot 10 + ... }
{ =} { a' \cdot 1 + b' \cdot 2 + c' \cdot 5 + d' \cdot 10 + ... }
{ } { }
{ } { }
{ } { }
} {}{}{.} 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. }{Siehe unten. } } In einem mathematischen Buch \zusatzklammer {bzw. in der Vorlesung} {} {} werden mathematische Aussagen häufig direkt bewiesen, ohne dass die Vorüberlegungen erläu\-tert 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 \zusatzklammer {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 \zusatzklammer {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\zusatzfussnote {Das gilt auch für die abzugebenden Aufgaben. Geben Sie ein überzeugendes Endprodukt der Überlegungen ab, keine Dokumentation der Überlegungen} {.} {.}

Nach all diesen Vorüberlegungen können wir den folgenden Satz beweisen.

\inputfaktbeweis
{Eurozahlen/Eindeutige Darstellung/Charakterisierung/Fakt}
{Satz}
{}
{

\faktsituation {}
\faktfolgerung {Es gelten die folgenden Aussagen. \aufzaehlungdrei{Jede natürliche Zahl $w$ besitzt eine eindeutige Summendarstellung
\mavergleichskettedisp
{\vergleichskette
{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 }
{ } { }
{ } { }
{ } { }
} {}{}{} \zusatzklammer {mit \mathlk{a_1 , \ldots , a_9 \in \N}{}} {} {} mit der Eigenschaft, dass die Gesamtanzahl der Summanden \zusatzklammer {also \mathlk{a_1 +a_2 + \cdots + a_9}{}} {} {} unter allen Darstellungen minimal ist. }{Eine solche Darstellung ist genau dann minimal, wenn die folgenden Koeffizientenbedingungen erfüllt sind.

a) Die Koeffizienten $a_i$, die sich auf $1,5,10,50,100$ beziehen, sind $\leq 1$.

b) Die Koeffizienten $a_i$, die sich auf $2,20,200$ beziehen, sind $\leq 2$.

c) Falls der Koeffizient, der sich auf $2$ \zusatzklammer {bzw. $20$ bzw. $200$} {} {} bezieht, gleich $2$ ist, so ist der vorhergehende Koeffizient \zusatzklammer {der sich also auf $1$ bzw. $10$ bzw. $100$ bezieht} {} {} gleich $0$. }{Die eindeutige Darstellung findet man, indem man sukzessive absteigend
\mathl{a_9 , \ldots , a_1}{} bestimmt, wobei man folgendermaßen\zusatzfussnote {Dies ist ein sogenannter \anfuehrung{gieriger Algorithmus}{,} da er sich bei jedem Einzelschritt daran orientiert, wie man möglichst viel von dem \zusatzklammer {verbleibenden} {} {} Geldbetrag abzahlen kann} {.} {} vorgeht
\mathdisp {a_9 \text{ ist die maximale natürliche Zahl mit } a_9 \cdot 500 \leq w} { , }
definiere
\mavergleichskettedisp
{\vergleichskette
{w_8 }
{ \defeq} {w- a_9 \cdot 500 }
{ } { }
{ } { }
{ } { }
} {}{}{.}
\mathdisp {a_8 \text{ ist die maximale natürliche Zahl mit } a_8 \cdot 200 \leq w_8} { , }
definiere
\mavergleichskettedisp
{\vergleichskette
{w_7 }
{ \defeq} { w_8- a_8 \cdot 200 }
{ } { }
{ } { }
{ } { }
} {}{}{,} etc. }}
\faktzusatz {}
\faktzusatz {}

}
{

Wir zeigen zuerst, dass jede minimale Darstellung von $w$ die in (2) angegebenen Koeffizientenbedingungen erfüllt. Es sei also
\mavergleichskettedisp
{\vergleichskette
{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$ \zusatzklammer {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 \zusatzklammer {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 \zusatzklammer {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 \zusatzklammer {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
\mavergleichskettealign
{\vergleichskettealign
{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 }
{ } { }
{ } { }
} {} {}{} 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
\mavergleichskettedisp
{\vergleichskette
{a_i }
{ =} {b_i }
{ } { }
{ } { }
{ } { }
} {}{}{} für alle
\mavergleichskette
{\vergleichskette
{ i }
{ = }{ 1 , \ldots , 9 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gilt. Wenn für ein bestimmtes $i$ die Koeffizienten \mathkor {} {a_i} {und} {b_i} {} beide
\mathl{\geq 1}{} sind, so kann man beidseitig die zugehörige Eurozahl \zusatzklammer {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\zusatzfussnote {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 \anfuehrung{wir können annehmen, dass ...}{.}} {} {} ist, können wir annehmen, dass
\mavergleichskette
{\vergleichskette
{a_9 }
{ = }{ 0 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ist. Aufgrund der Koeffizientenbedingungen ist \zusatzklammer {die Klammern sind suggestiv und sollen die verwendeten Abschätzungen verdeutlichen, die erste ist echt} {} {}
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{ (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 }
{ } { }
{ } { }
} {} {}{.} 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.

}

Die Aufgabe 2.25 zeigt, dass das Verfahren aus Satz 2.1  (3) nicht bei jeder Bargeldverteilung zur minimalen Darstellung führt.