Allgemeines zum Buch

Problem-Solving Strategies ist eine einzigartige Sammlung von Aufgaben aus 20 bedeutenden nationalen und internationalen mathematischen Wettbewerben für Abiturienten und Studenten. Die Abhandlung der Strategien zum Lösen von Problemen präsentiert sich sehr umfangreich. Das Buch ist zum einen für Übungsleiter und Teilnehmer an Mathematikwettbewerben gerichtet, wie auch an alle, die den Spaß am Lösen von Problemen nicht verloren haben. Die Auswahl der Aufgaben wurde didaktisch wertvoll gestaltet. Beginnend von einfachen Problemen verlangen die Aufgaben zunehmend mehr Kreativität und stetige Geduld ab. Diese Buch ist ein Muss für Lehrer und Dozenten, die Ihren Unterricht mit interessanten nicht alltäglichen Problemen anreichern wollen und für solche, die sich schweren und herausfordernden Problemen gerne stellen.

Jedes Kapitel beginnt mit typischen Beispielen, die die zentralen Konzepte verdeutlichen. Anschließend folgen eine Vielzahl von sorgfältig ausgewählten Problemen und ihren Lösungen. Die meisten Lösungen sind vollständig, aber einige zeigen nur den Weg bis zur finalen Lösung. Nur für sehr wenige Probleme von insgesamt mehr als 1300 Aufgaben sind keine Lösungen angegeben.

Problem-Solving Strategies ist eine reichhaltige Quelle für mathematische Problemstellungen und Lösungstrategien, aber vor allem ist es eines der vollkommensten Bücher auf dem Markt.

Zum Inhalt des Buches

Es sollen es kurz die Strategien der einzelnen Kapitel mit einer jeweils sehr einfachen Aufgabe vorgestellt werden.

The Invariance Principle. Das Prinzip der Invarianz ist anwendbar auf Algorithmen, Spiele, Transformationen und Zahlenfolgen. In einem Prozess, wo ständig die gleiche Sache wiederholt wird, sollte man nach Größen suchen, die sich nicht verändern.
Auf das folgende Problem ist das Invarianz-Prinzip direkt anwendbar.
Beispiel: Ein Kreis sei in sechs Sektoren eingeteilt. Nun schreibe man die Zahlen 1, 0, 1, 0, 0, 0 (zum Beispiel im Uhrzeigersinn) in die Sektoren. Nun können immer in einem Schritt jeweils zwei benachbarte Zahlen um eins erhöht werden. Ist es möglich, Gleichheit der sechs Zahlen mit einer gewissen Anzahl von Schritten zu erreichen?
Lösung: Seien a1,…,a6 die Zahlen momentan in den Sektoren. Dann ist I:=a1-a2+a3-a4+a5-a6 eine Invariante. Da zu Beginn I=2 ist, und I=0 bei Gleichheit der Zahlen wäre, kann Gleichheit nie erreicht werden.

Coloring Proofs. Die Probleme in diesem Kapitel beschäftigen sich mit der Zerlegung einer Menge in endlich viele Teilmengen. Eine solche Partitionierung kann als Färbung der Elemente der Mengen betrachtet werden, wobei zwei Elemente die gleiche Farbe haben, genau dann wenn sie in der gleichen Partition liegen.
Hier ein typisches Färbungsproblem.
Beispiel: Jeder Punkt der Ebene sei entweder rot oder blau gefärbt. Zeige, dass es ein Viereck in der Ebene gibt, dessen Ecken die gleiche Farbe haben.

The Extremal Principle. Versucht man die Existenz eines Objektes mit einer spezifischen Eigenschaft zu beweisen, so kann die Anwendung des Extremal-Prinzip hilfreich sein. Das Extremal-Prinzip sagt uns, dasjenige Objekt zu nehmen, dass irgendeine Funktion minimiert oder maximiert. Von diesem Objekt muss dann gezeigt werden, dass eine leichte Variation des Objektes einen größeren bzw. kleineren Funktionswert zur Folge hat.
Beispiel: Jeder Gitterpunkt in der Ebene ist mit einer positiven Zahl beschriftet. Jede Zahl ist das arithmetische Mittel seiner vier Gitternachbarn. Zeige, dass dann die Zahlen in allen Gitterpunkten gleich sein müssen.
Lösung: Sei m die kleinste dieser Zahlen und sei L ein beliebiger, der mit m beschriftet ist. Die Nachbarn wollen wir mit a, b, c und d bezeichnen. Dann gilt demnach m = (a+b+c+d)/4 bzw. a+b+c+d=4m. Da m als die kleinste Zahl gewählt wurde, sind a, b, c und d größer gleich m. Wenn jedoch nur eine der vier Zahlen echt größer als m ist, folgt a+b+c+d>4m. Widerspruch.

