Wir stellen hier einige einfache, aber deswegen nicht weniger interessante mathematische Probleme samt Beweisen vor. Und wir wähle sie so aus, dass dabei Beweismethoden zur Anwendung gelangen, die in der Mathematik besonders wichtig und häufig sind. Wer sich in der Stube der Mathematik umschaut, wird diese Methoden in jeder Ecke antreffen¹ .

Problem 1

Wir fangen ganz einfach an und behaupten Folgendes: Addiert man zwei gerade Zahlen, so wird das Resultat sicherlich wieder eine gerade Zahl sein. Wie kann man diesen Sachverhalt beweisen?

Zunächst genügt es nicht, Beispiele zu betrachten. Klar, das soll man tun, denn jedes erfolgreiche Beispiel erhöht die Plausibilität der Behauptung. Aber Beispiele ergeben keinen allgemeinen Beweis, denn es könnte ja sein, dass man beim Ausprobieren von Beispielen aus einem dummen Zufall stets Zahlen erwischt, bei denen die Behauptung zutrifft, während es vielleicht andere Beispiele gäbe, bei denen sie nicht zutrifft, die man aber nicht ausprobiert hat. \begin{align*} 4+16 &= 20 \quad\text{(gerade)}\\ 78+114 &= 192 \quad\text{(gerade)}\\ 100+1000 &= 1100 \quad\text{(gerade)} \end{align*} Okay, hier stimmt es immer. Aber wer garantiert uns, dass nicht schon das nächste Beispiel vielleicht zwei gerade Zahlen liefert, deren Summe ungerade ist? Absolute Sicherheit gewinnen wir erst, wenn wir beweisen können, dass der behauptete Sachverhalt wirklich immer zutrifft, egal an welche Beispiele wir gerade denken. Wir müssen also mit beliebigen geraden Zahlen arbeiten. Wir wählen hier einen sogenannten direkten Beweis. Und formulieren die Behauptung ein wenig genauer: Wenn x und y zwei beliebige gerade natürliche Zahlen sind, dann ist auch x + y eine gerade natürliche Zahl. Bezeichnen wir den Wenn-Teil des Satzes (wonach x und y zwei gerade Zahlen sind) mit A und den Dann-Teil (wonach x + y eine gerade Zahl ist) mit B, so hat unser Satz die folgende Struktur: \begin{align*} A \implies B \end{align*} Aus A folgt B. A impliziert B. Wenn A gilt, so sicher auch B. Diese Form hat unsere Behauptung nun. Bei einem direkten Beweis setzen wir A voraus und versuchen, B daraus durch logisches Schliessen und auf direktem Wege aus A abzuleiten. Das sieht dann etwa so aus:

Beweis

Wie setzen voraus, dass x und y zwei gerade natürliche Zahlen sind (A).
Wegen der Definition von “gerade” ist dann jede dieser Zahlen ein Vielfaches von 2, also: \begin{align*} x = 2\cdot p \quad \text{und} \quad y = 2\cdot q \qquad \text{(für zwei natürliche Zahlen $p$ und $q$)} \end{align*} Addiert man beide Zahlen, so erhält man: \begin{align*} x+y = 2\cdot p + 2\cdot q = 2\cdot \left(p+q\right) \end{align*} Somit existiert eine natürliche Zahl r, nämlich r=p+q, sodass x+y=2\cdot r ist. Nach Definition von “gerade” heisst das, dass x+y gerade ist (B). Q.E.D.

Diese Art zu beweisen ist häufig und besonders naheliegend, weil sie meist der natürlichsten Herangehensweise entspricht. Wir haben am Ende des Beweises ein kleines Quadrat gesetzt, weil das in der Mathematik die häufigste Art ist, ein Beweis-Ende zu kennzeichnen.

Problem 2

Jemand hat im Inneren eines Kreises eine beliebige gerade Anzahl von Punkten (mindestens 2) völlig zufällig gezeichnet. Die Abbildung zeigt ein Beispiel mit zehn Punkten. Die Frage ist: Ist es stets möglich, eine Gerade so durch den Kreis zu legen, dass genau die Hälfte der Punkte auf der einen Seite der Geraden und die andere Hälfte der Punkte auf der anderen Seite der Geraden zu liegen kommen? Ist das immer möglich, ganz egal, wie die Punkte im Kreis verstreut sind und wie viele es sind (solange die Anzahl gerade ist)? Kann man ein Verfahren finden, mit dem man in jedem nur denkbaren Fall eine solche Trenngerade finden kann?

Bildbeschreibung: TO BE DONE

Ja, das geht, und wir können dafür einen einfachen direkten Beweis angeben:

Beweis

Es sei also ein Kreis gegeben, und im Inneren des Kreises seien 2n Punkte für eine natürliche Zahl n > 0 zufällig gewählt worden.

Zunächst bilden wir sämtliche Geraden, die sich durch irgend zwei dieser Punkte legen lassen. Dabei entstehen sehr viele, aber natürlich immer nur endlich viele Geraden.

Bildbeschreibung: TO BE DONE

Da es nur endlich viele Geraden sind, kann man sicherlich ausserhalb des Kreises einen Punkt P finden und wählen, der auf keiner dieser Geraden liegt. Durch diesen Punkt legen wir eine Gerade g, die gänzlich ausserhalb des Kreises verläuft.

Bildbeschreibung: TO BE DONE

Schliesslich drehen wir die Gerade g um P langsam über den Kreis wie einen Scheibenwischer über eine Autoscheibe. Dabei wird sie einen Punkt nach dem anderen “einfangen”, aber ganz sicher nie zwei Punkte auf einmal, denn sonst müsste der Punkt P ja auf einer der anfangs konstruierten Geraden liegen, was er nicht tut. Wenn sie genau n Punkte eingefangen hat, kann man die Gerade g “anhalten”. Dann besitzt sie die verlangte Eigenschaft. Und das ist offenbar immer möglich. Q.E.D.

Problem 3

An der Internationalen Mathematik-Olympiade des Jahres 1972 wurde unter anderem das folgende Problem gestellt: Wenn man eine Menge S von 10 natürlichen Zahlen zwischen 1 und 99 beliebig wählt, so kann man ganz sicher zwei disjunkte Teilmengen von S finden, deren Summenwerte gleich sind. Können Sie das beweisen?

