Mathematisches Problemlösen und Beweisen

Mit diesem Buch möchte ich Sie zu einer Entdeckungsreise in die Mathematik einladen. Sie werden die Mathematik von einer ganz neuen Seite kennenlernen: nicht als Sammlung von Rechentechniken und Formeln, sondern als eine Welt, die Sie selbst erkunden können, in der Sie eigene Ideen entwickeln und wunderbare Schätze heben werden. Keine Sorge: Sie sind für Ihre Reise gut gerüstet. Unterwegs erweitern Sie Ihre Ausrüstung, lernen neue Werkzeuge kennen, die Ihnen beim Bewältigen schwieriger Passagen helfen. Dabei werde ich Ihnen als Reisebegleiter zur Seite stehen. Sie können selbst entscheiden, ob Sie alleine vorgehen, einige Hinweise annehmen oder sich vollständig durch das Terrain führen lassen.

Zum Auftakt unserer Entdeckungsreise in die Mathematik untersuchen wir drei Probleme: ein einfaches Problem zum Aufwärmen und zwei Probleme, deren Lösung sich uns erst nach einigem Suchen erschließt. Dabei werden wir besonders darauf achten, wie wir beim Problemlösen intuitiv vorgehen. Indem wir uns unsere Strategien bewusst machen und sie benennen, können wir sie bei schwierigeren Aufgaben gezielt einsetzen. Am Ende des Kapitels stellen wir sie in einem Werkzeugkasten zusammen. Das wird der Grundstock unserer Ausrüstung für die ganze Reise sein.

Was hat die russische Holzfigur Matrjoschka mit dem Lösen mathematischer Probleme gemeinsam? Öffnet man sie, so findet man darin eine kleinere Figur, die genauso aussieht. Diese kann man wieder öffnen und findet eine noch kleinere, und so weiter. Genauso kann man manche mathematische Probleme angehen: Löse das Problem, indem du es auf ein kleineres, gleichartiges Problem zurückführst. Das ist die Technik der Rekursion. Sie haben sie bereits in Problem 1.3 kennengelernt. Wir werden diese Idee nun systematisch weiterverfolgen. Rekursionen sind ein fundamentales Werkzeug der Mathematik, das vor allem für Abzählprobleme nützlich ist. In diesem Kapitel lösen Sie weitere Probleme mit dieser Methode und lernen ein Verfahren kennen, mit denen man bestimmte Arten von Rekursionen, zum Beispiel die Fibonacci-Rekursion, systematisch auflösen kann.

Die vollständige Induktion ist eines der grundlegenden Beweisverfahren für Aussagen der Form ”Für alle natürlichen Zahlen gilt . . .“. Sie basiert auf derselben Grundidee wie die Technik der Rekursion: Führe das Problem auf ein gleichartiges Problem kleinerer Größe zurück. Die vollständige Induktion ist die Umsetzung dieser Idee bei Beweisproblemen, die Technik der Rekursion bei Bestimmungsproblemen. In diesem Kapitel wird dieses sehr intuitive Beweisverfahren eingeführt und an zwei Beispielen illustriert. Weitere Beispiele finden Sie in den folgenden Kapiteln. Nebenbei lernen Sie ein weiteres wichtiges Element des Problemlösens wie auch jeden wissenschaftlichen Arbeitens kennen und schätzen: das Einführen geeigneter Begriffe.

Die Graphen, die Sie in diesem Kapitel kennenlernen, sind auf den ersten Blick so einfache Gebilde, dass sie die meisten Menschen gar nicht mit Mathematik in Verbindung bringen würden. Sie haben weder mit Formeln oder Gleichungen zu tun, noch gehören sie ins Reich der Geometrie. Und doch steckt in ihnen viel spannende Mathematik. Ein wenig davon werden Sie hier entdecken. Dabei werden Sie die vollständige Induktion in einem ungewohnten Zusammenhang einsetzen und weitere wichtige mathematische Techniken, z. B. doppeltes Abzählen und gerade/ungerade-Argumente, kennenlernen. Sie machen auch erste Bekanntschaft mit Unmöglichkeitsbeweisen, einer faszinierenden Spezies mathematischer Aussagen über die prinzipiellen Grenzen des Machbaren. Mit der Eulerschen Formel erhalten Sie schließlich einen ersten Einblick in das reizvolle Gebiet der Topologie.