The Box Principle. Die Grundidee: Wenn n+1 Socken auf n Schubfächer verteilt werden, dann liegen in einem Schubfach mindestens 2 Socken.
Das Schubfachprinzip wird von vielen Leuten als trivial verpöhnt. Es folgen aber damit eine Menge überraschender Anwendungen. Ebenso lassen sich tiefe Theoreme beweisen.
Beispiel: Es seien n ganze nicht notwendigerweise verschiedene Zahlen a1, a2, … gegeben. Zeige, dass immer eine Teilmenge dieser Zahlen existiert, so dass deren Summe durch n teilbar ist.
Lösung: Wir betrachten weitere n Zahlen s1=a1, s2=a1+a2, s3=a1+a2+a3,… Jede der Zahlen s1, s2, … läßt ein Rest bei Division mit n. Da n-1 verschiedene solcher Reste möglich nicht, müssen nach dem Schubfachprinzip mindestens 2 der n Zahlen s1, s2, … den gleichen Rest mit Division n lassen. Die Differenz dieser beider Zahlen wird durch n ohne Rest geteilt und impliziert die gesuchte Teilmenge.

Enumerative Combinatorics. In der enumerativen Kombinatorik geht es um das Abzählen von Objekten mit einer bestimmten Eigenschaft. Zu den Grundlagen der abzählenden Kombinatorik gehören zum Beispiel Permutationen und Kombinationen. Auch wenn oft weniger mathematische Fähigkeiten als viel mehr Kreativität gefragt sind, gibt es einige Konzepte, mit denen man vertraut sein sollte – allen voran die “Divide and Conquer”-Methode.
Beispiel: An einem Tennisturnier neben 2n Spieler teil. Wie viele Spiele gibt es in der ersten Runde?
Lösung: Alle 2n Spieler stellen sich in einer Reihe auf. Dafür gibt es genau (2n)! Möglichkeiten. Nun bilden wir Pärchen: (1,2)(3,4)….(2n-1,2n). Da die Paarungen (i,i+1) und (i+1,i) identisch sind und die Reihenfolge der Pärchen ebenfalls uninteressant ist, müssen wir noch Mehrfachzählungen eliminieren. Die Reihenfolge der n Paare wird durch n! ausgedrückt. Die doppelt gezählten Paare aufgrund der Reihenfolge innerhalb der n Paare wird durch 2^n erfasst. Damit gibt es insgesamt (2n)!/(2^n n!) Spiele in der ersten Spielrunde.

Number Theory. Die elementare Zahlentheorie beschäftigt sich hauptsächlich mit den Eigenschaften ganzer Zahlen und baut hauptsächlich auf dem Teilbarkeitsbegriff auf. Zum Lösen von Aufgaben aus der Zahlentheorie bedarf es umfassender Vorbereitung. Dieses Kapitel stellt die wichtigste Hilfsätze bereit (Fundamentalsatz der Arithmetik, Euklids Lemma, Kleiner Satz von Fermats, Satz von Euler und Fermat, Sophie Germain Identität).
Beispiel: Für n>1 ist z = n^4 + 4^n keine Primzahl.
Lösung: Falls n gerade ist, ist z auch gerade und kann damit nicht Primzahl sein. Wenn n=2k+1 ungerade ist, gilt n^4+4^n = n^4+4*4^(2k) = n^4+4*(2^k)^4.
Letztes hat die Form a^4 + 4*b^4=(a^2+2b^2+2ab)(a^2+2b^2-2ab), ist also faktorisierbar und folglich nicht prim.

Inequalities. Neben Identitäten spielen Ungleichungen eine wichtige Rollen und gehören zum Handwerkszeug eines jeden Mathematikers. Häufig werden Ungleichungen zu Abschätzung in Widerspruchsbeweisen benutzt – die Cauchy-Schwarz-Ungleichung ist wohl die berühmteste. Auch sollte man wissen, in welcher Relation arithmetisches, geometrisches und harmonisches Mittel stehen.
Beispiel: Zeige, dass für jedes Dreieck mit den Seiten a, b, c und der Fläche A gilt: a^2 + b^2 + c^2 >= 4*A*Wurzel(3).