Zuerst sollten wir es uns in diesem Problem “bequem machen”. Das soll heissen, wir sollten versuchen, ganz genau zu verstehen, worum es eigentlich geht, sodass uns die Aussage vertraut und vernünftig erscheint. Es geht also um eine Menge von 10 Zahlen zwischen 1 und 99. Die Menge hat den Namen S, was natürlich unwichtig ist. Die Zahlen sollen beliebig gewählt werden können; die Behauptung soll also offenbar für jede nur denkbare Auswahl von 10 Zahlen zwischen 1 und 99 standhalten. Es gibt sicher eine ungeheuer grosse (und zunächst unüberschaubare) Anzahl von Möglichkeiten, 10 Zahlen zwischen 1 und 99 zu wählen. Zweifellos ist diese Anzahl so gross, dass es unvernünftig wäre, alle Varianten aufzuzählen und auszuprobieren; wir würden wahrscheinlich bis an unser Lebensende nichts anderes mehr tun. Wir müssen uns also darüber im Klaren sein, dass hier eine Aussage über eine gigantische Anzahl von Auswahlen gemacht wird und dass wir es irgendwie schaffen müssen, die Behauptung für alle diese Auswahlen zu beweisen, ohne aber alle Auswahlen einzeln zu untersuchen. Wie soll das gehen?

Bevor wir weiter darüber nachdenken, sollten wir verstehen, was der Rest der Behauptung genau bedeutet. Wir denken uns dazu, dass irgendwelche 10 Zahlen zwischen 1 und 99 ausgewählt worden sind, vielleicht dadurch, dass wir mit verbundenen Augen zehnmal hintereinander eine der Zahlen von 1 bis 99 aus einer Tüte gezogen haben. Dabei ist vielleicht die folgende Auswahl entstanden: \begin{align*} S = \{87, 13, 2, 25, 89, 44, 29, 11, 70, 68\} \end{align*} Warum auch nicht!? Es könnte diese Auswahl entstanden sein oder irgendeine andere. Jede ist gleich gut, und jede muss die behauptete Eigenschaft haben. Welche genau? Es wird behauptet, dass wir ganz sicher zwei disjunkte Teilmengen von S mit dem gleichen Summenwert finden können. Zwei Teilmengen von S heissen “disjunkt”, wenn sie kein gemeinsames Element haben. Wenn die Behauptung zutrifft, und davon gehen wir natürlich aus, so müsste es uns nun gelingen, ein paar dieser Zahlen in einen ersten Behälter (die erste Teilmenge) und ein paar andere dieser Zahlen in einen zweiten Behälter (die zweite Teilmenge) abzufüllen, sodass bei Summenbildung in beiden Behältern derselbe Wert entsteht.

Das klingt abenteuerlich und zunächst vielleicht unglaubwürdig. Probieren wir es also gleich mit obiger Auswahl. Tatsächlich werden wir nach einigem Suchen fündig: \begin{align*} \text{Erster Behälter:}\quad &T_1= \{13, 25, 89\}\\ \text{Zweiter Behälter:}\quad &T_1= \{2, 44, 11, 70\} \end{align*} Summiert man die Zahlen in jeder dieser beiden Teilmengen auf, so erhält man 127. In beiden Behältern. Es ist überhaupt nicht klar, ob es vielleicht noch andere Möglichkeiten gibt, zwei Behälter so mit Zahlen aus S zu füllen, dass derselbe Summenwert entsteht, aber das ist gar nicht die Frage. Denn in der Behauptung steht lediglich, dass man ganz sicher zwei disjunkte Teilmengen finden kann, und wir haben zwei gefunden. Allerdings nur für diese eine Auswahl S von 10 Zahlen. Das Entscheidende ist – und nun verstehen wir die Aussage in ihrer ganzen Wucht –, dass es für jede beliebige Auswahl von 10 Zahlen zwischen 1 und 99 möglich sein soll, zwei disjunkte Teilmengen mit dem gleichen Summenwert zu finden. Das müssen wir beweisen. Aber ohne konkrete Auswahlen solcher Zahlen aufzulisten. Wie kann man das schaffen?

An dieser Stelle soll das sogenannte Taubenschlagprinzip (oder Schubfachprinzip) erläutert werden; es handelt sich dabei um eine ebenso einfache wie schlagkräftige mathematische Beweismethode. Das Prinzip besagt Folgendes: Wenn es n Taubenschläge gibt und wenn nun m > n Tauben angeflogen kommen, die alle in den Taubenschlägen landen, dann muss es mindestens einen Taubenschlag geben, in welchem mindestens zwei Tauben landen. Das ist völlig klar. Selbst wenn sich jede einzelne Taube bemühen würde, in einem noch freien Schlag zu landen, so wäre nach Ankunft von n Tauben jeder Schlag mit einer Taube besetzt. Da aber mehr als n Tauben angeflogen kommen, muss spätestens die Taube Nummer n + 1 in einem Schlag landen, in welchem sich schon eine andere Taube befindet.

Mit diesem Prinzip lässt sich zum Beispiel beweisen, dass in einer Gruppe von 13 Personen mindestens zwei im gleichen Monat Geburtstag haben. Die 12 Monate sind hier die Taubenschläge. Wenn nun 13 Personen (Tauben) “angeflogen” kommen, müssen mindestens zwei im gleichen Monat “landen”. Ebenso lässt sich damit beweisen, dass in New York (wie in jeder anderen Grossstadt auch) ganz sicher zwei Personen leben, die exakt dieselbe Anzahl Haare auf dem Kopf haben. Dazu muss man wissen, dass ein Mensch höchstens 200‘000 Haare auf dem Kopf trägt. Man könnte also 200‘001 Taubenschläge mit den Anzahlen 0, 1, 2, …, 200‘000 anschreiben und nun alle Bewohner von New York nacheinander diesen Kategorien zuordnen. Mit grosser Wahrscheinlichkeit werden schon bald zwei Personen in denselben Taubenschlag gesteckt. Aber selbst wenn jede der ersten 200‘001 Personen in einem anderen Schlag landen sollte, dann muss spätestens die 200‘002. Person in einem Schlag landen, in welchem sich schon jemand befindet; und diese beiden Personen haben dann dieselbe Anzahl Haare auf dem Kopf.