Dinge abzuzählen ist eine der ureigensten Aufgaben der Mathematik. Abzählprobleme können wir im Alltag antreffen (wie oft klingen die Sektgläser, wenn sich 10 Personen zuprosten?), und wir begegnen ihnen beim Berechnen von Wahrscheinlichkeiten. In den vorangegangenen Kapiteln haben Sie bereits einige Abzählprobleme untersucht, und Sie haben die Technik der Rekursion kennengelernt. In diesem Kapitel gehen wir Abzählprobleme systematisch an. Abzählen ist nicht nur Selbstzweck, es kann auch Mittel zu anderen Zwecken sein. Zum Beispiel kann man mit Hilfe der Technik des doppeltes Abzählens viele interessante Formeln herleiten. Das doppelte Abzählen ist eine Grundidee, die in verschiedenen Verkleidungen in vielen Bereichen der Mathematik auftritt. Einige davon werden am Ende des Kapitels erklärt.

Allgemeine Problemlösestrategien sind Strategien, die nicht nur in der Mathematik, sondern auch in vielen anderen Lebensbereichen eingesetzt werden können: Möchte ich ein Problem lösen, hilft es mir, mich zu erinnern, wie ich ähnliche Probleme gelöst habe. Möchte ich ein Ziel erreichen, kann ich mir überlegen, welche Schritte ich zuerst unternehmen sollte, um dorthin zu gelangen (Vorwärtsarbeiten); oder ich überlege zunächst, wie der letzte Schritt zum Erreichen des Ziels aussehen könnte (R ückwärtsarbeiten) und welche Zwischenziele ich mir setzen könnte. Wir werfen nun einen systematischen Blick auf diese Problemlösestrategien und stellen sie in einfachen Diagrammen dar, die dabei helfen können, den Überblick zu behalten. Dann untersuchen wir einige Probleme, eines aus der Geometrie und eines über gewisse Summendarstellungen von Zahlen, und achten dabei besonders darauf, wie wir diese Strategien einsetzen.

Wir formulieren mathematische Argumente in unserer natürlichen Sprache. Diese ist oft mehrdeutig, und im Alltag hört und liest man häufig logische Fehlschlüsse. Um zuverlässig argumentieren zu können, sollten Sie sich daher über die wichtigsten logischen Konstrukte und Sprechweisen im Klaren sein. Diese werden im ersten Abschnitt dieses Kapitels behandelt. Bei der Untersuchung eines mathematischen Sachverhalts beobachten wir Zusammenhänge und Muster, haben wir Einsichten, stellen Vermutungen auf. Um sicher zu sein, dass eine Vermutung stimmt, brauchen wir einen Beweis. Eine der Grundlagen des Beweisens bildet die Logik. Sie hilft Ihnen sicherzustellen, dass ein Argument oder Beweis schlüssig (also richtig und vollständig) ist. Eine ganz andere Frage ist, wie Sie einen Beweis finden. Dabei helfen Ihnen Erfahrung, allgemeine Problemlösestrategien und die Kenntnis typischer Beweismuster. Zu den allgemeinen Beweisformen direkter und indirekter Beweis kommen je nach Kontext zahlreiche weitere typische Beweismuster hinzu. Im zweiten Abschnitt dieses Kapitels werden die allgemeinen Beweisformen und einige dieser Beweismuster vorgestellt und mit Beispielen illustriert. Drei von ihnen lernen Sie in den folgenden Kapiteln noch eingehender kennen. Natürlich sind Ihrer Kreativität im Erfinden von Beweisen über diese typischen Formen hinaus keine Grenzen gesetzt!

Die Zahlentheorie ist die Lehre von den ganzen Zahlen. Hier geht es um Teilbarkeit, Primzahlen usw. Ganze Zahlen sind konkrete Objekte, mit denen Sie schon seit Kindheitstagen gespielt haben. Daher eignet sich die Zahlentheorie bestens für Ihre Entdeckungsreise in die Mathematik, und Sie finden Probleme zahlentheoretischer Natur über das ganze Buch verstreut. Trotzdem sei nicht verschwiegen, dass sich mit diesen einfachen Begriffen einige der schwierigsten, bis heute ungelösten mathematischen Probleme formulieren lassen. In diesem Kapitel werden einige grundlegende Definitionen und Sätze der Zahlentheorie zusammengestellt. Viele der Sätze werden Sie anhand von Beispielen sofort einsehen, daher können Sie dies als Übungsfeld ansehen, Ihre Zahlenintuition in mathematische Beweise umzusetzen. Sie werden auch den Begriff der Kongruenz kennenlernen, der es erlaubt, mit einfachen Mitteln manch komplizierte Frage zu beantworten.