The Induction Principle. Das Prinzip der vollständigen Induktionen wird benutzt, um eine All-Ausage A(n) für alle Zahlen n>=k zu beweisen. Dabei geht man in zwei Schritten vor. Zunächst zeigt man (oft relativ einfach), dass A(k) gilt. Im zweiten Schritt nimmt man an, dass die Aussagen A(k),A(k+1),…,A(n-1) schon bewiesen worden und zeigt, dass A(n) zwingend folgt. Das Kapitel setzt jedoch ein wenig Erfahrung mit Induktionbeweisen voraus, denn es werden ausschließlich nicht-triviale Probleme vorgestellt; Insbesondere in Verbindung mit Fibonacci-Zahlen.

Sequences. In diesem Kapitel über Zahlenfolgen geht es um die Darstellung einer Folge in geschlossener Form, über Konvergenz, Grenzwert und Konvergenzgeschwindigkeit. Die zulösenden Probleme sind mit den Methoden der vorherigen Kapitel sehr gut zu meistern.
Beispiel: Die Funktion f(x) erfülle für alle reellen Zahlen x die Gleichung f(x+1)-f(x-1)=Wurzel(2)f(x). Zeige, dass die Funktion f(x) periodisch ist.
Lösung: Mit a=f(x-1) und b=f(x), schreiben wir f(x+1)=Wurzel(2)b+a, f(x+2)=b-Wurzel(2)a, f(x+3)=-a, f(x+4)=-b. Wir sehen, dass f(x+4)=-f(x). Also folglich f(x+8)=f(x). Damit hat f(x) die Periode 8.

Polynomials. Hier erfährt man kurz und knapp das wichtigste über Polynome: Fundamentalsatz der Algebra, Satz von Vieta, Polynomdivision und Polynome mit mehreren Veränderlichen.
Beispiel: Seien a, b, c drei paarweise verschieden ganze Zahlen und P ein Polynome mit ganzzahligen Koeffizienten. Zeige, dass kein Polynom P existiert, dass alle drei Bedingungen P(a)=b, P(b)=c, P©=a gleichzeitig erfüllen kann.

Functional Equations. In den Kapiteln über Zahlenfolgen und Polynome sind schon einige funktionale Gleichungen aufgetaucht – siehe die beiden letzten angeführten Beispiele. Funktionale Gleichungen sind solche, bei denen eine Funktion gesucht ist, die die angegebene Relation (für jeden ihrer Werte) erfüllt.
Beispiel: Im letzten Beispiel wurde gezeigt, dass kein Polynom die dort angebenen Relationen erfüllt.

Geometry. Die Aufgaben zur Geometrie sind in drei Abschnitte aufgeteilt. Im ersten Abschnitt geht es allgemein um Vektoren im 2- oder 3-dimensionalen Vektorraum. Anschließend werden Transformationen im Vektorraum, wie Spiegelung, Rotation oder Verschiebungen diskutiert. Der letzte Abschnitt über die klassische euklidische Geometrie ist zugleich der umfangreichste. Dabei geht es um Probleme, wie sie auch oft im Mathematik-Unterricht durchgenommen wurden. Das folgende Beispiel zeigt eine typische Fragestellung.

Games. Hauptsächlich werden hier Probleme zu 2-Personen-Spielen untersucht, wobei beide Spieler abwechselnd am Zug sind. Es tauchen immer wieder die folgenden typischen Fragen auf. Gibt es eine Gewinn-Strategie für einen Spieler? Ist das Spiel fair? Wer gewinnt? Finde eine Gewinn-Strategie! Welche initialen Positionen führen zu einem Sieg für Spieler 1 bzw. Spieler 2?
Further Strategies. Das letzte Kapitel schneidet kurz die Graphentheorie an, mit der einige Probleme übersichtlicher modellieren werden können. Darüber hinaus wird eine der ältesten Beweisstrategien vorgestellt: Der unendlich Abstieg. Pierre de Format war stolz, seine ganzen Theoreme aus der Zahlentheorie hauptsächlich nur mit dieser Methode bewiesen zu haben. Ziel beim unendlich Abstieg ist es, die Unmöglichkeit einer Lösung zu einer vorgegebenen Gleichung zu finden. Ausgehend von einer – hypothetisch gesehen – schon gefundenen Lösung, konstruiert man daraus eine weitere, die in einem gewissen Sinn echt kleiner ist als die Ausgangslösung. Ein Klassiker ist der folgende Fakt.
Beispiel: Man zeige, das die Wurzel aus 2 irrational ist.

Inhaltsverzeichnis

1. The Invariance Principle
2. Coloring Proofs
3. The Extremal Principle
4. The Box Principle
5. Enumerative Combinatorics
6. Number Theory
7. Inequalities
8. The Induction Principle
9. Sequences
10. Polynomials
11. Functional Equations
12. Geometry
13. Games
14. Further Strategies