Mit diesem Prinzip lässt sich auch die oben gestellte Behauptung beweisen, und dies auf überaus elegante Weise. Wir müssen nur darüber nachdenken, was die Tauben und was die Taubenschläge sind. Wir müssen ja von einer beliebigen Auswahl S von 10 Zahlen zwischen 1 und 99 ausgehen. Eine solche liege nun also vor. Irgendeine! Nun dreht sich alles um zwei “Dinge”: Teilmengen und Summenwerte. Wir wollen einsehen, dass mindestens zwei Teilmengen mit demselben Summenwert existieren. Die Summenwerte sollten also die Taubenschläge und die Teilmengen sollten die Tauben sein, und wir wollen, dass ganz sicher mindestens zwei Teilmengen beim gleichen Summenwert “landen” müssen. Und zwar unabhängig davon, welche 10 Zahlen ausgewählt worden sind. Jetzt nimmt der Beweis endlich Konturen an. Wir müssen uns allerdings noch Gedanken dazu machen, wie viele mögliche Summenwerte und wie viele mögliche Teilmengen von S es gibt. Und es sollte, damit das Taubenschlagprinzip funktioniert, unbedingt mehr Teilmengen als Summenwerte geben.

Nun gut, die möglichen Summenwerte sind überschaubar: Da alle 10 Zahlen zwischen 1 und 99 liegen, ist jeder Summenwert jeder nur denkbaren Teilmenge ganz sicher kleiner als das Zehnfache von 99, also kleiner als 990. Egal, welche 10 Zahlen vorliegen, und egal, welche beiden Teilmengen wir bilden, wir können ganz sicher sein, dass ihre Summenwerte kleiner als 990 sein werden. Jetzt müssen wir uns noch die Teilmengen vorknöpfen. Wie viele gibt es denn insgesamt? Mehr als 990? Das wäre schön, nicht wahr? Wir spüren, dass es sehr viele sind, aber wie viele sind es genau? Gehen wir dazu noch einmal zu unserem Beispiel zurück: \begin{align*} S = \{87, 13, 2, 25, 89, 44, 29, 11, 70, 68\} \end{align*} Jemand verrät uns, er habe eine Teilmenge T_1 von Zahlen aus S gebildet, verrät uns aber nicht, um welche Zahlen es sich handelt. Hingegen ist er bereit, Ja-Nein-Fragen zu beantworten. Und das genügt uns völlig. Wir könnten nämlich der Reihe nach fragen: “Ist 87 in deiner Teilmenge?”, “Ist 13 in deiner Teilmenge?”, “Ist 2 in deiner Teilmenge?” und so weiter. Da unser Kollege bei jeder Frage zwei Antwortmöglichkeiten hat, gibt es insgesamt 2^{10} mögliche Antwortmuster. Das Antwortmuster zur Teilmenge T_1 = \{13, 25, 89\} wäre zum Beispiel: nein, ja, nein, ja, ja, nein, nein, nein, nein, nein. Es gibt also 2^{10} mögliche Teilmengen von S, weil es genauso viele Antwortmuster gibt. Und ja, das ist eine ganz tolle Nachricht, denn 2^{10} = 1024. Das ist mehr als 990. Nun können wir den Beweis der eingangs aufgestellten Behauptung ganz einfach formulieren:

Beweis

Sei S eine beliebige Auswahl von 10 Zahlen zwischen 1 und 99. Es gibt 2^{10} = 1024 mögliche Teilmengen von S. Da der Summenwert jeder beliebigen Teilmenge kleiner als 990 ist, müssen nach dem Taubenschlagprinzip ganz sicher mindestens zwei Teilmengen T_1 und T_2 von S existieren, deren Summenwerte gleich sind. Diese beiden Teilmengen sind vielleicht nicht disjunkt, aber wir können aus beiden Teilmengen die gemeinsamen Elemente entfernen. Danach sind die Summenwerte noch immer gleich, und die Teilmengen sind disjunkt.Q.E.D.

Problem 4

Hier untersuchen wir einmal ein Spiel, nämlich eine Variante des beliebten Brettspiels Dame. Gespielt wird es von einem einzigen Spieler. Dieser ordnet zwölf Damesteine wie abgebildet auf den drei untersten Reihen eines Schachbretts an. Diese Steine sind die Liebhaber, die alle danach dürsten, die Dame zu erobern, die am oberen Brettrand auf einen Eroberer wartet. Ein Zug besteht nun darin, mit einem Stein einen anderen Stein zu überhüpfen und den gezogenen Stein auf das freie Feld davor zu platzieren; der Überhüpfte wird sogleich vom Brett geräumt, er hat als möglicher Liebhaber der Dame ausgedient.

Bildbeschreibung: Das Bild zeigt ein quadratisches 8×8-Schachbrett mit abwechselnd hellen und hellgrauen Feldern und einem schwarzen Rahmen. Es gibt keine Spaltenbeschriftungen.

Links neben den acht Reihen stehen von unten nach oben die Zahlen 1, 1, 2, 3, 5, 8, 13, 21.

Auf den unteren drei Reihen liegen schwarze runde Spielsteine. In der untersten Reihe liegen Steine auf den Feldern 1, 3, 5 und 7 von links. In der zweiten Reihe von unten liegen Steine auf den Feldern 2, 4, 6 und 8 von links. In der dritten Reihe von unten liegen wieder Steine auf den Feldern 1, 3, 5 und 7 von links.

Ein schwarzer gebogener Pfeil beginnt beim rechten Stein in der zweiten Reihe von unten und zeigt nach links oben auf ein leeres Feld in der Reihe mit der Beschriftung 3, ungefähr im Bereich der sechsten Spalte von links.

Der Pfeil in der Abbildung zeigt einen möglichen ersten Zug. Ein Stein darf aber immer nur vorwärts, nach links oben oder nach rechts oben, gezogen werden. Und das Ziel besteht darin, mindestens einen Stein in die oberste Reihe zu befördern; damit wäre die Dame dann erobert. Kann dieses Ziel erreicht werden?

Wir behaupten Folgendes: Es ist prinzipiell unmöglich, mit einem Stein die oberste Reihe zu erreichen und damit die Dame zu erobern. Bei jedem nur denkbaren korrekten Spiel kann man höchstens mit genau einem Stein die zweitoberste Reihe erreichen. Das gilt es zu beweisen. Das Beweisprinzip, das wir hier verwenden wollen, ist das sogenannte Invarianzprinzip. Beim Invarianzprinzip suchte man Invarianten, also Grössen, die sich bei gewissen Operationen (zum Beispiel Spielzügen) nicht ändern. Wenn nun klar ist, dass man von einem bestimmten Startzustand in einen bestimmten Endzustand mittels solcher Operationen gelangen soll, dass die fragliche Grösse im Endzustand aber einen anderen Wert haben müsste als im Startzustand, dann ist gezeigt, dass der Endzustand nicht erreichbar ist. Das wird wohl erst dann ganz klar werden, wenn wir den Einsatz dieses Prinzips am Beispiel unseres Damespiels demonstriert haben.