Wenn vieles auf wenige Schubfächer verteilt wird, muss mindestens ein Schubfach viel erhalten. Das ist eine Binsenweisheit, und doch ist es die Grundlage vieler mathematischer Argumente. Mal offenkundig, mal versteckt, hat das Schubfachprinzip mitunter überraschende Konsequenzen. Es ist eines der wenigen ganz allgemeinen Prinzipien der Mathematik, ein wichtiges Hilfsmittel für Existenzbeweise. Die Kunst besteht darin zu erkennen, wo man es anwenden kann. In diesem Kapitel lernen Sie nach einer genauen Formulierung des Prinzips zunächst einige einfache Konsequenzen aus dem Alltag kennen. Indem wir dann Reste als Schubfächer betrachten, erhalten wir einige überraschende Aussagen über Zahlen. Wir werden auch die Frage erkunden, wie gut man beliebige Zahlen durch Brüche approximieren kann, und dort unvermittelt auf das Schubfachprinzip stoßen. Angewendet auf ein Problem aus der Graphentheorie zeigt das Schubfachprinzip schließlich, dass selbst im chaotischsten Dickicht noch Ordnung zu finden ist.

Extreme faszinieren. Wer ist am kleinsten, größten, schnellsten, stärksten? Alltagsmetaphern (der Weg des geringsten Widerstands, etwas auf die Spitze treiben usw.) belegen, wie tief die Idee des Extremen in uns verankert ist. Auch der wissenschaftliche Blick auf die Welt offenbart vielerorts Extreme: Die Seifenblase versucht, ihre Oberfläche möglichst klein zu machen, und nimmt deshalb Kugelform an. Chemische Reaktionen streben einen Zustand minimaler Energie an. Die Liste ließe sich beliebig verlängern. Die Seifenblase zeigt noch etwas: Extreme Formen haben oft besondere Eigenschaften, sind zum Beispiel sehr regelmäßig oder symmetrisch. Indem wir dies rückwärts lesen, finden wir eine Problemlösestrategie: Suchst du ein Objekt mit speziellen Eigenschaften, versuche, es durch eine extreme Eigenschaft zu charakterisieren. Damit werden Extreme zu einem Mittel, um besondere Objekte zu finden oder zumindest ihre Existenz zu beweisen. Auch bei anderen Problemen kann es nützlich sein, nach extremen Fällen Ausschau zu halten, das gibt Ansatzpunkte, strukturiert die Gedanken. Für alle diese Formen des Extremalprinzips finden Sie in diesem Kapitel Beispiele. Nebenbei lernen Sie zwei fundamentale Ungleichungen und Interessantes zu Spiegeln und Billardtischen kennen. Das Extremalprinzip ist eine Idee sehr großer Tragweite. Sie werden ihr immer wieder begegnen, wenn Sie sich mit Mathematik befassen. Halten Sie die Augen offen!

”Wo sich Dinge ändern, achte auf das, was gleich bleibt!“ Was wie eine Weltanschauung anmutet, ist eine der fundamentalen Ideen, die die ganze Mathematik durchziehen, und ein sehr patentes Problemlösewerkzeug. Viele komplexe Prozesse setzen sich aus einfachen Schritten zusammen: Die Möglichkeiten für einen Zug im Schachspiel sind überschaubar, doch eine ganze Partie ist äußerst komplex. Gehen Sie in einer Stadt spazieren, so ist jeder Ihrer Schritte unproblematisch, nach einiger Zeit können Sie sich aber verlaufen. Ein physikalisches System ändert sich momentan nur wenig, über einen längeren Zeitraum aber kann es seinen Zustand vollständig und unvorhersehbar ändern. Das Invarianzprinzip hilft Ihnen, trotz dieser Komplexität Informationen über solche Prozesse zu gewinnen. Sie lernen es in diesem Kapitel anhand zahlreicher Beispiele kennen. Dabei erfahren Sie Interessantes über das berühmte 15er-Puzzle und über das Solitaire-Spiel und lernen nebenbei einiges über Permutationen und ihre Signatur, grundlegende Konzepte der Mathematik.

Hier finden Sie einen Überblick über die Problemlösestrategien, die Sie in diesem Buch kennengelernt haben.

Die Sprache der Mengen und Abbildungen hat sich als Basissprache in der modernen Mathematik durchgesetzt. Da sie sehr praktisch ist, wird sie auch in diesem Buch an vielen Stellen verwendet. Daher werden hier die wichtigsten Begriffe zusammengetragen.