Dazu nehmen wir an, die Steine wären Liebhaber, die alle der Dame den Hof machen möchten, und je höher ein Liebhaber hinaufsteigt, desto höher wird sein Wert, desto grösser werden seine Chancen. Zu Beginn hat jeder Liebhaber der ersten und zweiten Reihe den Wert 1 und jeder Liebhaber der dritten Reihe den Wert 2, und die Wertstufen am linken Rand des Schachbretts sind so gebildet worden, dass die Werte von zwei aufeinanderfolgenden Reihen sich zum Wert der nächsten Reihe addieren \left(1+1=2,\text{ } 1+2=3,\text{ } 2+3=5 \text{ usw.}\right) Nur ein Liebhaber mit Wert 21 könnte die Dame erobern.

Der entscheidende Punkt ist nun der: Bei einem Zug gewinnt ein Liebhaber an Wert, und zwar addiert sich zu seinem Wert genau der Wert des übersprungenen Liebhabers, der ja ausscheidet. Die Summe der Werte aller Liebhaber auf dem Brett bleibt bei einem Zug also unverändert, invariant. Zu Beginn des Spiels beträgt die Summe der Werte aller Liebhaber 16. Das ist die Invariante. Und da sich diese Summe bei jedem Zug nicht ändert, kann auch am Schluss kein Liebhaber einen Wert über 16 erreichen. Damit ist die achte Reihe also unzugänglich, und die Dame kann nicht erobert werden, wie sehr sich die Liebhaber auch ins Zeug legen. Hingegen ist es möglich, die zweitoberste Reihe zu erreichen, da der Zahlwert eines Liebhabers auf dieser Reihe 13 beträgt und 13 weniger als die Invariante 16 ist. Das heisst, dass nebst einem Stein in der zweitobersten Reihe dann noch zum Beispiel drei Steine in den beiden untersten Reihen weit abgeschlagen und frustriert herumstehen würden. Mit diesen Überlegungen wird der Beweis der aufgestellten Behauptung ganz kurz:

Beweis

Wir wählen die Zahlwerte der acht Reihen wie in der Abbildung.
In der Anfangsposition beträgt die Summe der Zahlwerte aller Spielfiguren 16.
Da nun bei jedem möglichen Zug die Summe der Zahlwerte aller auf dem Brett sich befindlichen Steine invariant bleibt, muss auch in jeder möglichen Endposition die Summe der Zahlwerte aller Steine 16 sein.
Folglich ist es nicht möglich, mit einem Stein die achte Reihe zu erreichen, da allein schon sein Zahlwert 21 sein und damit über 16 liegen müsste.Q.E.D.

Problem 5

Hier geht es um ein Problem, das auf den ersten Blick sehr überraschend klingt. Es stammt aus einer Aufnahmeprüfung der mathematischen Abteilung der Unabhängigen Universität Moskau aus dem Jahr 1991, und wir wollen es hier genauer untersuchen, um ein weiteres sehr häufiges mathematisches Beweisprinzip zu erläutern: den “Beweis mit Kontraposition”.

Das Problem lautet so: Ein gleichseitiges Dreieck der Seitenlänge a wird überdeckt von fünf gleichseitigen Dreiecken der Seitenlänge b. Beweise, dass es dann möglich ist, das Dreieck der Seitenlänge a mit nur 4 Dreiecken der Seitenlänge b zu überdecken.

Wie bitte? Beim ersten Durchlesen bleibt dies hängen: Falls eine gewisse Überdeckung mit 5 Dreiecken gelingt, dann gelingt sie sogar mit nur 4. Immer. Und wir kennen nicht einmal die Seitenlängen, sie sind uns ja nur durch Buchstaben gegeben. Das ist wirklich erstaunlich. Kann das richtig sein?

Wie üblich machen wir es uns in der Behauptung zuerst bequem, indem wir ihre genaue Bedeutung ausloten. Ein gleichseitiges Dreieck ist also gegeben, und es hat irgendeine Seitenlänge a. Wir stellen uns einfach vor, dass dieses Dreieck auf einem Bogen Papier aufgezeichnet ist und vor uns auf dem Tisch liegt. Nun wird weiter behauptet, dass unser Dreieck von 5 gleichseitigen Dreiecken mit Seitenlänge b überdeckt wird. Wir könnten uns also vorstellen, dass wir aus Pappkarton 5 kongruente Dreiecke ausschneiden und diese dann so auf unser erstes Dreieck legen, dass dieses vollständig überdeckt (und damit unsichtbar) wird. Es ist offenbar sinnvoll, uns b kleiner als a vorzustellen, denn sonst würde ja ein einziges Kartondreieck ausreichen.

Was heisst genau “überdeckt”? Ist das im Text irgendwie spezifiziert? Nein, ist es nicht. Es ist also durchaus erlaubt, dass die 5 kleinen Dreiecke irgendwie kreuz und quer auf dem grossen Dreieck liegen und sich sogar überlappen. Damit wird unsere Vorstellung der Ausgangslage immer klarer: 5 kleine kongruente Dreiecke mit Seitenlänge b liegen irgendwie auf unserer Zeichnung und machen das grosse Dreieck mit Seitenlänge a damit unsichtbar. Das Ganze könnte sich etwa so darbieten:

Bildbeschreibung: Die Abbildung zeigt mehrere übereinanderliegende Dreiecke ohne Koordinatensystem, Achsen oder Beschriftungen.

Im Hintergrund liegt ein großes, gleichseitig wirkendes Dreieck mit orangefarbener Kontur und hell orangefarbener, transparenter Füllung. Die Spitze zeigt nach oben, die Grundseite verläuft waagerecht unten.

Darüber liegen mehrere kleinere bis mittelgroße Dreiecke mit grauer Kontur und hellgrauer, transparenter Füllung. Diese grauen Dreiecke sind verschieden verschoben und teilweise gedreht. Sie überdecken große Teile des orangefarbenen Dreiecks, ragen aber an mehreren Stellen auch über dessen Rand hinaus. Durch die Transparenz sind die Überlappungen und die orangefarbene Fläche darunter noch sichtbar.

Es gibt keine sichtbaren Zahlen, Punkte, Winkelmarkierungen oder Formeln.

Jetzt kommt der verrückte Teil. Es wird ja behauptet, dass, falls eine Situation wie die abgebildete vorliegt, es dann ganz sicher möglich ist, das grosse Dreieck mit nur 4 kleinen Kartondrei-ecken zu überdecken. Immer. Wenn es mit 5 geht, dann reichen 4 bereits aus. Und dies völlig unabhängig davon, wie die Überdeckung genau aussieht. Sollen wir das glauben? Nun ja, dies war eine Aufgabe aus einem Eignungstest einer Universität, es ist kaum anzunehmen (wenn auch nicht unmöglich), dass die Autoren eine falsche Behauptung aufgestellt haben. Wir nehmen also staunend zur Kenntnis: Immer, wenn es mit 5 geht, dann geht es auch mit nur 4. Und wir versuchen, dafür einen Beweis zu finden. Haben wir einen Beweis in der Hand, so müssten alle Zweifel verfliegen. Erinnern wir uns an die Worte von Pierre de Fermat: “La qualité essentielle d’une démonstration est de forcer à croire.” Der Beweis sollte uns also vollkommen überzeugen.

Welche Struktur hat unsere Behauptung? Wie schon in Problem 1 nennen wir den Wenn-Teil der Behauptung A und den Dann-Teil B:

A: Ein gleichseitiges Dreieck mit Seitenlänge a kann mit 5 gleichseitigen Dreiecken mit Seitenlänge b überdeckt werden.
B: Es kann bereits mit 4 gleichseitigen Dreiecken mit Seitenlänge b überdeckt werden.

Die Behauptung hat also die folgende Struktur: \begin{align} A \implies B \end{align}\tag{1}

Es ist der Moment gekommen, um zu erläutern, was es mit der “Kontraposition” auf sich hat; denn dies wird hier der Schlüssel zum Erfolg sein. Unter der Kontraposition versteht man den Umkehrschluss einer Implikation: Wenn B nicht gilt, dann gilt auch A nicht. Mit dem Zeichen für die logische Negation einer Aussage, \neg, sieht das so aus: \begin{align} \neg B \implies \neg A \end{align}\tag{2} Wir können uns leicht an Beispielen klarmachen, dass (2) äquivalent (gleichbedeutend) zu (1) ist. Wenn die Aussage \begin{equation*} \text{"Wenn es (hier und jetzt) regnet, dann wird diese Strasse nass."} \end{equation*} gesichert ist, dann ist ebenfalls die Kontraposition gesichert: \begin{equation*} \text{"Wenn diese Strasse nicht nass wird, dann regnet es (hier und jetzt) nicht."} \end{equation*} Das ist klar, denn würde es hier und jetzt regnen, dann müsste ja die Strasse nass werden. Angenommen, eine Chemikerin stellt fest: \begin{equation} \begin{aligned} \text{"Wenn bei einer chemischen Reaktion Knallgas} \\ \text{gezündet wird, dann entsteht Wasser."} \end{aligned} \end{equation}\tag{3} Sie hätte ebenso gut sagen können: \begin{equation} \begin{aligned} \text{"Wenn bei einer chemischen Reaktion kein Wasser entsteht,} \\ \text{dann kann nicht Knallgas gezündet worden sein"} \end{aligned} \end{equation}\tag{4} Denn wäre Knallgas gezündet worden, so hätte ja Wasser entstehen müssen. Beide Aussagen (3) und (4) sind gleichwertig. In der Tat: Wenn ich ganz sicher weiss, dass (3) gilt, dann weiss ich auch, dass (4) gilt, und umgekehrt. Wir können also jederzeit (3) ersetzen durch (4) oder umgekehrt und vermitteln exakt dieselbe Information. Mit aussagenlogischen Wahrheitstabellen könnte man die Äquivalenz von A \implies B und \neg B \implies \neg A übrigens noch strenger nachweisen.

Gehen wir zurück zu unserem Problem mit den Dreiecken. Wir wollen beweisen, dass A \implies B gilt: Wenn es mit 5 geht, dann geht es auch mit 4. Der entscheidende Punkt ist, dass wir Mühe haben, das auf direktem Wege zu beweisen. Es müsste uns ja irgendwie gelingen, für jede nur denkbare Überdeckung des grossen Dreiecks mit 5 kleinen Dreiecken – und solche gibt es unendlich viele – zu zeigen, dass bereits 4 kleine Dreiecke ausreichen. Es könnte aber sein, dass es uns viel einfacher gelingen wird, die Kontraposition dieser Implikation zu beweisen. Wie lautet diese denn? \neg B \implies \neg A, also: Wenn es mit 4 nicht geht, so auch mit 5 nicht. Tatsächlich ist es oftmals einfacher, die Kontraposition zu beweisen als die ursprüngliche Implikation. Und so ist es auch hier. Wir beweisen also die ursprüngliche Behauptung dadurch, dass wir ihre Kontraposition beweisen: Falls ein gleichseitiges Dreieck mit Seitenlänge a nicht mit 4 gleichseitigen Dreiecken mit Seitenlänge b überdeckt werden kann, so kann es auch nicht mit 5 gleichseitigen Dreiecken mit Seitenlänge b überdeckt werden. Hier kommt der Beweis. Und er sollte für absolute Klarheit sorgen. Er sollte uns deutlich machen, woraus diese seltsame Aussage ihre Gültigkeit bezieht:

Beweis

Wir setzen also voraus, dass ein gleichseitiges Dreieck mit Seitenlänge a nicht mit 4 gleichseitigen Dreiecken mit Seitenlänge b überdeckt werden kann (\neg B).
Daraus folgt zwingend, dass b<\frac{a}{2} Denn wäre b=\frac{a}{2} (oder gar grösser), dann wäre eine Überdeckung ja möglich, und zwar so:

Bildbeschreibung: TO BE DONE

Wenn nun also b < \frac{a}{2} ist, dann ist eine Überdeckung in der Tat auch mit 5 solchen Dreiecken unmöglich. Um das einzusehen, markieren wir spezielle Punkte P_1 - P_6 im grossen Dreieck, nämlich die Eckpunkte und die Seitenmittelpunkte. Je zwei dieser Punkte haben einen Abstand von mindestens \frac{a}{2}. Ein Dreieck mit Seitenlänge b < \frac{a}{2} kann also höchstens einen dieser Punkte überdecken, niemals aber gleichzeitig deren zwei.

Bildbeschreibung: TO BE DONE

Und daraus folgt, dass auch fünf Dreiecke mit Seitenlänge b<\frac{a}{2} zur Überdeckung nicht ausreichen (\neg A).
Damit haben wir gezeigt: Wenn es mit 4 nicht geht, so auch mit 5 nicht. Und damit ist auch die Originalaussage bewiesen: Wenn es mit 5 geht, so geht es auch mit 4. Toll, nicht? Q.E.D.

Problem 6

An einer Party treffen 50 Personen zusammen. Jeder notiert sich auf einen Zettel, wie viele der anwesenden Personen zu seinem Freundeskreis zählen, wobei wir annehmen, dass immer dann, wenn eine Person X eine Person Y als Freund betrachtet, umgekehrt auch Y X als Freund betrachtet. Beweisen Sie, dass es ganz sicher mindestens zwei Personen geben wird, die dieselbe Zahl notieren.

Diesen Beweis könnten wir ganz einfach mit dem Taubenschlagprinzip erbringen. Wir können die einfache Aufgabe aber auch zum Anlass nehmen, um ein weiteres überaus häufiges und kraftvolles Beweisprinzip zu diskutieren: den “Widerspruchsbeweis” oder die “Reductio ad absurdum”. Bei diesem Vorgehen nimmt man das Gegenteil dessen an, was man eigentlich einsehen will, und zeigt dann durch präzises Schlussfolgern, dass diese Gegenannahme unmöglich zutreffen kann, weil sie zu einem Widerspruch zu irgendeiner bereits anerkannten Aussage führen würde. Man beweist also, dass die Negation dessen, was man als wahr vermutet, nicht wahr sein kann. Und wenn das Gegenteil einer Aussage nicht zutreffen kann, so muss natürlich die Aussage selber zutreffen. Prägnanter formuliert:

Man will A nachweisen.
Man nimmt das Gegenteil an: \neg A
Und zeigt, dass diese Annahme zu einem Widerspruch führen würde, sodass also \neg\neg A gilt.
Da man aus \neg\neg A auf A schliessen kann, muss dann A selber gelten.

Diese Vorgehensweise ist in der Mathematik überaus häufig. Zum Beispiel ist der Beweis der berühmten Fermat-Vermutung von Andrew Wiles und Richard Taylor im Kern ein Widerspruchsbeweis. Die Äquivalenz von \neg\neg A und A könnte man auch hier mit einer aussagenlogischen Wahrheitstabelle nachweisen. Nicht verschweigen sollte man allerdings, dass eine bestimmte mathematikphilosophische Richtung, nämlich der Intuitionismus, diese Äquivalenz ablehnt. Es würde hier aber zu weit führen, detaillierter darauf einzugehen.

Wie können wir nun die aufgestellte Behauptung mit einem Widerspruchsbeweis erhärten?

Beweis

Wir stellen die Gegenannahme auf: Es gibt keine zwei Personen, die dieselbe Anzahl von Freunden notieren (\neg A).
Da es 50 Personen sind, müssen am Ende auf allen 50 Zetteln verschiedene Zahlen stehen.
Da die kleinste mögliche Zahl 0 und die grösste mögliche Zahl 49 ist, müssen auf den 50 Zetteln folglich genau die Zahlen 0–49 (in irgendeiner Reihenfolge) stehen.
Daraus folgt, dass es eine Person X mit 0 Freunden und eine zweite Person Y mit 49 Freunden geben muss.
Das würde aber bedeuten, dass Y sämtliche anderen Gäste, inklusive X, als Freunde hat, während X jedoch niemanden zum Freund hat, auch Y nicht. Das ist ein Widerspruch zu der Voraussetzung, dass eine Person eine andere zum Freund hat, genau dann wenn das auch umgekehrt zutrifft.
Die Gegenannahme führt also zu einem Widerspruch und muss somit falsch sein (\neg\neg A). Ergo muss A selber wahr sein: Es gibt mindestens zwei Personen, die dieselbe Zahl notieren. Q.E.D.

Problem 7

Der grosse ungarische Mathematiker Paul Erdős pflegte von dem “Buch” zu erzählen, in welches Gott die perfekten Beweise für mathematische Sätze notiert. Martin Aigner und Günter M. Ziegler ist es zu verdanken, dass eine Annäherung an dieses geheimnisvolle Buch tatsächlich entstanden ist, unter anderem basierend auf Vorschlägen, die Erdős selbst noch 1966, in seinem letzten Lebensjahr, gemacht hat. In diesem Buch der Beweise steht ein berühmter Beweis an erster Stelle, ein Beweis von Euklid für die Tatsache, dass es unendlich viele Primzahlen gibt, genauer: dass es mehr Primzahlen gibt als jede vorgelegte endliche Menge von Primzahlen. Und es ist ein Widerspruchsbeweis, vielleicht der älteste der Menschheitsgeschichte.

Zunächst: Eine Primzahl ist eine natürliche Zahl mit genau zwei Teilern. Wir reden also über Zahlen, die durch 1 und durch sich selber restlos teilbar sind, sonst aber durch keine andere Zahl. Die ersten zehn Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Euklid hat gezeigt, dass, egal, welches aktuell die grösste bekannte Primzahl ist, sich stets eine noch grössere Primzahl finden lässt. Es gibt keine letzte, grösste Primzahl. Es gibt in der Tat unendlich viele Primzahlen. Und hier ist der Beweis:

Beweis

Wir formulieren die Gegenannahme: Angenommen, es gibt nur endlich viele Primzahlen, und p ist die letzte, grösste existierende Primzahl (\neg A). Dann ist also \{2, 3, 5, 7, 11, ..., p\} die Menge aller Primzahlen; es gibt keine anderen. Wir bilden die natürliche Zahl \begin{align*} n \coloneqq \left(2\cdot 3\cdot 5\cdot 7\cdot 11\cdot ... \cdot p \right)+1 \end{align*} also das um 1 erhöhte Produkt sämtlicher existierender Primzahlen.
Da n > p und p ja die grösste Primzahl ist, kann n selber keine Primzahl sein. Folglich muss n mindestens einen Primteiler besitzen, also durch mindestens eine Primzahl restlos teilbar sein. (Jede natürliche Zahl, die nicht prim ist, kann in ihre Primfaktoren zerlegt werden, und jeder dieser Primfaktoren ist dann ein Primteiler der Zahl.)
Daraus folgt, dass n durch mindestens eine der Primzahlen 2, 3, 5, 7, 11, ..., p restlos geteilt wird.
Aber das ist ein Widerspruch, denn bei Division durch jede dieser Zahlen lässt n den Rest 1.
Also ist die Gegenannahme falsch (\neg\neg A). Ergo muss A selber wahr sein: Es gibt mehr Primzahlen als jede vorgelegte endliche Menge von Primzahlen.Q.E.D.

Problem 8

Jemand zeichnet ein quadratisches Feld auf einen Bogen kariertes Papier und daneben einen sogenannten Tromino-Stein. Darunter wollen wir ein Puzzlestück verstehen, das die Form eines Winkels hat und genau drei Kästchen überdeckt, so wie in der Abbildung unten. Jemand – derselbe Jemand wie vorher – behauptet nun: Wenn die Seitenlänge des Quadrats eine Zweierpotenz grösser als 1, also eine der Zahlen2, 4, 8, 16, 32 und so weiter, ist, dann kann man das Quadrat so mit Trominos parkettieren, dass nur ein einziges Kästchen übrig bleibt, und dieses freie Kästchen kann an jeder Stelle innerhalb des Quadrats sein. Können wir das einsehen?

Bildbeschreibung: TO BE DONE

Beissen wir an? Sind wir interessiert? Mathematikerinnen und Mathematiker müssen an so etwas Interesse finden. Denn die Fragestellung enthält viele würzige, schmackhafte Zutaten: Sie ist zunächst unklar, aber wir ahnen, dass sie geklärt werden kann und dann herausfordernd ist. Sie ist keine langweilige Rechenaufgabe; vielmehr fordert sie uns heraus, einen Weg zu finden, von dem wir jetzt gerade nicht einmal den Anfang sehen. Sie stellt und auf die Probe, sie definiert eine “Battle”: die Frage gegen unseren Intellekt. Die Frage gewinnt, wenn wir keine Antwort finden. Aber wer will schon gerne verlieren? Klar, wir können weiterleben, ohne einen Beweis gefunden zu haben, sehr oft muss man das auch. Aber der Lockruf der Aufgabe ist doch unüberhörbar, und es wäre ein kleiner Triumph, würden wir gewinnen. Und wenn wir gewinnen, dann besteht unser Lohn darin, dass wir grenzenlose Klarheit erlangen, etwas Stolz empfinden dürfen und – vielleicht – eine schöne Idee geniessen können.

Gut, wie lautet also die Frage? Da ist ein Quadrat, und seine Seitenlänge ist eine Zweierpotenz, genauer: eine Zahl der Art 2^n für eine natürliche Zahl n ungleich null. Warum ungleich null? Klar, weil 2^0 gleich 1 wäre, und wir können nicht erwarten, ein Quadrat mit Seitenlänge 1, das also aus einem einzigen Kästchen besteht, mit Trominos zu füllen. Ist die Seitenlänge 2, so geht es aber schon. Was genau geht? Nun, es wird behauptet, dass man das Quadrat mit Trominos so bedecken kann, dass nur ein einziges Kästchen übrig bleibt, und dass dieses Kästchen an jeder beliebigen Stelle sein kann. Für ein Quadrat mit Seitenlänge 2 geht das offenbar, wie wir uns sofort klarmachen können, wobei wir das frei gebliebene Kästchen mit einem Kreuz markieren:

Bildbeschreibung: TO BE DONE

Okay, es stimmt also für die Seitenlänge 2. In der Tat kann jedes der vier Kästchen frei bleiben, und der Rest wird von Trominos (eigentlich ja nur einem) lückenlos überdeckt. Gemäss Behauptung müsste es auch für die Seitenlänge 2^2 = 4 zutreffen. Warum eigentlich nicht für die Seitenlänge 3? Klar, weil das Quadrat dann aus neun Kästchen bestehen würde, und wenn man ein solches Quadrat überhaupt mit Trominos parkettieren könnte – was aber nicht geht – dann wäre kein Kästchen übrig. Es ist also offenbar bedeutsam, dass die Seitenlänge des Quadrats eine Zweierpotenz ist. Nun gut, betrachten wir also ein Quadrat mit Seitenlänge 4. Die Abbildung zeigt in zwei Fällen, dass eine Überdeckung mit Trominos in der Tat möglich ist. Wir haben das freie Feld einmal im Inneren und einmal am Rand gewählt, und auch in einer Eckposition wäre der Rest des Quadrats problemlos parkettierbar.

Bildbeschreibung: TO BE DONE

Jetzt kommt die entscheidende Stelle. Die Behauptung ist mittlerweile sehr klar, und wir haben uns davon überzeugt, dass sie für die beiden Zweierpotenzen 2 und 4 zutrifft. Aber wir können unmöglich, unter gar keinen Umständen, so fortfahren. Die Quadrate wachsen nun rapide, es gibt bezüglich des freien Feldes immer mehr Möglichkeiten, und selbst wenn wir die nächsten zehn Zweierpotenzen mit brute force untersuchen würden, wäre damit noch lange nicht gezeigt, dass es für jede Zweierpotenz geht. Bei unendlich vielen Fällen sind deren zehn nicht einmal wenig; sie wären einfach nur nichts.

Wir sollten also anfangen zu denken. Was ist eigentlich das Besondere an einer Zweierpotenz? Wenn man sie verdoppelt, ist es wieder eine Zweierpotenz. Ebenso, wenn man sie halbiert. Was würde eine Verdoppelung respektive Halbierung der Zweierpotenz bewirken? Im ersten Fall entstünde ein Quadrat mit vierfacher Fläche, im zweiten Fall eines mit einem Viertel der Fläche. Nehmen wir zum Beispiel ein Quadrat mit Seitenlänge 16, dann lässt sich dieses aufteilen in vier Quadrate mit Seitenlänge 8. Hilft uns das? Angenommen, wir hätten schon gezeigt, dass die Behauptung für Quadrate mit Seitenlänge 8 zutrifft, könnten wir dann allein damit die Gültigkeit der Behauptung auf Quadrate mit Seitenlänge 16 ausweiten? Man könnte an Vererbung denken: Die Quadrate mit Seitenlänge 8 sind die Quadrate der 3. Generation, weil 8 = 2^3. Die Quadrate mit Seitenlänge 16 sind die Quadrate der 4. Generation, weil 16 = 2^4. Können wir irgendwie zeigen, dass sich die Gültigkeit der Behauptung für Quadrate einer bestimmten Generation immer auf die nächste Generation vererbt, weil ein Quadrat der neuen Generation aus vier Quadraten der vorherigen Generation aufgebaut ist? Sei n irgendeine natürliche Zahl ungleich 0. Können wir irgendwie zeigen, dass sich die Gültigkeit der Behauptung für Quadrate der Generation n immer auf die Generation n+1 vererbt, weil ein Quadrat der Generation n+1 aus vier Quadraten der Generation n aufgebaut ist? Könnte das eine heisse Spur sein?

Notieren wir das einmal ganz präzise:

Angenommen, wir wissen schon, dass die Behauptung auf Quadrate der Generation n zutrifft. Das würde bedeuten:

Dass sich diese Eigenschaft auf die nächste Generation vererbt – falls dies denn zutrifft – würde bedeuten:

Zur Abkürzung haben wir hier die Notation A(n) eingeführt. Sie steht für “Aussage für die natürliche Zahl n”. Entsprechend steht A(n+1) für “Aussage für die nächsthöhere natürliche Zahl n+1”. Worum es uns also im Kern geht, ist dies: Unter der Voraussetzung, dass wir es irgendwie geschafft haben, A(n) zu beweisen, also zu beweisen, dass die Behauptung für alle Quadrate mit Seitenlänge 2^n zutrifft, können wir dann einsehen, dass auch A(n+1) gilt, dass die Behauptung also auch für die nächsthöhere Generation n+1 zutrifft? Noch kürzer: Können wir beweisen, dass aus der Gültigkeit von A(n) die Gültigkeit von A(n+1) zwingend folgt? Dass also die folgende Implikation gültig ist: \begin{align*} A(n) \implies A(n+1) \end{align*}

Die Konsequenz wäre schwindelerregend. Es käme dann nämlich eine ungeheure Kettenreaktion in Gang. Die Gültigkeit von A(1) haben wir ja schon eingesehen: Dass die Behauptung für Quadrate der ersten Generation, also Quadrate mit Seitenlänge 2^1, zutrifft, haben wir durch Überprüfen der wenigen möglichen Fälle eingesehen. Wenn wir nun auch noch die obige Implikation einsehen könnten, dann würde sich dank ihrer die Gültigkeit der Behauptung von Generation 1 auf Generation 2 vererben, dann sofort von Generation 2 auf Generation 3, dann sofort von Generation 3 auf Generation 4 und so weiter. Anders gesagt: Die Gültigkeit der Behauptung würde sich augenblicklich dank Vererbung durch alle natürlichen Zahlen hocharbeiten. Wirklich durch alle. Die Behauptung wäre dann also für alle unendlich vielen Generationen und damit für alle Quadrate mit einer Zweierpotenz als Seitenlänge bewiesen. Wir müssen also “nur” noch einsehen, dass aus der Gültigkeit von A(n) die Gültigkeit von A(n+1) zwingend folgt, und zwar für irgendeine natürliche Zahl n ungleich null.

Dazu betrachten wir ein Quadrat der Generation n+1. Seine Seitenlänge misst also 2^{n+1}. Es lässt sich unterteilen in vier Unterquadrate der Generation n, deren Seitenlänge 2^n misst. Wir markieren zudem ein beliebiges Kästchen im grossen Quadrat, das am Ende frei bleiben soll. Klar ist sofort, dass dieses Kästchen zu genau einem der vier Unterquadrate gehören muss. Und wir sollten versuchen einzusehen, dass obige Implikation gilt, dass also unter der Voraussetzung, dass die vier Unterquadrate gemäss der Behauptung mit Trominos parkettiert werden können, dass dann auch das grosse Quadrat parkettiert werden kann.

Bildbeschreibung: TO BE DONE

Wenn die vier Unterquadrate gemäss Behauptung parkettiert werden können, dann können wir sicherlich dasjenige Unterquadrat, in dem sich das markierte Kästchen befindet, um dieses Kästchen herum lückenlos parkettieren. Schön, das ist ein Teilerfolg. Aber wie können wir nun noch die restlichen drei Unterquadrate lückenlos parkettieren und zwar ohne, dass irgendwelche Kästchen frei bleiben? Das scheint ein Problem zu sein. Wir könnten die restlichen Unterquadrate gemäss Voraussetzung der Implikation zwar mit Trominos überdecken, aber nur so, dass in jedem Unterquadrat ein Kästchen frei bleibt. Nun sollte aber nirgends mehr ein Kästchen frei bleiben. Ist das ein herber Rückschlag?

Glücklicherweise nicht. Wir müssen uns nur Folgendes klarmachen: Nach Voraussetzung können wir die drei restlichen Unterquadrate immer je mit Trominos überdecken, ganz egal, welche drei Kästchen ausgewählt sind, sodass nur ein einziges Kästchen frei bleibt. Wir könnten also auch drei ganz spezielle Kästchen auswählen. Nämlich solche, die zusammen ein Tromino formen. Paukenschlag! Das ist die rettende Idee.

Bildbeschreibung: TO BE DONE

Wir wählen also in den drei restlichen Unterquadraten je ein Eckfeld wie in der Abbildung. Dann geschieht Folgendes: Nach Voraussetzung (die Gültigkeit von A(n)) können wir nun jedes der vier Unterquadrate so mit Trominos überdecken, dass in jedem das eine markierte Kästchen frei bleibt. Ein weiteres Tromino legen wir dann in die Mitte und überdecken damit gerade die drei Eckfelder. Insgesamt haben wir dann eine Überdeckung des grossen Quadrats mit Trominos gewonnen, bei der genau das ursprünglich markierte beliebig gewählte Kästchen frei bleibt (A(n+1)).

Die Vererbung ist also gelungen. Wir konnten zeigen, dass sich die Gültigkeit der Behauptung von Generation n auf die nächste Generation n+1 vererbt. Zusammen mit der verifizierten Gültigkeit von A(1) entfaltet damit die Kettenreaktion ihre Wirkung. Die Behauptung ist also bewiesen für alle unendlich vielen Generationen von Quadraten mit Zweierpotenzen als Seitenlängen.

Zusammengefasst: Wir haben die beiden folgenden Leistungen erbracht: \begin{gather*} A(1) \text{ verifiziert} \\ \text{und}\\ A(n) \implies A(n+1) \text{ bewiesen.} \end{gather*} Q.E.D.

Unzählige mathematische Behauptungen können nach diesem Schema bewiesen werden. Wer das tut, benutzt eine Methode, die unter dem Namen “vollständige Induktion” bekannt geworden ist. Sie ist beeindruckend und kraftvoll. Und sie bezieht ihre Legitimation aus dem 5. Peano-Axiom.