Source: https://b-ok.org/book/609431/16d8d1
Timestamp: 2019-05-21 23:25:14+00:00

Document:
Diskrete Mathematik fuer Einsteiger | Albrecht Beutelspacher | download
Main Diskrete Mathematik fuer Einsteiger
ISBN 10: 3834800945
ISBN 13: 9783834800947
Mit Anwendungen in Technik und Informatik
Albrecht.Beutelspacher@math.uni-giessen.de
Marc.Zschiegner@weidigschule.de
2., durchgesehene Auflage August 2004
3., erweiterte Auflage März 2007
Lektorat: Ulrike Schmickler-Hirzebruch | Petra Rußkamp
ISBN 978-3-8348-0094-7
Was ist diskrete Mathematik?
Diskrete Mathematik ist ein junges Gebiet der Mathematik, das in einzigartiger Weise
sogenannte „reine Mathematik“ mit „Anwendungen“ verbindet.
Um diese Antwort zu verstehen, müssen wir etwas weiter ausholen. Bis vor wenigen
Jahrzehnten hatte nach allgemeiner Meinung die angewandte Mathematik ausschließlich
die Aufgabe, die physikalische Welt möglichst gut und aussagekräftig zu beschreiben.
Typische Fragen waren dabei:
Wie modelliert man den Raum?
Wie misst man den Raum?
Wie beschreibt man Bewegungen?
Die mathematischen Disziplinen, die sich mit solchen Fragestellungen beschäftigen,
sind die Geometrie und die Analysis, sowie alle sich daraus ableitenden Teildisziplinen.
Dies sind vor allem Teilgebiete der Mathematik, die sich mit kontinuierlichen, „stetigen“
Phänomenen beschäftigen.
Im 20. Jahrhundert, insbesondere seit der Einführung des Computers in der Mitte des
Jahrhunderts, drängte sich ein anderer Typ von Fragen in den Vordergrund. Die Herausforderung besteht darin, Modelle zum Verständnis und zur Beherrschung von endlichen, eventuell allerdings sehr großen Phänomenen und Strukturen zu entwickeln. Solche
Strukturen können sein:
Eine Gesellschaft als Menge ihrer endlich vielen Mitglieder,
ein ökonomischer Prozess mit nur endlich vielen möglichen Zuständen,
ein Computer, der nur Zahlen bis zu einer gewissen Größe verarbeiten kann,
Die mathematischen Disziplinen, die sich mit solchen diskreten Phänomenen beschäftigen, sind Kombinatorik, Graphentheorie, Algebra, Zahlentheorie, Codierungstheorie,
Kryptographie, Algorithmentheorie usw. Man fasst diese Disziplinen oft unter dem Begriff
diskrete Mathematik zusammen. Diskrete Mathematik schafft eine Verbindung von der reinen Mathematik zu den Anwendungen und insbesondere zur Informatik. Das Wort
„diskret“ hat also in diesem Zusammenhang nichts zu tun mit „heimlich“, „verborgen“
o.ä., sondern bezieht sich darauf, dass endliche, das heißt diskrete Phänomene untersucht
Das Ziel dieses Buches besteht darin, Sie in möglichst elementarer Weise mit den Grundzügen einiger der oben genannten Gebiete vertraut zu machen. Das beginnt in Kapitel 1
mit dem Schubfachprinzip, einer fast trivialen Aussage mit unglaublichen Folgerungen. In
Kapitel 2 werden Färbungsmethoden eingesetzt, und zwar konstruktiv und für Nicht-
existenzbeweise. Die vollständige Induktion, ein unentbehrliches mathematisches Werkzeug wird in Kapitel 3 eingeführt und an Beispielen klar gemacht. Kapitel 4 ist einem zentralen Aspekt der diskreten Mathematik gewidmet, nämlich dem Zählen; wir werden eine
ganze Reihe von Formeln erarbeiten, die es uns ermöglichen, Mengen mit komplexen
Elementen abzuzählen. Daran schließt sich das Kapitel an, in dem die Zahlen der Untersuchungsgegenstand sind; es geht hauptsächlich um die Teilbarkeit ganzer Zahlen.
Der zweite Teil des Buches ist ausgesprochen angewandten Themen gewidmet. Im
sechsten Kapitel werden Codes behandelt; dazu gehören zum Beispiel die Strichcodes der
Lebensmittel und die ISBN-Codes der Bücher. In Kapitel 7 geht es um Datensicherheit,
das heißt Kryptographie; insbesondere werden die Themen „Verschlüsselung“ und „Authentifizierung“ behandelt, und zwar sowohl in der klassischen Kryptographie als auch in
der modernen Public-Key-Kryptographie. Im achten Kapitel werden Graphen behandelt,
ein außerordentlich wichtiges Gebiet der diskreten Mathematik. Dies wird in Kapitel 9
durch die Behandlung von gerichteten Graphen fortgeführt. Das letzte Kapitel widmet sich
schließlich der Booleschen Algebra und der Entwicklung elektronischer Schaltkreise.
An mathematischen Vorkenntnissen wird nicht viel vorausgesetzt. Sie kommen mit
Schulkenntnissen gut aus. Insbesondere wird keine Analysis und keine lineare Algebra gebraucht. Allerdings müssen wir, wie in der Mathematik unumgänglich, Ihre Bereitschaft
voraussetzen, sich ein Stück weit auf vergleichsweise abstrakte Argumentation einzulassen, bei der man nicht immer sofort sieht, worauf sie hinaus soll.
Das Buch eignet sich zur Begleitung der entsprechenden Vorlesungen an Fachhochschulen und Universitäten. Es eignet sich besonders gut zum Selbststudium und kann in
Arbeitsgemeinschaften an Gymnasien eingesetzt werden. Beim Schreiben haben wir besonders an die „Einsteiger“ gedacht. In den ersten Kapiteln gehen wir sehr behutsam vor
und legen keinen Wert auf übertriebenen Formalismus. In den späteren Kapiteln wird die
Argumentationsdichte dann größer.
Das Buch enthält eine Fülle von Übungsaufgaben, insgesamt über 200. Wir sind der
Überzeugung, dass alle lösbar sind, manche sogar sehr einfach. Sie dienen nicht nur dazu,
den Stoff zu festigen, sondern erschließen oft auch neue Aspekte. Im letzten Kapitel finden
Sie ausführliche Lösungen zu allen Übungsaufgaben. Sie dürfen gerne nachschauen  aber
erst, wenn Sie selbst probiert haben!
Wenn Sie, liebe Leserin, lieber Leser, Anregungen haben oder gar Druck- oder andere
Fehler gefunden haben, bitten wir Sie, uns diese mitzuteilen.
Wir danken den Hörern unserer Vorlesungen und unseren Kolleginnen und Kollegen
für zahlreiche Anregungen und dem Verlag Vieweg für die unendliche Geduld mit diesem
Marc-A. Zschiegner
1 Das Schubfachprinzip
1.1 Was ist das Schubfachprinzip?
1.2 Einfache Anwendungen
1.3 Cliquen und Anticliquen
1.4 Entfernte Punkte im Quadrat
1.5 Differenzen von Zahlen
1.6 Teilen oder nicht teilen
1.7 Das verallgemeinerte Schubfachprinzip
1.8 Das unendliche Schubfachprinzip
2 Färbungsmethoden
2.1 Überdeckung des Schachbretts mit Dominosteinen
2.2 Überdeckung des Schachbretts mit größeren Steinen
2.3 Monochromatische Rechtecke
2.4 Eine Gewinnverhinderungsstrategie
2.5 Das Museumsproblem
2.6 Punkte in der Ebene
3.1 Das Prinzip der vollständigen Induktion
3.2 Anwendungen des Prinzips der vollständigen Induktion
3.3 Landkarten schwarz-weiß
3.4 Fibonacci-Zahlen
4.1 Einfache Zählformeln
4.2 Binomialzahlen
4.3 Siebformel
5.1 Teilbarkeit
5.2 Division mit Rest
5.3 Der größte gemeinsame Teiler
5.4 Zahlendarstellung
5.5 Teilbarkeitsregeln
5.6 Primzahlen
5.7 Modulare Arithmetik
6 Fehlererkennung
6.1 Die Grundidee
6.2 Paritätscodes
6.3 Codes über Gruppen
6.4 Der Code der ehemaligen deutschen Geldscheine
7.1 Klassische Kryptographie
7.2 Stromchiffren
7.3 Blockchiffren
7.4 Public-Key-Kryptographie
8 Graphentheorie
8.2 Das Königsberger Brückenproblem
8.3 Bäume
8.4 Planare Graphen
8.5 Färbungen
8.6 Faktorisierungen
9.1 Gerichtete Graphen
9.2 Netzwerke und Flüsse
9.3 Trennende Mengen
10 Boolesche Algebra
10.1 Grundlegende Operationen und Gesetze
10.2 Boolesche Funktionen und ihre Normalformen
10.3 Vereinfachen von booleschen Ausdrücken
10.4 Logische Schaltungen
Eines der grundlegenden Prinzipien der Mathematik ist das Schubfachprinzip. Es wirkt
vollkommen unschuldig und macht keinerlei Aufhebens von sich. Aber es tut nur so, in
Wirklichkeit kann man mit ihm die unglaublichsten Aussagen beweisen. Das Schubfachprinzip heißt manchmal auch „Taubenschlagprinzip“ (pigeonhole principle). Es wurde
erstmals von L. Dirichlet (1805 - 1859) explizit formuliert.
Die folgenden Aussagen sind offenbar richtig:
x Unter je 13 Personen gibt es mindestens zwei, die im selben Monat Geburtstag haben.
x Unter je drei Personen haben mindestens zwei dasselbe Geschlecht.
x Unter je 20 Studenten gibt es mindestens zwei aus demselben Fachbereich.
x Unter je 50 Studierenden gibt es mindestens zwei mit derselben Semesterzahl.
x Es gibt zwei Deutsche mit derselben Anzahl von Haaren.
Hinter all diesen Aussagen steckt ein allgemeines Schema – das Schubfachprinzip:
Schubfachprinzip. Seien m Objekte in n Kategorien („Schubfächer“) eingeteilt. Wenn
m > n ist, so gibt es mindestens eine Kategorie, die mindestens zwei Objekte enthält.
Die Veranschaulichung ist klar: Wenn viele Tauben sich auf wenige Taubenschläge verteilen, dann sitzen in mindestens einem Taubenschlag mindestens zwei Tauben.
Bild 1.1 Sechs Objekte sind in fünf Kategorien eingeteilt
Der Beweis des Schubfachprinzips ist klar: Wenn jede der n Kategorien höchstens ein
Objekt enthalten würde, dann gäbe es insgesamt höchstens n Objekte: ein Widerspruch,
da es nach Voraussetzung mehr Objekte als Schubfächer gibt.
Wir diskutieren jetzt einige Anwendungen dieses Prinzips. Die ersten sind ganz einfach,
andere vergleichsweise raffiniert.
Die Socken von Professor Mathemix
In der Sockenkiste von Professor Mathemix befinden sich 10 graue und 10 braune Socken. Der Professor nimmt – in Gedanken versunken – eine Reihe von Socken heraus. Wie
viele muss er herausnehmen, um
(a) garantiert zwei gleichfarbige,
(b) garantiert zwei graue Socken zu erhalten?
Lösung: Wir teilen die Socken des Herrn Professor in zwei Kategorien ein, in die Kategorie der grauen und die der braunen Socken; dann ist n = 2.
(a) Wenn Professor Mathemix m = 3 Socken seiner Kiste entnimmt, so sind nach dem
Schubfachprinzip mindestens zwei aus derselben Kategorie. Also hat er entweder zwei
graue oder zwei braune Socken gezogen.
(b) Wenn er aber darauf besteht, zwei Socken seiner Lieblingsfarbe grau zu bekommen, so
muss er im schlimmsten Fall 12 Socken ziehen, denn die ersten 10 könnten ja alle braun
Gleiche Zahl von Bekannten
Wir behaupten: In jeder Gruppe von mindestens zwei Personen gibt es zwei, die die gleiche Anzahl von Bekannten innerhalb dieser Gruppe haben.
Dabei setzen wir voraus, dass „bekannt sein“ symmetrisch ist, dass also aus der Tatsache, dass X mit Y bekannt ist, auch folgt, dass Y mit X bekannt ist. Außerdem wollen
wir zu den Bekannten einer Person nicht diese Person selbst rechnen.
Man kann statt „bekannt sein“ jede andere symmetrische Relation einsetzen.
Bild 1.2 Bekanntschaften
Warum ist diese Behauptung richtig? Warum gilt sie nicht nur für dieses Beispiel sondern
für alle denkbaren Konstellationen von Personen und ihren Bekanntschaftsverhältnissen?
Um das einzusehen, brauchen wir das Schubfachprinzip. Dazu müssen wir uns klarmachen, was die Objekte und was die Kategorien sind.
Für die Objekte gibt es naheliegende Kandidaten, nämlich die Personen der Gruppe.
Sei m die Anzahl der Personen.
Für die Kategorien müssen wir die Bekanntschaftsrelation berücksichtigen. Wir fassen
diejenigen Personen in einer Kategorie zusammen, die die gleiche Anzahl von Bekannten
haben. Das bedeutet:
x In der Kategorie K0 sitzen genau die armen Tropfe, die überhaupt keine Bekannten
x in K1 stecken diejenigen elitären Menschen, die sich mit einem einzigen Bekannten
begnügen;
x in Km–1 finden sich schließlich diejenigen liebenswerten Menschen, die alle anderen
kennen (und jedem anderen bekannt sind).
Allgemein können wir sagen:
x In der Kategorie Ki befinden sich genau diejenigen Personen der Gruppe, die genau i
Bekannte innerhalb der Gruppe haben.
Damit haben wir die Kategorien K0, K1, ..., Km–1 definiert; dies sind genau m Kategorien, also genau so viele wie Objekte. Können wir das Schubfachprinzip anwenden?
Nein, denn dieses hat als Voraussetzung, dass die Anzahl der Objekte größer als die Anzahl der Kategorien ist.
Was tun? Die einzige Möglichkeit ist, eine Kategorie loszuwerden. Das können wir aber
nicht dadurch machen, dass wir eine Kategorie verbieten, sondern dadurch, dass wir
nachweisen, dass eine Kategorie in Wirklichkeit überhaupt nicht in Erscheinung tritt.
Welche Kategorie könnte das sein? Das können wir nicht sagen, wir können aber zeigen,
dass folgende Aussage gilt: Von den Kategorien K0 und Km–1 tritt höchstens eine auf.
Mit anderen Worten: Wenn eine von diesen Kategorien ein Objekt enthält, dann die andere
Wir betrachten also die Situation, dass mindestens eine Person P in die Kategorie Km–1
fällt. Das bedeutet, dass P alle anderen Personen der Gruppe kennt. Dann kennen aber
auch alle Personen der Gruppe die Person P („bekannt sein“ ist symmetrisch!). Also hat
jede Person der Gruppe mindestens einen Bekannten. Das heißt, dass keine Person in der
Kategorie K0 ist.
Also haben wir unsere Zwischenaussage bewiesen. Es gibt daher höchstens m–1 Kategorien, die überhaupt eine Person enthalten. Jetzt können wir das Schubfachprinzip anwenden. Dieses liefert uns eine Kategorie mit mindestens zwei Objekten, also zwei Personen mit der gleichen Anzahl von Bekannten.
Jetzt fragen wir nach größeren Bekanntschaftskreisen. Wir behaupten:
Unter je sechs Personen gibt es stets drei, die sich paarweise kennen, oder drei, die sich
paarweise nicht kennen.
Bild 1.3 Bekanntschaften unter 6 Personen
Warum ist das richtig? Wir greifen irgendeine Person, sagen wir P1, heraus und betrachten
zunächst deren Bekannte. Hätte P1 höchstens 2 Bekannte und 2 Nichtbekannte, dann
könnte es nur 4 weitere Personen geben. Also hat P1 drei Bekannte oder drei Nichtbekannte in der Gruppe. Nehmen wir zu seinen Gunsten an, er habe drei Bekannte P2, P3
und P4.
Nun unterscheiden wir zwei einfache Fälle.
1. Fall: Unter den Personen P2, P3, P4 gibt es zwei, die sich kennen, sagen wir P2 und
P3. Dann kennen sich P1, P2 und P3 gegenseitig. Daher ist die Behauptung richtig.
Bild 1.4 P1, P2 und P3 kennen sich
2. Fall: Keine zwei der Personen P2, P3, P4 kennen sich. Dann ist P2, P3, P4 eine Menge
von Personen, die sich gegenseitig nicht kennen. Auch in diesem Fall gilt also die Behauptung.
Bild 1.5 P2, P3 und P4 kennen sich gegenseitig nicht
Bemerkung. Diese einfache Beobachtung ist der Beginn der sogenannten Ramsey-Theorie.
Im Jahre 1928 bewies F. P. Ramsey (1903 – 1930) einen Satz eines neuen Typs: Gegeben
seien zwei natürliche Zahlen m, n t 2. Dann gibt es eine natürliche Zahl M, so dass für
jede Menge von mindestens M Personen gilt: Es gibt unter den Personen der Menge n
Personen, die sich paarweise kennen oder m Personen, die sich paarweise nicht kennen
(siehe Ramsey 1930 und van Lint 2001).
Wir betrachten ein Quadrat der Seitenlänge 2 und fragen uns, wie viele Punkte wir in das
Quadrat einzeichnen können, von denen je zwei „weit voneinander entfernt“ sind. Die
Vorstellung ist die, dass „weit voneinander entfernt zu sein“ eine sehr starke Eigenschaft
ist, so dass es nur wenige Punkte geben wird. Wenn wir zum Beispiel fordern, dass die
Punkte gegenseitig den Abstand 2 (oder minimal weniger) haben sollen, dann gibt es
höchstens vier Punkte, und diese müssen ziemlich genau in den Ecken liegen.
Nun fordern wir viel weniger; wir untersuchen Punkte, deren gegenseitiger Abstand
größer als 2 (| 1,41) ist. Man könnte vermuten, dass man es schafft, mehr als vier
Punkte mit diesem Abstand im Quadrat unterzubringen. Überraschenderweise ist dies aber
nicht so; dies sagt die nächste Behauptung:
Unter je fünf Punkten, die in einem Quadrat der Seitenlänge 2 liegen, gibt es zwei, die einen Abstand d 2 haben.
Warum ist dies so? Genauer gefragt: Was sind die Kategorien bzw. die Schubfächer?
Wir denken uns das Quadrat der Seitenlänge 2 in natürlicher Weise in vier Teilquadrate
der Seitenlänge 1 eingeteilt.
Bild 1.6 Einteilung in Teilquadrate
Die Punkte eines jeden Teilquadrats fassen wir zu einer Kategorie zusammen; es gibt also
genau vier Kategorien. Da es aber fünf Objekte (die Punkte) gibt, sagt uns das Schubfachprinzip, dass es eine Kategorie mit zwei Objekten gibt. Das heißt: Es gibt ein Teilquadrat,
in dem zwei der fünf Punkte liegen. Da der maximale Abstand in einem Teilquadrat gleich
2 (die Länge der Diagonale) ist, haben diese beiden Punkte einen Abstand d 2 .
Jetzt betrachten wir natürliche Zahlen und deren Teilbarkeit. Das ist ganz einfach: Eine natürliche Zahl ist durch 5 teilbar, wenn sie ein Vielfaches von 5 ist, also kurz gesagt, wenn
sie eine Fünferzahl ist.
Behauptung: Unter je sechs natürlichen Zahlen gibt es stets zwei, deren Differenz durch 5
Beispiel: Wenn die Zahlen 8, 17, 21, 25, 33, 49 sind, so ergibt sich, dass 33 – 8 = 25
durch 5 teilbar ist.
Nun beweisen wir die Richtigkeit der obigen Aussage. Um das Schubfachprinzip anwenden zu können, müssen wir wissen, was die Objekte und was die Kategorien sind. Die Objekte sind die 6 natürlichen Zahlen. Diese werden nun in fünf Kategorien K0, K1, ..., K4
x In K0 kommen diejenigen Zahlen, die Vielfache von 5 sind,
x in K1 kommen diejenigen Zahlen, die bei Division durch 5 den Rest 1 ergeben,
x in K2 kommen diejenigen Zahlen, die bei Division durch 5 den Rest 2 ergeben,
x in K3 kommen diejenigen Zahlen, die bei Division durch 5 den Rest 3 ergeben,
x in K4 kommen diejenigen Zahlen, die bei Division durch 5 den Rest 4 ergeben.
Da jede Zahl bei Division durch 5 den Rest 0, 1, 2, 3 oder 4 ergibt, ist jede Zahl in
mindestens einer Kategorie enthalten.
Das Schubfachprinzip sagt jetzt, dass es eine Kategorie mit zwei Objekten gibt. Das bedeutet: Es gibt zwei Zahlen, die bei Division durch 5 denselben Rest ergeben. Wenn wir
die Differenz dieser Zahlen bilden, „hebt sich der Rest weg“. Das heißt: Wenn man die
Differenz dieser Zahlen durch 5 teilt, geht diese ohne Rest auf. Mit anderen Worten: Die
Differenz ist durch 5 teilbar.
Wir nennen zwei ganze Zahlen teilerfremd, wenn ihr größter gemeinsamer Teiler 1 ist.
Zum Beispiel sind 7 und 12 teilerfremd, da sie keine gemeinsamen Teiler außer 1 haben; 8 und 12 dagegen sind nicht teilerfremd, da 4 ein gemeinsamer Teiler ist.
Behauptung: Unter je n+1 Zahlen der Menge {1, 2, 3, ..., 2n} gibt es stets zwei teilerfremde.
Warum? Unter je n+1 Zahlen der Menge {1, 2, 3, ..., 2n} gibt es stets zwei aufeinanderfolgende; diese Zahlen sind sicher teilerfremd.
Behauptung: Unter je n+1 Zahlen der Menge {1, 2, 3, ..., 2n} gibt es stets zwei Zahlen,
von denen die eine die andere teilt.
Beweis. Seien a0, a1, ..., an die gewählten n+1 Zahlen. Wir schreiben jede dieser Zahlen
als Produkt einer Zweierpotenz und einer ungeraden Zahl; das heißt
ai = 2 e i  ui,
wobei ei eine natürliche Zahl ist (ei darf Null sein) und ui ungerade ist. (Zum Beispiel:
Wenn ai ungerade ist, dann ist ei = 0 und ui = ai. Im Fall ai = 12 ist ei = 2 und ui =
Dann sind die ui ungerade Zahlen zwischen 1 und 2n. Da es in diesem Intervall nur
n ungerade Zahlen gibt, muss es ein i und ein j (i z j) geben mit ui = uj. Dann ist
ai = 2 e i  ui und aj = 2 j  uj.
Dann teilt die Zahl mit der kleineren Zweierpotenz die mit der größeren.
Verallgemeinertes Schubfachprinzip. Seien m Objekte in n Kategorien eingeteilt.
Wenn m > rn ist, so enthält mindestens eine Kategorie mindestens r+1 Objekte.
Beweis. Wenn jede Kategorie höchstens r Objekte enthalten würde, so gäbe es insgesamt
höchstens rn Objekte.
Bemerkung. Das einfache Schubfachprinzip aus 1.1 ergibt sich, wenn man r = 1 setzt.
Unendliches Schubfachprinzip. Wenn man eine unendliche Menge in endlich viele Kategorien einteilt, gibt es mindestens eine Kategorie, die unendlich viele Elemente enthält.
Auch hier ist der Beweis klar: Wenn jede der endlich vielen Kategorien nur endlich viele
Objekte enthalten würde, dann gäbe es insgesamt auch nur endlich viele Objekte.
Beispiel: Sei n t 2 irgendeine natürliche Zahl. Wir betrachten die „Restklassen” K0, K1,
K2, ..., Kn–1 bezüglich n. Das heißt: K0 ist die Menge der natürlichen Zahlen, die Vielfache von n sind; K1 ist die Menge der natürlichen Zahlen, die bei Division durch n den
Rest 1 ergeben, usw. Dann gibt es mindestens eine Restklasse, die unendlich viele
Primzahlen enthält.
Warum? Es gibt unendlich viele Primzahlen (siehe Satz 5.6.2).
Bemerkung. Es gilt ein viel stärkerer Satz: Wenn eine Restklasse Ki die Eigenschaft hat,
dass i und n den größten gemeinsamen Teiler 1 haben, dann enthält Ki unendlich viele Primzahlen. Dieser Satz wurde von R. Dedekind (1831 – 1916) bewiesen.
Zum Beispiel enthalten also K1 und Kn–1 in jedem Fall unendlich viele Primzahlen.
In der Sockenkiste von Professor Mathemix befinden sich 10 graue, 10 braune und
10 schwarze Socken. Der Professor nimmt eine Reihe von Socken heraus. Wie viele
muss er herausnehmen, um
Machen Sie sich mit dem Schubfachprinzip klar: Unter je zehn Punkten in einem
Quadrat der Seitenlänge 3 gibt es stets zwei, deren Abstand d 2 ist.
Zeigen Sie: Unter je neun Punkten in einem Würfel der Kantenlänge 2 gibt es stets
zwei, deren Abstand d 3 ist.
Unter je hmhm Punkten in einem Würfel der Kantenlänge 3 gibt es stets zwei, deren
Abstand d 3 ist. Was ist hmhm?
Zeigen Sie: Unter je fünf Punkten in einem gleichseitigen Dreieck der Seitenlänge 1
gibt es stets zwei, deren Abstand höchstens ½ ist.
Zeigen Sie: Unter je 17 Punkten in einem gleichseitigen Dreieck der Seitenlänge 1
gibt es stets zwei, deren Abstand höchstens hmhm ist. Was ist hmhm?
Bei einer Party begrüßen sich die Personen, indem sie miteinander anstoßen. Das dauert seine Zeit. Zeigen Sie: In jedem Augenblick gibt es zwei Personen, die mit der
gleichen Anzahl von Personen angestoßen haben.
Wie viele Springer kann man auf einem 8u8-Schachbrett so aufstellen, dass sie sich
gegenseitig nicht bedrohen?
Auf einem 8u8-Schachbrett befinden sich 23 Springer. Zeigen Sie, dass man stets 12
so auswählen kann, dass sie sich gegenseitig nicht bedrohen.
10 Zeigen Sie: Unter je elf natürlichen Zahlen gibt es stets drei, so dass die Differenz von
je zweien durch 5 teilbar ist.
11 Wie viele Möglichkeiten gibt es, auf einem 8u8-Schachbrett acht Türme so aufzustellen, dass sie sich gegenseitig nicht bedrohen?
12 Zeigen Sie: Unter je fünf Punkten der Ebene mit ganzzahligen Koordinaten gibt es
zwei, deren Mittelpunkt ebenfalls ganzzahlige Koordinaten hat.
13 Unter je hmhm Punkten im 3-dimensionalen Raum mit ganzzahligen Koordinaten gibt
es zwei, deren Mittelpunkt ebenfalls ganzzahlige Koordinaten hat. Was ist hmhm?
14 Zeigen Sie: Unter je zehn Punkten der Ebene mit ganzzahligen Koordinaten gibt es
zwei, bei denen der Punkt, der ihre Strecke im Verhältnis 2:1 teilt, ebenfalls ganzzahlige Koordinaten hat.
15 Machen Sie sich klar: Unter je neun natürlichen Zahlen gibt es mindestens zwei, deren
Differenz durch 8 teilbar ist.
16 Gilt auch folgendes: Unter je 1000 natürlichen Zahlen gibt es zwei, deren Differenz
durch 8 teilbar ist?
17 Verallgemeinern Sie Aufgabe 15, indem Sie „8“ durch „n“ ersetzen.
18 Gilt auch die folgende Aussage? Unter je sechs natürlichen Zahlen gibt es zwei, deren
Summe durch 5 teilbar ist. [Sie müssen entweder diese Aussage beweisen oder ein
Gegenbeispiel finden.]
N. L. Biggs: Discrete Mathematics. Oxford University Press, Oxford 1996.
P. J. Cameron: Combinatorics: Topics, Techniques, Algorithms. Cambridge University
Press, Cambridge 1994.
J. H. van Lint, R. M. Wilson: A Course In Combinatorics. Second Edition. Cambridge University Press, Cambridge 2001.
F. P. Ramsey: On a problem of formal logic. Proc. London Math. Soc. 30 (1930), S. 264 
In der Mathematik werden Probleme oft dadurch gelöst, dass man eine zusätzliche Struktur
einführt. Diese Struktur hat in der Regel nur eine Hilfsfunktion, sie kommt weder in der
Voraussetzung noch in der Behauptung vor, sondern dient nur für den Beweis. In vielen
Fällen kann man eine solche Struktur durch eine Färbung realisieren. Durch eine geschickte Färbung wird dabei ein Problem gelöst, das gar nichts mit Farben zu tun hat. Mit dieser
Methode kann man sowohl Existenz- wie auch Nichtexistenzsätze beweisen.
Wir stellen uns ein ganz normales Schachbrett vor, auf dem wir allerdings nicht Schach
spielen werden. Wir betrachten vielmehr nur das Brett.
Neben dem Schachbrett haben wir noch eine Menge von 2u1-Dominosteinen, von denen jeder genau zwei benachbarte Felder des Schachbretts überdecken kann. Auch bei den
Dominosteinen kommt es uns nicht darauf an, was darauf steht, sondern nur auf die Form.
Bild 2.1 Ein Schachbrett
Wir stellen drei scheinbar ganz ähnliche, in Wirklichkeit aber völlig verschiedene Fragen,
von denen die letzte den eigentlichen Pfiff enthält.
Einfache Frage: Kann man die Felder des Schachbretts lückenlos mit Dominosteinen so
überdecken, dass sich keine zwei Dominosteine überlappen?
Natürlich, es gibt Tausende von Möglichkeiten, das zu tun; die einfachste ist die folgende:
Bild 2.2 Eine mögliche Überdeckung des Schachbretts
Dumme Frage: Nun schneiden wir ein Feld des Schachbretts heraus, zum Beispiel ein
Eckfeld. Kann man auch dieses „verstümmelte Schachbrett“ lückenlos und überschneidungsfrei so mit Dominosteinen überdecken, dass kein Stein „übersteht“?
Bild 2.3 Das verstümmelte Schachbrett
Zur Antwort müssen wir uns überlegen, wie viele Felder unser verstümmeltes Schachbrett
hat. Das Originalschachbrett hat 88 = 64 Felder, also hat das verstümmelte genau 63
Felder. Wie viele Dominosteine bräuchten wir zur Überdeckung? Da 31 Steine nur 62
Felder überdecken, reichen 31 nicht; 32 Steine überdecken aber bereits 64 Felder, also
sind 32 Steine zuviel.
Also ist die Antwort „nein“: Es gibt keine Überdeckung des verstümmelten Schachbretts. Blöd!
Interessante Frage: Jetzt schneiden wir zwei Felder aus dem Schachbrett aus, und zwar
gegenüberliegende Eckfelder. Kann man dieses „doppelt verstümmelte“ Schachbrett lückenlos und überschneidungsfrei mit Dominosteinen überdecken?
Bild 2.4 Das doppelt verstümmelte Schachbrett
Auf den ersten Blick scheint nichts dagegen zu sprechen. Wir haben 62 Felder, und diese
müssten mit 31 Steinen überdeckt werden.
Wohl jeder wird so anfangen, dass in die unterste Reihe drei Steine gelegt und einer
senkrecht gestellt wird. Aber das geht nicht gut:
Bild 2.5 Ein Überdeckungsversuch
Man kann zwar noch problemlos drei Steine unterbringen, aber man müsste vier Steine
Auch andere Versuche schlagen fehl. Vielleicht geht es ja wirklich nicht? Aber wie
können wir uns überzeugen, dass es nicht geht? Mathematisch gesprochen: Wie können
wir beweisen, dass es keine Lösung gibt? Wir müssten beweisen, dass keine der möglichen
tausend und abertausend Ansätze zum Ziel führt! Aber kein Mensch wird alle diese
Möglichkeiten auflisten und ausprobieren!
Wir müssen alle diese unübersehbar vielen Fälle auf einen Schlag erledigen! Aber wie?
Hier ist die Idee: Bislang haben wir nur ganz wenige Eigenschaften des Schachbretts
benutzt, eigentlich nur seine äußeren Abmessungen. Jeder weiß aber, dass ein Schachbrett
auch gefärbt ist, seine Felder sind abwechselnd schwarz und weiß gefärbt. Die Idee ist,
diese Färbung zu betrachten:
Bild 2.6 Die Färbung des Schachbretts
Wenn unsere Idee Erfolg haben soll, dann müssen wir zwei Dinge mit Hilfe dieser Färbung
untersuchen: Einerseits das Schachbrett und andererseits die Dominosteine.
Das Schachbrett: Wie viele schwarze und wie viele weiße Felder hat das
Originalschachbrett? Von jeder Sorte gleich viele, also 32. Man kann sich das auf viele
Weisen klar machen, zum Beispiel dadurch, dass man bemerkt, dass in jeder Zeile genau
vier weiße und vier schwarze Felder sind.
Wie viele schwarze und wie viele weiße Felder hat das „doppelt verstümmelte“
Schachbrett? Dazu müssen wir einfach überlegen, welche Felder entfernt wurden. Die entfernten Felder sind gegenüberliegende Eckfelder, und diese haben immer die gleiche Farbe. In unserem Beispiel haben wir zwei schwarze Felder entfernt. Deshalb hat das „doppelt
verstümmelte“ Schachbrett genau so viele weiße Felder wie das Originalschachbrett, aber
zwei schwarze Felder weniger. Im Klartext: Das „doppelt verstümmelte“ Schachbrett hat
genau 32 weiße und nur 30 schwarze Felder.
Die Dominosteine: Jeder Dominostein auf dem Schachbrett überdeckt zwei benachbarte
Felder, also zwei Felder verschiedener Farbe, ein weißes und ein schwarzes. Das bedeutet:
Unabhängig davon, wie viele Dominosteine auf dem Schachbrett liegen, diese überdecken
immer gleich viele weiße wie schwarze Felder! Ein Dominostein überdeckt ein weißes und
ein schwarzes Feld, dreißig Dominosteine bedecken 30 weiße und 30 schwarze Felder.
Keines mehr und keines weniger. Exakt.
Zusammen erhalten wir folgende überraschende Erkenntnis: Das „doppelt verstümmelte“ Schachbrett kann mit Dominosteinen nicht lückenlos überdeckt werden! Denn dazu
müssten wir 32 weiße und 30 schwarze Felder überdecken. Jedes Arrangement von Dominosteinen erfasst aber gleich viele weiße wie schwarze Felder. Wenn wir 30 Dominosteine verwenden, haben wir alle schwarzen Felder besetzt aber zwei weiße sind noch leer.
Diese können nie mit einem Dominostein überdeckt werden.
Anstelle des normalen Schachbretts betrachten wir nun ein „Schachbrett“ beliebiger Größe, es muss auch nicht quadratisch sein, sondern darf ein Rechteck beliebiger Größe sein.
Ein mun-Schachbrett ist ein Schachbrett mit m Zeilen und n Spalten; es hat mn Felder. In dieser Sprechweise ist das normale Schachbrett ein „8u8-Schachbrett“.
Wir fragen uns, wann ein solches Schachbrett mit Dominosteinen überdeckt werden
kann, wobei wir uns jetzt nicht nur die normalen 2u1-Dominosteine, sondern allgemein
au1-Dominosteine vorstellen. Diese bestehen aus einer Reihe von a aneinandergefügten
Eine Aussage ist einfach einzusehen:
2.2.1 Satz. Wenn m oder n ein Vielfaches von a ist, dann kann man das munSchachbrett lückenlos mit au1-Dominosteinen überdecken.
Beweis. Wenn die Anzahl m der Reihen ein Vielfaches von a ist, dann kann man sogar
jede Spalte mit au1-Dominosteinen ausfüllen. Indem man jede Spalte auffüllt, erhält man
eine (ziemlich langweilige, aber immerhin!) Überdeckung des gesamten Schachbretts. 
Die Frage ist, ob auch die Umkehrung gilt, ob also aus der Tatsache, dass ein munSchachbrett lückenlos durch au1-Dominosteine überdeckt werden kann, schon folgt, dass
m oder n ein Vielfaches von a ist. Das würde bedeuten, dass man eine Überdeckung nur
dann hinbekommt, wenn es auch die langweilige Überdeckung gibt.
Ein Fall ist einfach: Wenn a eine Primzahl ist, dann gilt die Umkehrung. (Warum? Sei
z die Anzahl der benötigten Steine. Da das mun-Schachbrett genau mn Felder hat und
jeder Stein genau a davon überdeckt, muss za = mn sein. Also teilt a das Produkt mn.
Da a eine Primzahl ist, muss a also einen der Faktoren m oder n teilen. Daher ist m
oder n ein Vielfaches von a.)
Der erste offene Fall ist daher a = 4 und m = n = 6. Die Frage lautet: Kann man ein 6u6Schachbrett mit 4u1-Dominosteinen überdecken? Die Antwort kann man durch systematisches Probieren erhalten. Man nimmt an, es geht. Dann muss einer der Steine ein Eckfeld
überdecken. Dann überlegt man sich sukzessive, wie die anderen Steine liegen müssen und
sieht dann sehr schnell, dass es nicht geht. (Siehe Übungsaufgabe 1.)
Die Umkehrung gilt aber allgemein:
2.2.2 Satz. Wenn man das mun-Schachbrett lückenlos mit au1-Dominosteinen überdecken
kann, dann ist eine der Zahlen m oder n ein Vielfaches von a.
Beweis. Wir färben jetzt das Schachbrett nicht nur mit 2, sondern mit a Farben; wir bezeichnen diese mathematisch nüchtern mit 1, 2, 3, ..., a.
Wir färben das Schachbrett damit auf die einfachste Art und Weise: Wir beginnen links
oben mit der Farbe 1 und machen dann nach rechts und nach unten in der Reihenfolge der
Farben weiter: 1, 2, 3, ..., a, 1, 2, ...
a1
Bild 2.7 Eine Färbung mit a Farben
Wir beobachten, dass jeder au1-Dominostein jeweils ein Feld jeder Farbe überdeckt. Das
bedeutet: Wenn das Schachbrett vollständig mit au1-Dominosteinen überdeckt werden
kann, dann muss es von jeder Farbe gleich viele Felder geben.
Sei m = ha + b die Anzahl der Zeilen und n = ka + c die Anzahl der Spalten; dabei
sind b und c Zahlen zwischen 0 und a–1. Wenn b = 0 oder c = 0 ist, gilt unsere Behauptung. Deshalb nehmen wir b z 0 und c z 0 an.
Zunächst stellen wir fest, dass in den ersten ka Spalten jede Farbe gleichhäufig vorkommt (denn jede Farbe kommt in den ersten ka Zellen jeder Zeile genau k mal vor).
Nun betrachten wir die restlichen c Spalten. In diesen kommt in den ersten ha Zeilen jede Farbe gleichhäufig vor (siehe Abbildung 2.8).
n Spalten
ha
ka
Bild 2.8 Aufteilung des mun-Schachbretts
Es bleibt ein Rechteck in der rechten unteren Ecke zu untersuchen, das b Zeilen und c
Spalten hat. Wir können annehmen, dass c t b ist.
Behauptung: In diesem Rechteck kommt die Farbe c häufiger vor als die Farbe a.
Da c < a ist, kommt in der ersten Zeile dieses Rechtecks die Farbe a nicht vor und in
jeder Zeile tritt jede Farbe höchstens einmal auf. Außerdem kommt in jeder Zeile genau
einmal die Farbe c vor. Insgesamt folgt, dass die Farbe c häufiger vorkommt als die Farbe a.
Bild 2.9 Das Rechteck rechts unten
Also kommen nicht alle Farben gleich häufig vor, und damit ist im Fall b z 0 und c z 0
keine Überdeckung möglich.
2.2.3 Satz. Ein mun-Schachbrett sei lückenlos durch eine Mischung aus 1u4- und 2u2Steinen überdeckt. Nun entfernt man einen 1u4-Dominostein und fügt einen 2u2-Stein hinzu. Behauptung: Mit diesem Set kann man das Schachbrett nicht überdecken!
Warum geht das nicht? Wir färben das Schachbrett mit den Farben 1, 2, 3, 4 wie im vorigen Satz. Das heißt, wir beginnen links oben mit der 1 und führen die Färbung dann nach
rechts und unten in zyklischer Reihenfolge 1, 2, 3, 4, 1, 2, 3, 4, ... fort.
Jeder 1u4-Dominostein überdeckt alle vier Farben, während ein 2u2-Stein zwei Felder
der gleichen Farbe überdeckt und dafür eine Farbe gar nicht enthält. Daher kann man keinen 1u4-Dominostein durch einen 2u2-Stein ersetzen.
Wir betrachten wieder „Schachbretter“ beliebiger Größe, und auch bei der Färbung lassen
wir jede mögliche Freiheit zu. Die einzige Forderung soll sein, dass jedes Feld entweder
schwarz oder weiß gefärbt ist – sonst gibt es keine Regeln.
Wir untersuchen jetzt also Strukturen wie die folgenden:
Bild 2.10 Ein „Schachbrett“
Wir stellen uns folgende Frage: Können wir ein Rechteck finden, dessen Eckfelder alle mit
der gleichen Farbe gefärbt sind? Ein solches Rechteck nennen wir monochromatisch
(„einfarbig“). Im obigen „Schachbrett“ gibt es viele monochromatische Rechtecke; zwei
davon sind im Folgenden zu sehen:
Bild 2.11 Monochromatische Rechtecke
Wir stellen jetzt aber eine viel allgemeinere und prinzipiell viel schwierigere Frage: Kann
man in jedem, noch so wild gefärbten Schachbrett wenigstens ein monochromatisches
Rechteck finden?
Die Antwort darauf ist „nein“, und das sieht man an folgendem Schachbrett:
Bild 2.12 Keine monochromatischen Rechtecke
In diesem Schachbrett wird kein Mensch ein monochromatisches Rechteck entdecken! Also ist die Antwort auf obige Frage „nein“? Nein: Die Antwort ist fast immer „ja“! Genauer
gesagt gilt der folgende Satz:
2.3.1 Satz. Hat das Schachbrett mindestens die Ausmaße 3u7, so gibt es immer ein monochromatisches Rechteck.
Das bedeutet: Wenn das Brett genügend groß ist, so kann sich das verrückteste Gehirn eine
noch so verrückte Färbung ausdenken – wir Mathematiker können uns ruhig und gelassen
zurücklehnen in der Gewissheit: Wir wissen, dass es ein monochromatisches Rechteck
Aber zuvor müssen wir uns davon überzeugen. Dazu stellen wir uns vor: Was wäre,
wenn es kein monochromatisches Rechteck gäbe? Dazu betrachten wir einen Streifen der
Höhe 3 des Feldes und studieren die Möglichkeiten für diese Spalten.
Theoretisch könnte es die folgenden acht verschiedenen Spalten geben:
Bild 2.13 Alle acht verschiedenen Spalten
Nun untersuchen wir die möglichen Kombinationen dieser Spalten genauer.
1. Feststellung: Keine Spalte kommt doppelt vor.
Denn wenn eine dieser Spalten zweimal auf dem Feld vorkommen würde, so gäbe es ein
monochromatisches Rechteck. (In jeder Spalte kommen entweder zwei weiße oder zwei
schwarze Kästchen vor; diese bilden die Ecken eines monochromatischen Rechtecks.)
2. Feststellung: Die ganz schwarze Spalte ist nicht vorhanden.
Denn wenn sie vorhanden wäre, dürfte keine andere Spalte mit zwei schwarzen Feldern
vorkommen – sonst hätten wir ein monochromatisches Rechteck; also könnte es höchstens
fünf Spalten geben, es gibt aber mindestens sieben.
Genauso sieht man:
3. Feststellung: Auch die makellos weiße Spalte taucht nicht auf.
Zusammen ergibt sich: Das Schachbrett kann aus höchstens sechs Spalten bestehen, nämlich aus denen, die mindestens ein weißes und mindestens ein schwarzes Feld haben.
Das bedeutet umgekehrt: Wenn das Feld mindestens sieben Spalten hat, so gibt es ein
monochromatisches Rechteck.
Wir spielen folgendes Zweipersonenspiel auf kariertem Papier. Die Spieler spielen abwechselnd, indem der eine ein Feld mit einem Kreuz, der andere mit einem Kringel versieht. Wer zuerst eine vorgegebene Figur mit seinem Zeichen ausgefüllt hat, hat gewonnen.
Wir betrachten hier als Zielfigur das 2u2-Quadrat. Es wird sich herausstellen, dass es
hier keine Gewinnstrategie gibt, genauer gesagt gilt: Der zweite Spieler hat eine Strategie,
einen Sieg des ersten Spielers zu verhindern!
Wie geht das? Der zweite Spieler muss auf jeden Zug des ersten die richtige Antwort
haben! Wie soll diese aussehen?
Der Trick besteht darin, dass der erste Spieler sich das Spielfeld auf folgende Weise mit
Dominosteinen ausgefüllt vorstellt:
Bild 2.14 Dominosteine bedecken das Spielfeld
Die Strategie des zweiten Spielers ist nun einfach die folgende: Wenn immer der erste
Spieler sein Kreuz in ein Kästchen malt, so macht er seinen Kringel in das andere Feld des
Dominosteins, der durch das Kreuz ausgewählt wurde.
Das bedeutet, dass der erste Spieler niemals beide Felder eines Dominosteins mit seinem Zeichen versehen kann. Daher kann der erste Spieler nie gewinnen: Denn jedes 2u2Quadrat enthält bestimmt einen ganzen Dominostein – und dieser Dominostein enthält sicher keine zwei Kreuze! Also kann der erste Spieler nicht gewinnen.
In Museen gibt es immer ein Problem, das Problem der Aufsicht. Jeder Winkel muss
ständig überwacht werden, deshalb braucht man viele Aufseher. Aber schon aus Kostengründen möchte man mit so wenig Aufsehern wie möglich auskommen.
Das Problem lautet also: Welche Zahl von Aufsehern braucht man, um ein beliebig geformtes Museum lückenlos überwachen zu können?
Was ist ein Museum? Wir betrachten dazu folgendes mathematische Modell: Wir stellen uns vor, dass das Museum nur eine Ebene ausfüllt und dass es nicht auf zwei oder mehr
Gebäude verteilt ist (es ist „zusammenhängend”). Ansonsten gibt es keine Einschränkung
für die Architektur. Mit anderen Worten: Das Museum besteht aus dem Innern eines beliebigen Vielecks.
Bild 2.15 Ein Museum
Auf den ersten Blick ist nicht klar, dass es überhaupt eine vernünftige Antwort gibt. Wenn
es eine gibt, erwarten wir, dass sie von der Anzahl n der Ecken abhängt: Je mehr Ecken
und Kanten das Museum hat, desto mehr Aufseher benötigt man. Die präzise Antwort ist
2.5.1 Satz. Ein Museum, das ein n-Eck ist, kann stets mit n/3 Aufsehern überwacht werden.
Beweis. Der Beweis erfolgt in drei Schritten.
1. Schritt: Wir triangulieren den Grundriss. Das bedeutet: Wir ziehen virtuelle Wände
ein, so dass jeder Raum die Form eines Dreiecks hat.
2. Schritt: Wir färben die Ecken jetzt so mit drei Farben, dass die Ecken jedes Dreiecks
mit allen drei Farben gefärbt sind. Man kann zeigen, dass das immer funktioniert (siehe
Kapitel 3, Übungsaufgabe 7). Das Beweismittel ist die sogenannte „vollständige Induktion“, die im nächsten Kapitel vorgestellt wird.
3. Schritt: Wir wählen eine Farbe aus und stellen an die Ecken dieser Farbe je einen
Aufseher. Diese Aufseher überblicken insgesamt das ganze Museum, da sie je jeden (virtuellen) dreieckigen Raum überblicken.
Bild 2.16 Triangulierung und Färbung
Wenn wir die Farbe wählen, die am seltensten vorkommt (also höchstens n/3 mal), erhalten wir eine Lösung des Problems mit höchstens n/3 Aufsehern.
Nun färben wir Punkte der Ebene. Nicht nur einige wenige, sondern viele, meistens alle.
Im ersten Satz färben wir nur die Gitterpunkte. Dies sind diejenigen Punkte (x, y) im
kartesischen Koordinatensystem, die ganzzahlige Koordinaten x, y haben. Man kann sich
die Gitterpunkte auch als die Schnittpunkte der Linien auf einem (unendlich großen) karierten Papier vorstellen.
2.6.1 Satz. Die Gitterpunkte der Ebene seien mit zwei Farben gefärbt. Dann gibt es ein
Rechteck, dessen Ecken alle die gleiche Farbe haben.
Beweis. Wir betrachten einen Ausschnitt von 3 Reihen und 9 Spalten aus dem Gitter und
zeigen, dass es schon in diesem Ausschnitt ein Rechteck mit gleichfarbigen Ecken gibt.
Jede Spalte dieses Ausschnitts hat drei Gitterpunkte. Drei Punkte können auf genau 8
verschiedene Arten gefärbt werden (www, wws, wsw, sww, ssw, sws, wss, sss).
Da es 9 Spalten gibt, gibt es mindestens zwei Spalten mit derselben Farbanordnung.
In jeder Farbanordnung gibt es aber zwei Punkte, die gleich gefärbt sind.
Man nehme diese Punkte in den beiden Spalten. Diese bilden ein Rechteck mit gleichfarbigen Ecken.
2.6.2 Satz. Die Punkte der Ebene seien mit zwei Farben gefärbt. Dann gibt es ein gleichseitiges Dreieck, dessen Ecken alle die gleiche Farbe haben.
Beweis. Die Farben seien schwarz und weiß. Wir betrachten ein gleichseitiges Sechseck
zusammen mit seinem Mittelpunkt. Dies ergibt eine Figur aus sechs gleichseitigen Dreiecken.
Bild 2.17 Regelmäßiges Sechseck
Der Mittelpunkt sei weiß gefärbt. Wenn eines der sechs Dreiecke noch zwei weiße Ecken
hat, ist die Behauptung gezeigt.
Also habe jedes der sechs Dreiecke „außen” eine weiße und eine schwarze Ecke. Dann
bilden aber die schwarz und die weiß gefärbten Ecken des Sechsecks jeweils ein gleichseitiges Dreieck.
2.6.3 Satz. Die Punkte der Ebene seien mit drei Farben gefärbt. Dann gibt es zwei Punkte
vom Abstand 1, die die gleiche Farbe haben.
Beweis. Die Farben seien rot, blau und gelb. Angenommen, je zwei Punkte vom Abstand 1
haben verschiedene Farbe.
Wir gehen von einem roten Punkt R aus und betrachten ein gleichseitiges Dreieck
'RBG der Seitenlänge 1. Nach Annahme haben die Punkte R, B, G paarweise verschiedene Farben. Sei B blau und G gelb.
Nun betrachten wir das gleichseitige Dreieck 'BGR’, das von BG aus nach der anderen Seite konstruiert wird.
Bild 2.18 'RBG und 'BGR’
Wieder nach Annahme muss R’ rot gefärbt sein. Sei d der Abstand von R und R’.
Da diese Überlegung für jedes gleichseitige Dreieck der Seitenlänge 1 gilt, das R als
Ecke hat, ergibt sich, dass der Kreis um R mit Radius d ausschließlich aus roten Punkten
Da es auf diesem Kreis sicherlich zwei Punkte vom Abstand 1 gibt, ist der Satz bewiesen.
Zeigen Sie durch elementare Überlegungen, dass man ein 6u6-Schachbrett nicht mit
4u1-Dominosteinen vollständig und überschneidungsfrei überdecken kann.
Zeigen Sie, dass man jedes mun-Schachbrett, bei dem m und n gerade sind, mit
4u1-Dominosteinen und höchstens einem 2u2-Stein überdecken kann.
Ein Springer ist von einem Feld des Schachbretts aus gestartet, hat eine gewisse Anzahl von Zügen gemacht und ist zu seinem Ausgangsfeld zurückgekehrt. Warum ist
die Anzahl seiner Züge eine gerade Zahl?
Kann man durch eine Reihe von Zügen mit einem Turm von einem Eckfeld des
Schachbretts in die gegenüberliegende Ecke gelangen und dabei jedes Feld des
Schachbretts genau einmal berühren?
Machen Sie sich klar, dass die folgenden Figuren („Tetrisfiguren”, auch „Tetrominos“
genannt) alle zusammenhängenden ebenen Figuren sind, die man aus vier gleich großen Quadraten bilden kann.
Bild 2.19 Alle Tetrisfiguren
Bestimmen Sie alle zusammenhängenden ebenen Figuren („Pentominos”), die man
aus fünf gleich großen Quadraten bilden kann. (Unterscheiden Sie, wenn nötig, zwischen einer Figur und ihrem Spiegelbild!)
Betrachten Sie folgendes Spiel für zwei Personen: Die Spieler einigen sich auf eine
Tetrisfigur, die verschieden vom 2u2-Quadrat ist. Sie machen abwechselnd ihr Zeichen auf ein Feld eines karierten Papiers. Gewonnen hat, wer als erster mit seinem
Zeichen die verabredete Figur erhalten hat. Zeigen Sie: Es gibt eine Strategie, mit der
der erste Spieler 100%-ig gewinnt.
Die Gitterpunkte seien mit drei Farben gefärbt. Gibt es ein Rechteck, dessen Ecken
gleichfarbige Gitterpunkte sind?
A. Engel: Problem-Solving Strategies. Springer-Verlag, Berlin und Heidelberg 1997, Kapitel 2.
A. Engel: Problemlösestrategien. Didaktik der Mathematik 4 (1995), S. 265-275.
M. Gardner: Mathematische Rätsel und Probleme. Verlag Vieweg, Braunschweig und
Wiesbaden 1966.
S. W. Golomb: Checker Boards and Polyominoes. Amer. Math. Monthly 61 (1954), S.
Um Einsicht in eine Struktur oder ein Problem zu gewinnen, wird man in der Regel nicht
nur ein Beispiel betrachten, sondern viele, im Idealfall alle. Das bedeutet, dass man sich oft
mit einer unendlichen Menge von Objekten herumschlagen muss. Zur Behandlung solcher
Probleme gibt es in der Mathematik ein Hauptwerkzeug, das wir auf Schritt und Tritt benützen werden, nämlich die Induktion, manchmal auch „vollständige“ oder „mathematische“ Induktion genannt.
Das Ziel der vollständigen Induktion ist es also, Beweise von Aussagen führen zu können, die sich auf unendlich viele Objekte beziehen: unendlich viele Zahlen, unendlich viele
Wir formulieren das Prinzip der vollständigen Induktion zunächst abstrakt, um es dann
durch viele Beispiele zu erläutern. Keine Angst vor der abstrakten Formulierung; diese
scheint nur schwierig zu sein, in Wirklichkeit ist sie ganz natürlich.
Prinzip der vollständigen Induktion. Sei A eine Aussage oder eine Eigenschaft, die von
einer natürlichen Zahl n abhängt. Wenn wir diese Abhängigkeit zum Ausdruck bringen
wollen, schreiben wir auch A(n).
Wenn wir wissen, dass folgendes gilt:
(1) Induktionsbasis (Induktionsverankerung): Die Aussage A gilt im Fall n = 1
(das heißt, es gilt A(1)),
(2) Induktionsschritt: Für jede natürliche Zahl n t 1 folgt aus A(n) die Aussage
A(n+1),
dann gilt die Aussage A für alle natürlichen Zahlen t 1.
Die Bedeutung dieses Prinzips liegt darin, dass man, um eine Aussage über unendlich viele
Objekte zu beweisen, nur zwei Aussagen beweisen muss, nämlich die Induktionsbasis und
den Induktionsschritt. Im Induktionsschritt muss man aus A(n) die Aussage A(n+1) folgern; in diesem Zusammenhang nennt man A(n) auch die Induktionsvoraussetzung.
Sehr häufig ist die Induktionsbasis leicht zu beweisen, der Induktionsschritt aber schwieriger.
Man kann sich das Prinzip leicht am Besteigen einer Leiter klar machen: Wenn es (1)
gelingt, auf die erste Sprosse einer Leiter zu gelangen, und es (2) möglich ist, von jeder
Sprosse auf die nächste zu steigen, dann kann man alle Sprossen der Leiter erklimmen.
Das Betreten der ersten Sprosse entspricht der Induktionsbasis, das Fortschreiten von
einer beliebigen Sprosse auf die nächste ist ein Bild für den Induktionsschritt.
Die hinter diesem Prinzip stehende „Philosophie“ ist die, dass man in objektiv kontrollierbarer Weise über eine Unendlichkeit („alle“ natürlichen Zahlen) sprechen kann. Die
Bedeutung dieses Prinzips, das zwischen 1860 und 1920 unter anderem von Moritz Pasch
und Giuseppe Peano entdeckt wurde, kann gar nicht überschätzt werden.
Wir versuchen nun, dieses Prinzip anzuwenden. Zuerst machen wir uns klar, was eine
„Aussage“, die von einer natürlichen Zahl n abhängt, sein kann. In der Mathematik versteht man unter einer Aussage einen Ausdruck, der entweder wahr oder falsch ist. Dazu
A(n): 4n ist eine gerade Zahl.
A(n): n2 ist eine gerade Zahl.
A(n): n ist eine Primzahl.
A(n): Die Anzahl der Sitzordnungen von n Studierenden auf n Stühlen ist n!
(:= n  (n–1)  ...  2  1, sprich „n Fakultät“).
A(n): Unter n Personen, gibt es immer zwei, die am selben Tag Geburtstag haben.
A(n): n geradlinige Straßen haben höchstens n Kreuzungen.
A(n): Wenn n Computer zu je zweien durch eine Leitung verbunden werden, so braucht
man genau n(n–1)/2 Leitungen.
In diesem Abschnitt beweisen wir einige einfache Aussagen, die im Wesentlichen zum
Üben der vollständigen Induktion dienen.
Häufig wird das Prinzip der vollständigen Induktion darauf angewandt, unendliche
Summen zu berechnen. Wir behandeln einige Beispiele.
Die erste Aufgabe besteht darin, die ersten n Zahlen aufzuaddieren. Es geht also darum, die Summe
1 + 2 + 3 + ... + (n–1) + n
zu berechnen. Mit Hilfe von vollständiger Induktion ist das nicht schwer. Allerdings muss
man dabei, wie immer bei Induktionsbeweisen, schon wissen, was herauskommt. Hier ist
3.2.1 Satz. Für jede natürliche Zahl n t 1 gilt:
n(n  1)
In Worten: Die Summe der ersten n positiven ganzen Zahlen ist gleich (n+1)n/2.
Eine Konsequenz dieses Satzes ist, dass man diese Summe ganz einfach ausrechnen kann
und kaum Rechenfehler passieren können.
Bemerkung. Die Zahlen der Form (n+1)n/2, also die Zahlen 1, 3, 6, 10, 15, ... heißen
Dreieckszahlen. Man kann den Satz also auch so ausdrücken: Die Summe der ersten n
positiven ganzen Zahlen ist gleich der n-ten Dreieckszahl.
Bild 3.1 Die ersten fünf Dreieckszahlen
Beweis durch Induktion nach n.
Die Aussage A(n) sei genau die Aussage des Satzes. Sowohl bei der Induktionsbasis als
auch beim Induktionsschritt müssen wir zeigen, dass in der entsprechenden Gleichung die
linke und die rechte Seite übereinstimmen.
Induktionsbasis: Sei n = 1. Dann steht auf der linken Seite nur der Summand 1, und auf
der rechten Seite steht 21/2, also ebenfalls 1. Also gilt die Aussage A(1).
Induktionsschritt: Sei n eine natürliche Zahl t 1, und sei die Aussage richtig für n. Wir
müssen die Aussage A(n+1) beweisen, das heißt, wir müssen die Summe
1 + 2 + 3 + ... + (n–1) + n + (n+1)
berechnen. Um die Induktionsvoraussetzung anwenden zu können, spalten wir diese Summe auf in die ersten n Summanden einerseits und den letzten andererseits. Dann wird die
Sache ganz einfach:
= [1 + 2 + 3 + ... + (n–1) + n] + (n+1)
n(n  1)+2(n + 1)
(nach Induktion)
(n  1)(n  2)
Insgesamt haben wir genau die Gleichung bewiesen, die der Aussage A(n+1) entspricht.
Die Induktionsvoraussetzung wurde beim zweiten Gleichheitszeichen verwendet.
Interessanterweise kann man diese Formel auch ohne Induktion beweisen. Dann braucht
man allerdings einen Trick, eine Idee. Dieser Trick wurde von Gauß gefunden.
Carl Friedrich Gauß (1777  1855) war einer der größten Mathematiker aller Zeiten,
vielleicht sogar der größte. Die folgende Anekdote zeigt, dass sein enormes Talent schon
in der Grundschule offenbar wurde. Um die Schüler zu beschäftigen, hatte der Lehrer den
Schülern die Aufgabe gestellt, die Zahlen von 1 bis 100 aufzusummieren. Statt nun, wie
ganz selbstverständlich für jeden Schüler dieser Altersklasse, der Reihe nach zu rechnen:
1 + 2 = 3, 3 + 3 = 6, 6 + 4 = 10, 10 + 5 = 15 usw., fiel dem jungen Gauß auf, dass in der
Summation 1 + 2 + 3 + ... + 97 + 98 + 99 + 100 jeweils aus zwei Zahlen am Anfang und
am Ende die Zahl 101 zu bilden ist: 1 + 100 = 101, 2 + 99 = 101 usw. Es gibt 50 solche
Paare. Es bleibt also nur eine einfache Multiplikation zu erledigen: 10150 = 5050. Kein
Wunder, dass Gauß nur eine einzige Zahl auf seine Tafel zu schreiben brauchte und die
Lösung im Handumdrehen hatte! (Vgl. zum Beispiel Wußing 1989)
Im Allgemeinen funktioniert dieser Trick wie folgt:
Im folgenden Satz wird nicht die Summe aller ersten n Zahlen sondern die Summe der
ersten n ungeraden Zahlen berechnet.
3.2.2 Satz. Für jede natürliche Zahl n t 1 gilt: 1 + 3 + 5 + ... + (2n–1) = n2. In Worten:
Die Summe der ersten n ungeraden Zahlen ist gleich der n-ten Quadratzahl.
der rechten Seite steht 12, also ebenfalls 1. Somit gilt A(1).
Induktionsschritt: Sei n eine natürliche Zahl mit n t 1, und es gelte A(n). Wir müssen
A(n+1) nachweisen. Wir beginnen wieder mit der linken Seite von A(n+1) und formen
diese so lange um, bis wir die rechte Seite von A(n+1) erhalten:
1 + 3 + 5 + ... + (2n–1) + (2n+1) = [1 + 3 + 5 + ... + (2n–1)] + (2n+1)
= n2 + 2n + 1 = (n+1)2 .
Somit gilt A(n+1), und damit ist die Aussage bewiesen.
Eine überraschende Aussage ist der folgende Satz:
3.2.3 Satz. Für jede natürliche Zahl n t 1 gilt:
13 + 23 + 33 + ... + n3 = (1 + 2 + 3 + ... + n)2.
In Worten: Die Summe der ersten n positiven Kubikzahlen ist gleich dem Quadrat der
Summe der ersten n positiven ganzen Zahlen.
Induktionsbasis: Sei n = 1. Dann steht auf der linken Seite 13 und auf der rechten 12, also
in jedem Fall die Zahl 1. Daher gilt A(1).
A(n+1) nachweisen. Es gilt:
13 + 23 + 33 + ... + n3 + (n+1)3 = [13 + 23 + 33 + ... + n3] + (n+1)3
= (1 + 2 + 3 + ... + n)2 + (n+1)3
n 2 (n  1) 2
(nach 3.2.1)
[n + 2n3 + n2 + 4n3 + 12n2 + 12 n + 4]
(n+1)2(n+2)2 = [1 + 2 + 3 + ... + n + (n+1)]2.
Damit ist die Behauptung des Induktionsschrittes verifiziert. Also gilt der Satz.
Eine der wichtigsten Summenformeln bezieht sich auf die geometrische Reihe.
3.2.4 Satz. (a) Seien a und q reelle Zahlen, q z 1, und sei n eine natürliche Zahl. Dann
a + aq + aq2 + aq3 + ... + aqn = a 
1  q n 1
1 q
Man benutzt für die linke Seite oft auch die Summenschreibweise. Dann lautet die Aussage
¦a q
= a
(b) Für ~q~ < 1 konvergiert die unendliche geometrische Reihe:
¦a  q
   ...
1  12
Bemerkung. Man nennt die Folge aqn eine geometrische Folge. Sie hat die Eigenschaft,
dass sich jedes Glied vom vorhergehenden durch einen konstanten Faktor q unterscheidet.
Dementsprechend bezeichnet man
als geometrische Reihe.
Beweis. Wir beweisen (a) durch Induktion nach n. Dies ist nicht schwer.
Die Induktionsbasis ist einfach: Sei n = 0. Dann steht auf der linken Seite nur a und auf
der rechten a(1–q)/(1–q) = a.
Induktionsschritt: Sei n eine natürliche Zahl mit n t 0, und es gelte die Aussage für die
Zahl n. Wir müssen die Aussage für n+1 nachweisen. Es gilt:
a + aq + aq2 +aq3 + ... + aqn + aqn+1 = (a + aq + aq2 +aq3 + ... + aqn) + aqn+1
+ aqn+1
1  q n 1  q n 1  q n  2
1  q n2
Damit gilt der Induktionsschritt und damit die Behauptung.
(b) ergibt sich aus (a), da für ~q~ < 1 die Folge 1, q, q2, q3, ... eine Nullfolge ist, also
kleiner als jede noch so kleine Zahl wird. Daher konvergiert
Eine andere wichtige Klasse von Aussagen, die man mit vollständiger Induktion zu beweisen pflegt, sind Ungleichungen.
3.2.5 Bernoullische Ungleichung. Für jede natürliche Zahl n und für jede reelle Zahl
x > 1 gilt
(1 + x)n t 1 + nx.
Induktionsbasis: Für n = 0 steht auf beiden Seiten 1, und für n = 1 steht auf beiden Seiten 1 + x. Also gilt in diesen Fällen sogar Gleichheit; insbesondere ist die linke Seite größer oder gleich der rechten Seite.
Induktionsschritt: Sei nun n eine natürliche Zahl mit n t 1, und sei die Behauptung richtig für n. Da 1 + x > 0 ist, folgt damit
(1 + x)n+1 = (1 + x)n  (1 + x)
t (1 + nx)  (1 + x)
= 1 + nx + x + nx2 t 1 + nx + x = 1 + (n+1)x.
(da nx2 t 0)
Damit ist der Induktionsschritt bewiesen, und damit gilt der Satz.
Bemerkung. Die Ungleichung ist nach Jakob Bernoulli (1654 1705) benannt.
3.2.6 Satz. Für jede natürliche Zahl n t 4 gilt
n! > 2n.
Induktionsbasis: Sei n = 4. Dann ist n! = 4! = 4  3  2  1 = 24 und 2n = 24 = 16. Da 24 >
16 ist, gilt die Behauptung in diesem Fall.
Induktionsschritt: Sei n eine natürliche Zahl mit n t 4, und sei die Behauptung richtig für
n. Dann folgt
(n+1)! = (n+1)  n!
t (n+1)  2n
t 2  2n = 2n+1 .
(da n+1 t 5 t 2)
Also ist der Induktionsschritt richtig, und somit folgt die Behauptung.
Abschlussbemerkung. Manche Aussagen A(n), wie etwa die aus Satz 3.2.6, gelten nicht
für alle natürlichen Zahlen, sondern erst ab einer gewissen Zahl n0 (im Beispiel ist
n0 = 4). Auch solche Aussagen kann man mit Induktion beweisen; man formuliert das Induktionsprinzip dazu etwas allgemeiner wie folgt:
Prinzip der vollständigen Induktion (allgemein). Sei A eine Aussage oder eine Eigenschaft, die von einer natürlichen Zahl n abhängt. Wenn wir diese Abhängigkeit zum Ausdruck bringen wollen, schreiben wir auch A(n).
(1) Induktionsbasis (Induktionsverankerung): Die Aussage A gilt im Fall n = n0
(das heißt, es gilt A(n0)),
(2) Induktionsschritt: Für jede natürliche Zahl n t n0 folgt aus A(n) die Aussage
dann gilt die Aussage A für alle natürlichen Zahlen t n0.
Wir stellen uns vor, dass ein Gebiet, etwa ein Erdteil, durch geradlinige Grenzen in Länder
aufgeteilt ist. Die Grenzen sollen dabei so gezogen sein, dass sie den ganzen Erdteil durchqueren.
Wir stellen uns folgende Frage: Wie viele Farben braucht man, um die Länder so zu
färben, dass keine zwei Länder, die ein Stück Grenze gemeinsam haben, gleich gefärbt
Bemerkungen. 1. Länder, die nur einen Punkt gemeinsam haben, dürfen sehr wohl gleich
2. Eine solche Färbung nennt man auch eine zulässige Färbung.
Bild 3.2 Eine Landkarte mit geraden Grenzen
Vermutung: Man kommt bei jeder solchen Landkarte mit zwei Farben (zum Beispiel
schwarz und weiß) aus.
3.3.1 Satz. Jede Landkarte, die dadurch entsteht, dass man einen Erdteil durch Geraden
aufteilt, kann mit zwei Farben so gefärbt werden, dass je zwei Länder, die eine gemeinsame Grenze haben, verschieden gefärbt sind.
Der Beweis erfolgt durch Induktion. Aber für einen Induktionsbeweis brauchen wir immer
eine Aussage, die von einer natürlichen Zahl n abhängt. Was soll n sein? Der naheliegendste Gedanke ist der, dass man mit n die Anzahl der Geraden bezeichnet, die den Erdteil aufteilen. Dann lautet die zu beweisende Aussage so:
A(n): Jede Landkarte, die dadurch entsteht, dass man einen Erdteil durch n Geraden aufteilt, kann mit den Farben schwarz und weiß so gefärbt werden, dass je zwei Länder, die
eine gemeinsame Grenze haben, verschieden gefärbt sind.
Induktionsbasis: Sei n = 1. Wir müssen zeigen, dass jede Landkarte, die durch Aufteilung
mittels nur einer Geraden entsteht, mit zwei Farben gefärbt werden kann. Das ist klar:
Durch Aufteilung mit einer Geraden entstehen ohnedies nur zwei Länder, wenn man diese
mit verschiedenen Farben färbt, so haben angrenzende Länder verschiedene Farben.
Induktionsschritt: Sei n eine natürliche Zahl mit n t 1, und sei die Aussage A(n) richtig.
Wir müssen beweisen, dass auch die Aussage A(n+1) gilt.
Dazu betrachten wir eine beliebige Landkarte, die durch Ziehen von n+1 Geraden g1,
g2, ... , gn+1 entstanden ist. Wir müssen zeigen, dass diese Landkarte zulässig mit den Farben schwarz und weiß gefärbt werden kann.
Wir drehen unsere Landkarte so, dass die Gerade gn+1 waagrecht liegt, und lassen
dann diese Gerade (vorerst) außer Betracht.
Dann haben wir eine Landkarte, die nur durch die n Geraden g1, ... , gn entstanden ist.
Nach Induktionsvoraussetzung ist diese Landkarte also mit den Farben schwarz und weiß
zulässig färbbar!
Das ist aber (noch) nicht das, was wir zeigen müssen; wir müssen die Landkarte mit
n+1 Geraden färben! Dazu fügen wir die (n+1)-te Gerade wieder ein. Dabei entstehen
neue Länder, und sicherlich ist die alte Färbung nicht mehr brauchbar. Wir müssen also die
Länder oder jedenfalls einen Teil der Länder umfärben.
Das ist der eigentliche Trick des Beweises! Wir färben die obere Hälfte der Karte um!
Das bedeutet: Jedes Land, das oberhalb von gn+1 liegt, wechselt die Farbe, wird also
schwarz, wenn es weiß war, und umgekehrt. Die Länder im unteren Teil der Karte behalten
dagegen ihre Farbe.
Bild 3.3 Umfärben der oberen Hälfte der Landkarte
Wir müssen uns jetzt noch klarmachen, dass die so entstandene Färbung zulässig ist, dass
also je zwei benachbarte Länder L und L' verschieden gefärbt sind. Da diese Länder benachbart sind, gibt es eine Gerade gi, mit der die Grenze der Länder gebildet wird. Wir unterscheiden drei Fälle.
1. Fall: Die Grenze von L und L' liegt unterhalb von gn+1. Dann hatten die Länder L,
L' bzw. die Länder, aus denen sie durch Teilung mittels gn+1 hervorgegangen sind, verschiedene Farbe. Da sich in diesem Bereich nichts geändert hat, haben L und L' nach
wie vor verschiedene Farbe.
2. Fall: Die Grenze von L und L' liegt oberhalb von gn+1. In dem Bereich oberhalb von
gn+1 hat sich alles geändert. Da L und L' vorher verschiedene Farben hatten, haben sie
auch jetzt verschiedene Farben.
3. Fall: Die Grenze von L und L' liegt auf gn+1. Dann sind L und L' durch Aufteilung
eines alten Landes L* entstanden: durch Einziehen von gn+1 entstand aus L* ein südli-
ches Land (sagen wir L) und ein nördliches, sagen wir L'. Wenn L* weiß war, bleibt L
weiß, während L' schwarz wird.
Insgesamt haben wir gezeigt, dass je zwei benachbarte Länder verschieden gefärbt sind.
Also ist auch die neue Landkarte zulässig gefärbt.
Bemerkung. Ein berühmtes Problem der Mathematik ist das folgende: Wie viele Farben
braucht man, um eine beliebige Landkarte, also eine Landkarte, die nicht durch Ziehen von
Geraden entsteht, zulässig zu färben? Über 100 Jahre war die Vermutung, dass vier Farben
ausreichen, unbewiesen, bis im Jahre 1976 die Sensation perfekt war: Die Amerikaner W.
Apel und K. Haken konnten mit massivem Computereinsatz den „Vierfarbensatz“ beweisen. Dabei bauten sie entscheidend auf Vorarbeiten des Deutschen H. Heesch auf. (Vgl.
etwa Fritsch 1994.)
Dieses Problem werden wir in Kapitel 8 wieder aufgreifen, wo wir mit Hilfe der Graphentheorie den „Fünffarbensatz“ beweisen werden.
Im Jahre 1202 erschien das Buch Liber Abaci („Das Buch vom Abakus“) des 1175 geborenen Leonardo von Pisa, der auch Fibonacci („Sohn des Bonacci“) genannt wurde. Ein
Hauptziel dieses Buches war es, die Überlegenheit des arabischen Zahlensystems gegenüber dem römischen zu demonstrieren. Berühmt wurde dieses Buch (und mit ihm sein Verfasser) aber durch folgende unscheinbare Aufgabe.
Wir betrachten die Nachkommenschaft eines Kaninchenpaares. Wie jedermann weiß, ist
diese außerordentlich groß. Wir wollen aber ganz genau wissen, wie viele Nachkommen
ein solches Kaninchenpaar hat. Dazu gehen wir von folgenden Annahmen aus:
(i) Jedes Kaninchenpaar wird im Alter von 2 Monaten gebärfähig.
(ii) Jedes Paar bringt von da an regelmäßig in jedem Monat ein neues Paar zur Welt.
(f) Alle Kaninchen leben ewig.
Unter diesen Annahmen lebt im ersten Monat ein Paar; dieses wird im zweiten Monat
gebärfähig und gebiert im dritten Monat ein weiteres Paar. Auch im vierten Monat bringt
das erste Paar ein neues Paar zur Welt, während im fünften Monat beide Paare ein Kaninchenpaar zur Welt bringen. Im fünften Monat gibt es also schon 5 Kaninchenpaare.
Wir können uns das Fortpflanzungsverhalten mit Hilfe von Abbildung 3.4 veranschaulichen.
Mit fn bezeichnen wir die Anzahl der Kaninchenpaare, die im n-ten Monat leben (einschließlich derer, die in diesem Monat geboren werden). Die obige Überlegung zeigt
f1 = 1, f2 = 1, f3 = 2, f4 = 3, f5 = 5, f6 = 8, ...
Und so weiter? Wie geht es denn weiter? Das ist die Frage, mit der wir uns im Folgenden beschäftigen werden.
X: nicht gebärfähig
O: gebärfähig
Bild 3.4 Kaninchenfortpflanzung
3.4.1 Satz. Für alle natürlichen Zahlen n t 1 gilt fn+2 = fn+1 + fn.
Zum Beweis betrachten wir die Situation im (n+1)-ten Monat. Zu diesem Zeitpunkt gibt es
nach Definition genau fn+1 Kaninchenpaare. Von diesen sind genau fn gebärfähig, nämlich diejenigen, die schon im n-ten Monat gelebt haben (genau diese Paare sind jetzt schon
mindestens zwei Monate alt). Im (n+2)-ten Monat bringen also genau fn der fn+1 Paare
ein junges Paar zur Welt. Das bedeutet
fn+2 = Anzahl der Kaninchenpaare im (n+2)-ten Monat
= Anzahl der Kaninchenpaare im (n+1)-ten Monat
+ Anzahl der Kaninchenpaare, die im (n+1)-ten Monat geboren werden
= fn+1 + fn.
Dieser Satz ermöglicht es uns, die Zahlen f1, f2, f3, ... sehr schnell auszurechnen:
Die Zahlen f1, f2, f3, ..., die definiert sind durch
f1 = 1 und f2 = 1
fn+2 = fn+1 + fn für alle natürlichen Zahlen n t 1
heißen die Fibonacci-Zahlen. Die Fibonacci-Zahl
Kaninchenpaare, die im n-ten Monat leben.
ist also die Anzahl der
Fibonacci-Zahlen spielen innerhalb und außerhalb der Mathematik eine entscheidende
Rolle. Insbesondere bei Wachstumsprozessen kommen Fibonacci-Zahlen regelmäßig vor,
etwa bei Tannenzapfen, Ananas, Kakteen, ...
Wir wollen zwei mathematische Sachverhalte über die Fibonacci-Zahlen hier präsentieren und dabei das Prinzip der vollständigen Induktion üben. Die erste Frage ist, ob man die
Fibonacci-Zahlen nur rekursiv (das heißt mit Hilfe der Formel aus 3.4.1) ausrechnen kann
oder ob das auch „direkt“ geht. Wir wünschen uns also eine Formel, in die man n einsetzen kann, und dann ergibt sich automatisch fn. Eine solche Formel ist die sogenannte Binet-Formel (nach J. P. M. Binet, 1786  1856).
3.4.2 Satz (Binet-Formel). Für jede natürliche Zahl n t 1 gilt
1 5
)n  (
Bemerkung. Das Erstaunliche an dieser Formel ist, dass sich für jedes n die Wurzelterme
so wegheben, dass nur eine natürliche Zahl, nämlich fn, stehen bleibt.
Beweis. Wir wenden das Prinzip der vollständigen Induktion an. Die Aussage A(n) ist
Induktionsbasis: Wir müssen die Aussage für n = 1 beweisen, also die Aussage A(1).
Dazu rechnen wir einfach die Formel (also die rechte Seite) für den Fall n = 1 aus:
1 5 1
)1  (
Damit gilt A(1). Wir beweisen nach ähnlichem Muster auch noch A(2):
)2  (
1 2 5  5
1 2 5  5
4 1 f .
Damit gilt auch A(2).
Induktionsschritt: Sei n eine natürliche Zahl mit n t 2, und es mögen die Aussagen A(n)
und A(n–1) gelten. Wir müssen zeigen, dass dann auch A(n+1) gilt. Dazu verwenden
wir die Rekursionsformel fn+1 = fn + fn–1, und wenden sowohl auf fn also auch auf fn–1
die Induktionsvoraussetzung an:
fn+1 = fn + fn–1 =
) n 1  (
) n 1
) n 1  [
 1]  (
 1]
An dieser Stelle passiert ein kleines Wunder, und das gleich zweimal. Wir können nämlich
die eckigen Klammern günstig umformen. Genauer gesagt gilt:
1 5 2
1 5 2
Man sieht beide Formeln sofort ein, wenn man die jeweiligen rechten Seiten ausrechnet.
Was letztlich hinter diesem Wunder steckt, wird dadurch natürlich nicht klar; dieses hängt
aber mit dem „goldenen Schnitt“ zusammen, der in diesen Formeln versteckt ist (siehe unten).
Nun kann uns aber nichts mehr hindern, die obige Gleichungskette weiterzuspinnen:
) n 1[
]2  (
) n 1  (
) n 1
Wenn wir Anfang und Ende der Gleichungskette betrachten, sehen wir, dass damit die
Aussage A(n+1) bewiesen ist.
Nach dem Prinzip der vollständigen Induktion gilt also die Aussage A für alle natürlichen Zahlen.
Vor der nächsten Eigenschaft der Fibonacci-Zahlen machen wir uns einen mathematischen
Zaubertrick klar – allerdings einen unfairen. Wir zerschneiden ein Quadrat der Seitenlänge
8 + 5 = 13 wie angegeben in vier Teile. Diese setzen wir zu einem Rechteck mit den
Seitenlängen 8 und 21 wieder zusammen.
Bild 3.5 Zauberei?
Wir haben also aus einem Quadrat mit einem Flächeninhalt von 1313 = 169 ein Rechteck
mit dem Flächeninhalt von 821 = 168 gemacht. Also haben wir eine Einheit verloren!
Natürlich geht alles mit rechten Dingen zu: In Wirklichkeit erhalten wir gar kein vollständiges Rechteck, denn in der Mitte bleibt ein kleiner Streifen frei – allerdings nur eine
Einheit auf 168 Einheiten, viel weniger als 1% und deshalb kaum wahrnehmbar.
Man kann einen entsprechenden Trick immer machen, wenn man ein Quadrat der Seitenlänge fn = fn–1 + fn–2 wählt und dieses dann in ein „Rechteck“ mit den Seitenlängen
fn–1 und fn+1 = fn + fn–1 verwandelt. Dabei entsteht jeweils nur ein Fehler von einer Einheit: Mal entsteht ein kleiner Schlitz, mal eine kleine Überlappung. Dass das immer so ist,
erkennt man aus dem folgenden Satz.
3.4.3 Satz (Simpson-Identität). Für jede natürliche Zahl n t 2 gilt
fn+1  fn–1 – fn2 = (–1)n.
In Worten: fn+1  fn–1 und fn2 unterscheiden sich nur um 1, mal um +1, mal um –1,
Beweis. Wir beweisen diese Formel durch Induktion nach n. Die Aussage A(n) sei die
Aussage des Satzes.
Induktionsbasis: Sei n = 2. Wir müssen die Aussage A(2) zeigen. Dazu rechnen wir einfach die linke Seite aus:
f3  f1 – f22 = 21 – 12 = 1.
Dies ist gleich (–1)2, also gilt A(2).
Induktionsschritt: Sei nun n eine natürliche Zahl t 2, und es gelte die Aussage A(n). Wir
müssen A(n+1) zeigen. Auch dazu rechnen wir einfach die entsprechende linke Seite aus:
fn+2  fn – fn+12 = (fn+1 + fn)  fn – fn+12
= fn+1  (fn  fn+1) + fn2
= fn+1  (fn  fn+1) + fn+1  fn–1 – (–1)n
= fn+1  (fn  fn+1 + fn1) + (–1)n+1 = fn+1  0 + (–1)n+1
= (–1)n+1.
Bemerkung. Wie in der Binet-Formel bereits deutlich wurde, stehen die Fibonacci-Zahlen
in engem Zusammenhang mit der Zahl
M=
| 1,618.
Diese Zahl heißt goldener Schnitt und ist die positive Lösung der quadratischen Gleichung x2  x  1 = 0.
Man kann zeigen, dass die Folge fn+1/fn der Quotienten aufeinanderfolgender Fibonacci-Zahlen gegen M konvergiert (siehe zum Beispiel Beutelspacher und Petri 1996).
Der goldene Schnitt hat folgende schöne Eigenschaft (siehe Übungsaufgabe 19): Wenn
man eine Strecke so teilt, dass sich die größere Teilstrecke M zur kleineren Teilstrecke m
so verhält wie die Gesamtstrecke M + m zum größeren Teil M, das heißt
so ist dieses Verhältnis gleich M. Zum Beispiel teilen sich die Diagonalen eines regelmäßigen Fünfecks im goldenen Schnitt.
Wie viele Gitterpunkte enthält ein Gitterquadrat der Seitenlänge n?
Wie viele Gitterpunkte enthält ein gleichseitiges Dreieck, dessen eine Seite eine Gitterstrecke der Länge n ist?
Wie viele Gitterpunkte enthält ein reguläres Sechseck (auf dem Rand und im Innern),
dessen eine Seite eine Gitterstrecke der Länge n ist?
Ein bekanntes mathematisches Spiel ist der „Turm von Hanoi“. Auf einem von drei
Stäben sitzen n Scheiben, die kleinste oben, die größte unten. Die Aufgabe besteht
darin, diese Scheiben auf einen der anderen Stäbe zu bringen, wobei folgende Regeln
1. In jedem Schritt darf nur eine Scheibe bewegt werden.
2. Nie darf eine größere Scheibe auf einer kleineren liegen.
Zeigen Sie mit vollständiger Induktion, dass man diese Aufgabe mit 2n – 1 Schritten
Es geht die Legende, dass die Mönche eines buddhistischen Klosters das Spiel „Turm
von Hanoi“ mit n = 64 Scheiben aus echtem Gold spielen, ... und solange sie damit
beschäftigt sind, geht die Welt nicht unter.
Angenommen, die Mönche brauchen zu jedem Zug genau eine Sekunde. Wie viele
Jahre brauchen sie, bis sie fertig sind?
Zeigen Sie: Wenn ein Erdteil durch eine gewisse Anzahl von Kreisen in Länder eingeteilt wird, so kann man diese Landkarte mit zwei Farben zulässig färben.
Ein beliebiges n-Eck sei „trianguliert“, das heißt lückenlos und überschneidungsfrei in
Dreiecke unterteilt. Zeigen Sie, dass man die Ecken des n-Ecks so mit drei Farben färben kann, dass die Ecken jedes Dreiecks mit allen drei Farben gefärbt sind.
Beweisen Sie Satz 3.2.2 mit dem Trick von Gauß.
Beweisen Sie die geometrische Summenformel 3.2.4 (a) mit dem Trick von Gauß.
10 Beweisen Sie 1 + 2 + 4 + ... + 2n = 2n+1 – 1 für jede natürliche Zahl n t 1.
11 Beweisen Sie 12 + 222 + 323 + 424 + ... + n2n = (n–1)2n+1 + 2 für jede natürliche Zahl n t 1.
12 Beweisen Sie mit vollständiger Induktion nach n:
12 + 22 + 32 + ... + n2 =
n  (n  1)  (2n  1)
13 Für welche natürlichen Zahlen n gilt 2n > n2? Formulieren und beweisen Sie Ihre
14 Für welche natürlichen Zahlen gilt n! t 2n? Beweisen Sie Ihre Vermutung.
15 Zeigen Sie mit vollständiger Induktion, dass für alle natürlichen Zahlen n die Zahl
7n – 1 ein Vielfaches von 6 ist.
16 Im folgenden sehen Sie Ausschnitte aus Zahlenfolgen. Entscheiden Sie jeweils, ob es
sich um einen Ausschnitt aus der Folge der Fibonacci-Zahlen handelt und begründen
 ..., 144, 233, 322, ...
 ..., 2584, 3181, 5765, ...
 ..., 46568, 75025, 121593, ...
 ..., 39087968, 63245684, 102333652, ...
17 Ein Briefträger steigt täglich eine lange Treppe nach folgendem Muster empor: Die
erste Stufe betritt er auf jeden Fall. Von da an nimmt er jeweils nur eine Stufe oder aber zwei Stufen auf einmal. Auf wie viele Arten kann der Briefträger die n-te Stufe
[Machen Sie sich zunächst die Fälle n = 2, 3, 4 klar.]
18 Eine Drohne (männliche Biene) schlüpft aus einem unbefruchteten Ei einer Bienenkönigin, während aus befruchteten Eiern die (weiblichen) Arbeiterbienen und Königinnen schlüpfen. Eine Drohne hat also nur ein "Elter" (nämlich eine Königin), während Königinnen, wie es sich gehört, zwei Eltern haben.
Überlegen Sie sich, dass eine Drohne in der n-ten Vorfahrensgeneration genau fn
Vorfahren hat.
[Machen Sie sich die Situation für die Fälle n = 2, 3, 4 anhand einer Schemazeichnung klar.]
19 Zeigen Sie: Wenn man eine Strecke so teilt, dass sich die größere Teilstrecke M zur
kleineren Teilstrecke m so verhält wie die Gesamtstrecke M + m zum größeren Teil
M, das heißt
so ist dieses Verhältnis gleich dem goldenen Schnitt.
20 Zeigen Sie durch Induktion nach n, dass für die Fibonacci-Zahlen fn folgendes gilt:
1 + f2 + f4 + f6 + ... + f2n = f2n+1 .
21 Zeigen Sie durch Induktion nach n, dass für die Fibonacci-Zahlen gilt
fn+2 = fn + fn–1 + . . . + f1 + 1.
A. Beutelspacher, B. Petri: Der goldene Schnitt. Spektrum Akademischer Verlag, Heidelberg 21996 (Kapitel 6: Fibonacci-Zahlen).
H. Wußing: Carl Friedrich Gauß. B. G. Teubner Verlagsgesellschaft, Stuttgart 1989.
Ein zentrales Problem der diskreten Mathematik ist die Frage nach der Anzahl der Elemente einer Menge. Diese Frage scheint auf den ersten Blick einfach zu beantworten zu sein,
insbesondere wenn die Menge durch eine Aufzählung ihrer Elemente gegeben ist. Interessant ist dieses Problem allerdings, wenn die Mengen durch eine Beschreibung ihrer Eigenschaften gegeben sind oder wenn aus gegebenen, einfachen Mengen neue, komplexere
Mengen konstruiert werden.
Für eine Menge M bezeichnet ~M~ die Anzahl ihrer Elemente; wir nennen diese
Zahl die Mächtigkeit der Menge M.
Beispiele: (a) Die Mächtigkeit der Menge {1, 2, a, b, c} ist gleich ~{1, 2, a, b, c}~ = 5.
(b) Wenn M die Menge der Einwohner der Bundesrepublik Deutschland ist, so ist ~M~
| 80.000.000.
(c) Wenn M die Menge der Atome des Weltalls bezeichnet, so ist ~M~ | 1078.
Wir interessieren uns im Rahmen der diskreten Mathematik hauptsächlich für endliche
Mengen, also für solche Mengen, die nur eine endliche Anzahl von Elementen enthalten.
Daher vereinbaren wir: Wenn nicht ausdrücklich anders gesagt, sei jede vorkommende
Menge endlich.
Als erstes geben wir eine Formel an, mit der man die Anzahl der Elemente in der Vereinigung A  B und im Durchschnitt A  B berechnen kann. Wir erinnern uns dazu: Die
Vereinigung A  B („A vereinigt mit B“) der Mengen A und B besteht aus all den
Elementen, die in A oder in B enthalten sind; der Durchschnitt A  B („A geschnitten mit B“) der Mengen A und B enthält genau diejenigen Elemente, die in A und in
B enthalten sind.
Zum Beispiel: Wenn B die Menge der Studierenden im Fach Biologie und C die Menge
der Studierenden des Faches Chemie ist, dann ist B  C die Menge derjenigen Menschen,
die Biologie oder Chemie oder beides studieren, während B  C die Menge derjenigen
Studierenden ist, die sowohl Biologie als auch Chemie studieren.
4.1.1 Summenformel. Für je zwei Mengen A und B gilt
~A  B~ = ~A~ + ~B~ – ~A  B~.
Wenn A und B kein gemeinsames Element haben (man sagt dazu: A und B sind disjunkt), so gilt sogar
~A  B~ = ~A~ + ~B~.
Beispiele: (a) Um die Anzahl der Studierenden, die Biologie oder Chemie studieren, zu erhalten, genügt es nicht, nur die Anzahl der Biologiestudierenden und die Anzahl der Chemiestudierenden zu kennen, man muss auch noch wissen, wie viel Menschen Biologie und
Chemie studieren.
(b) Die Anzahl der Studierenden im Fach Psychologie ist gleich der Anzahl der weiblichen
plus der Anzahl der männlichen Studierenden des Faches Psychologie. (Wenn W die
Menge der weiblichen und M die Menge der männlichen Psychologiestudierenden ist, so
sind W und M disjunkt, also ist die Anzahl aller Studierenden des Faches Psychologie
gleich ~W~ + ~M~.)
Nun wenden wir uns der Produktformel zu. Für zwei Mengen A, B definieren wir A u B
als die Menge aller Paare, von denen der erste Teil aus A, der zweite aus B kommt. Formaler:
A u B := {(a, b) ~ a  A, b  B}.
Beispiele: (a) Wenn A = {1, 2, 3} und B = {x, y} ist, so gilt
A u B = {(1, x), (1, y), (2, x), (2, y), (3, x), (3, y)}.
(b) Wenn S die Menge aller Studierenden und V die Menge aller Vorlesungen ist, so ist
S u V die Menge aller denkbaren Vorlesungsbesuche.
Man nennt A u B das kartesische Produkt der Mengen A und B. Dies geht zurück auf
den französischen Mathematiker und Philosophen René Descartes (lat. Cartesius, 1596 
1650), der die Punkte der Ebene durch Paare von reellen Zahlen darstellte und so die Geometrie einer algebraischen Behandlung zugänglich machte; für dieses Vorgehen hat sich
ungeschickterweise auch international der Name analytische Geometrie eingebürgert.
Man kann das kartesische Produkt auch von mehr als zwei Mengen bilden: Wenn M1,
M2, ..., Ms nichtleere Mengen sind, so ist
M1 u ... u Ms := {(m1, ..., ms) ~ mi  Mi}.
Die Menge M1 u ... u Ms besteht also aus allen Folgen der Länge s, wobei das i-te Folgenglied aus der Menge Mi gewählt wird.
Man nennt (m1, ..., ms) auch ein s-Tupel. Die i-te Stelle (also die Stelle von Mi) heißt
auch die i-te Komponente des kartesischen Produkts.
4.1.2 Produktformel. Für je zwei nichtleere Mengen A und B gilt
~A u B~ = ~A~~B~.
Dies kann man auf das kartesische Produkt beliebig vieler Mengen verallgemeinern. Für
nichtleere Mengen M1, ..., Ms gilt:
~M1 u ... u Ms~ = ~M1~ ... ~Ms~.
Diese Regel ist nicht so unmittelbar einsichtig wie die Summenregel; deshalb muss dieser
Einsicht etwas nachgeholfen werden, aber der Beweis ist nicht schwierig.
Um die Menge aller Paare aus einem Element aus A und einem Element aus B zu
zählen, geht man so vor: Für die erste Komponente kommt jedes Element von A in Frage;
also gibt es genau so viele Möglichkeiten wie Elemente in A, also ~A~ Möglichkeiten.
Entsprechend gibt es für die zweite Komponente genau so viele Möglichkeiten wie die
Anzahl der Elemente von B angibt, also genau ~B~ Möglichkeiten.
Da man diese Möglichkeiten unabhängig kombinieren kann, folgt:
~A u B~ = Anzahl der Möglichkeiten für ein Element aus A u B = ~A~~B~.
Die zweite Aussage ergibt sich entsprechend (formal durch Induktion nach s).
Beispiel: Die Geheimzahl (PIN: Persönliche Identifizierungs-Nummer), die in Verbindung
mit der ec-Karte zur Identifizierung der Kunden am Geldautomaten oder beim Einkaufen
dient, besteht aus 4 Dezimalstellen, wobei als erste Ziffer keine 0 auftritt. Wie viele
PINs gibt es?
Für die erste Stelle gibt es 9 Möglichkeiten (die Ziffern 1, ..., 9), während für die
zweite, dritte und vierte Stelle jeweils 10 Möglichkeiten zur Verfügung stehen. Also ist
die Anzahl aller PINs gleich
9  10  10  10 = 9000.
Eine wichtige Anwendung der Produktformel ist das Zählen von Folgen, insbesondere von
binären Folgen.
Sei B = {0, 1} die Menge, die nur aus den Elementen 0 und 1 besteht. Eine binäre
Folge der Länge n ist eine Folge (b1, b2, ..., bn) mit bi  B. Wir fragen uns, wie groß
die Anzahl aller binären Folgen der Länge n ist.
Beispiel: Die binären Folgen der Länge 3 sind die folgenden:
000, 001, 010, 100, 011, 101, 110, 111;
also gibt es genau 8 binäre Folgen der Länge 3.
4.1.3 Satz. Die Anzahl der binären Folgen der Länge n ist gleich 2n.
Zum Beispiel gibt es über 1 Million binäre Folgen der Länge 20.
Beweis. Die Menge der binären Folgen der Länge n ist gleich dem n-fachen kartesischen
Produkt der Menge B = {0, 1}. Mit der Produktformel ergibt sich:
~B u B u ... u B~ = ~B~~B~ ... ~B~ = ~B~n = 2n.
Sei M eine Menge. Eine Menge M' ist eine Teilmenge von M, falls jedes Element von
M' auch ein Element von M ist. Wir schreiben dafür auch M'  M.
Jede Menge hat sich selbst als Teilmenge; eine andere „triviale“ Teilmenge ist die leere
Menge, die kein Element enthält; diese wird mit {} oder mit  bezeichnet.
Die Menge aller Teilmengen einer Menge M bezeichnen wir mit P(M) und nennen
P(M) die Potenzmenge von M.
Als Beispiel bestimmen wir alle Teilmengen der Menge M = {a, b, c}:
{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}.
Dies führt uns zur Vermutung, dass eine Menge mit n Elementen genau 2n Teilmengen
4.1.4 Satz. Sei M eine n-elementige Menge. Dann hat M genau 2n Teilmengen.
Beweis. Wir beweisen den Satz durch Induktion nach n.
Sei zunächst n = 1. Dann hat M nur ein Element, und somit nur zwei Teilmengen,
nämlich {} und M. Somit gilt der Satz in diesem Fall.
Sei nun n eine natürliche Zahl mit n t 2, und sei die Aussage richtig für n–1. Wir betrachten ein festes Element m0 von M. Dann gibt es zwei Sorten von Teilmengen von
M: solche, die m0 enthalten, und solche, die m0 nicht enthalten.
Die Teilmengen von M, die m0 nicht enthalten, sind genau die Teilmengen der
(n–1)-elementigen Menge M \ {m0}. Also gibt es nach Induktion genau 2n–1 solche
Die Teilmengen von M, die m0 enthalten, entsprechen aber auch genau den Teilmengen von M \ {m0}. Denn durch Entfernen des Elements m0 werden die Teilmengen der
einen Sorte in die der anderen überführt. Somit gibt es auch genau 2n–1 Teilmengen dieser Sorte.
Insgesamt besitzt M also 2n–1 + 2n–1 = 2n Teilmengen.
Nun studieren wir nicht alle Teilmengen einer gegebenen Menge, sondern nur die Teilmengen einer festen Mächtigkeit.
Wir definieren: Die Anzahl der Teilmengen der Mächtigkeit k einer n-elementigen
Menge wird mit
§ n·
© k¹
bezeichnet (gesprochen: „n über k“); diese Zahlen heißen Binomialzahlen.
Beispiele von Binomialzahlen:
¨ ¸ = 1,
da jede Menge genau eine 0-elementige Teilmenge hat, nämlich die leere Menge.
da jede n-elementige Menge nur eine n-elementige Teilmenge besitzt, nämlich sich selbst.
¨ ¸ = n,
da eine n-elementige Menge genau n Elemente, also auch genau n Teilmengen der
Mächtigkeit 1 besitzt.
¨ ¸ = 6,
da die 4-elementige Menge {a, b, c, d} die folgenden sechs 2-elementigen Teilmengen
hat: {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}.
Beim Lotto „6 aus 49“ werden sechs der Zahlen 1, 2, ..., 49 gezogen, wobei es auf die
Reihenfolge nicht ankommt. In unserer Sprache heißt das: Es wird eine 6-elementige Teil§ 49 ·
menge der Menge {1, 2, ..., 49} gezogen. Dafür gibt es nach Definition genau ¨¨ ¸¸
Möglichkeiten. Wir werden diese Zahl bald ausrechnen können.
Generell stellt sich die Frage, wie man die Binomialzahlen ausrechnen kann. Dazu stehen
zwei Methoden zur Verfügung: Eine rekursive und eine explizite Formel.
4.2.1 Rekursionsformel für die Binomialzahlen. Seien k und n natürliche Zahlen mit
1 d k d n. Dann gilt
§ n  1· § n  1·
¸ ¨
© k ¹ © k  1¹
Dieser Satz hat viele nützliche Anwendungen. Wenn wir zum Beispiel ¨¨ ¸¸ ausrechnen
wollen, können wir wie folgt vorgehen:
§ 5· § 5·
¨ ¸ ¨ ¸
© 2¹ © 1¹
§ 4· § 4· § 5·
¨ ¸ ¨ ¸ ¨ ¸
© 2¹ © 1¹ © 1¹
6  4  5 15 .
Zum Beweis gehen wir wie folgt vor. Wir betrachten irgendeine Menge M mit n Elementen. Wir fassen eines der Elemente von M genauer ins Auge und nennen es m.
Dann kann man die k-elementigen Teilmengen von M bezüglich des Elements m in
zwei Klassen einteilen. Die erste Klasse besteht aus denjenigen k-elementigen Teilmengen,
die das Element m nicht enthalten, und die zweite aus denen, die das Element m enthalten.
Wir zählen beide Mengen separat ab. Jede Teilmenge in der ersten Klasse ist eine
k-elementige Teilmenge der (n–1)-elementigen Menge M \ {m}. Also gibt es davon genau
¸ Stück.
© k ¹
Zur zweiten Klasse: Betrachten wir eine Teilmenge M’ in dieser Klasse. Diese enthält
m. Wir entfernen nun m aus M’ und aus M. Dann ist M’ \ {m} eine (k–1)-elementige
Teilmenge der (n–1)-elementigen Menge M \ {m}. Umgekehrt kann man jede (k–1)elementige Teilmenge von M \ {m} durch Hinzufügen von m zu einer Teilmenge der
Klasse 2 ergänzen. Somit ist die Anzahl der Teilmengen in der Klasse 2 gleich ¨
© k  1¹
Durch Addition der beiden Anzahlen ergibt sich die Formel.
Die Binomialzahlen kann man sehr schön im sogenannten Pascalschen Dreieck zusammenfassen. Dieses Dreieck war chinesischen Mathematikern schon viele Jahrhunderte vor
Blaise Pascal (1623  1662) bekannt. Das Bildungsgesetz dieses Dreiecks entspricht genau
obiger Rekursionsformel:
Manchmal ist auch eine explizite Formel sehr nützlich. Mit dieser kann man die Binomialzahlen insbesondere für kleine Werte von k bequem ausrechnen.
4.2.2 Explizite Formel für die Binomialzahlen. Seien k und n natürliche Zahlen mit
0 d k d n. Dann gilt
k!  (n  k )!
n  (n  1)  (n  2)  ...  (n  k  1)
n  (n  1)
Der Beweis erfolgt durch Induktion nach n.
§ 0·
Induktionsbasis: n = 0. Dann muss auch k = 0 sein. Da ¨ ¸ = 1 ist und da
k ! ( n  k )!
0! ( 0  0)!
1 1
ist (man beachte, dass 0! = 1 gesetzt wird), gilt die Aussage im Fall n = 0.
Induktionsschritt: Sei n t 1 eine natürliche Zahl, und sei die Aussage richtig für n.
Wir müssen zeigen, dass sie dann auch für n+1 gilt. Dazu schließen wir wie folgt:
§ n  1· § n· § n ·
¸ = ¨ ¸ ¨
© k ¹ © k¹ © k  1¹
k ! ( n  k )! ( k  1)! ( n  ( k  1))!
(nach 4.2.1)
 
( k  1)! ( n  k )! k ( k  1)! ( n  k )! n  k  1
( 
( k  1)! ( n  k )! k n  k  1
(Zusammenfassen)
( n  k  1)  k
( k  1)! ( n  k )! k  ( n  k  1)
(Hauptnenner)
n 1
(k  1)!  (n  k )! k  (n  k  1)
( n  1)!
k ! ( n  1  k )!
Damit gilt die Aussage auch für n+1, und der Satz ist vollständig bewiesen.
Beispiel: Wir können jetzt die Anzahl der Möglichkeiten beim Lotto ausrechen. Es gilt:
§ 49 ·
= 13.983.816.
6!  43!
Eine wichtige Anwendung der Binomialzahlen ist der Binomialsatz, mit dem man Ausdrücke der Form (x + y)n berechnen kann.
4.2.3 Binomialsatz. Seien x und y Unbestimmte über R. Dann gilt für jede natürliche
Zahl n die folgende Gleichung:
¦ ¨ k ¸ x k  yn  k .
(x  y)n
k 0©
Bemerkung. Der Binomialsatz hat viele Anwendungen. Zunächst sagt er aber, wie man einen schwierig zu bestimmenden Term durch einfache Terme ausdrückt. Aber Obacht: Obwohl es zunächst nicht so aussieht, ist die linke Seite die schwierig auszurechnende, während die rechte ganz einfach zu bestimmen ist.
Beispiel: Was ist 115? Diese schwierig erscheinende Aufgabe können wir mit dem Binomialsatz ganz einfach im Kopf ausrechnen:
115 = (10+1)5
§ 5· 2 § 5· 3 § 5· 4 § 5·
= ¨ ¸ + ¨ ¸ 10 + ¨ ¸ 10 + ¨ ¸ 10 + ¨ ¸ 10 + ¨ ¸ 105
© 0¹ © 1¹
= 1 + 510 + 10100 + 101000 + 510000 + 100000 = 161051.
Beweis des Binomialsatzes. Wir stellen uns vor, wie man die linke Seite ausrechnen würde:
Man müsste n mal die Terme x+y miteinander multiplizieren. Wenn man dies ausmultiplizieren würde, würde man aus k dieser Terme die Variable x und aus den anderen n–
k die Variable y auswählen. Also erhält man Ausdrücke der Form xkyn–k .
Die Frage ist nur, wie oft man den Summand xkyn–k erhält. Um diesen Term zu erhalten, muss man x genau k mal unter n Möglichkeiten auswählen. Daher erhält man den
Summand xkyn–k genau ¨ ¸ mal.
Man kann den Binomialsatz auch für feste Werte von x und y spezialisieren und n allgemein lassen. So erhält man eine Aussage über Binomialzahlen, die man dann in eine
Aussage über Teilmengen übersetzen kann.
4.2.4 Korollar. Sei n eine natürliche Zahl. Dann gilt:
¦ ¨© k¸¹
Das heißt: Die Anzahl aller Teilmengen einer n-elementigen Menge ist gleich 2n.
¦ ¨© k¸¹ ( 1) k
k gerade
¨¨ ¸¸ =
k ungerade
¨¨ ¸¸ .
Das heißt: Die Anzahl der Teilmengen gerader Mächtigkeit einer n-elementigen Menge ist
gleich der Anzahl der Teilmengen ungerader Mächtigkeit.
Beweis. (a) Wir setzen im Binomialsatz x = 1 und y = 1. Dann ergibt sich:
2n = (1+1)n = ¦ ¨ ¸ 1k 1n  k ¦ ¨ ¸ .
(b) Wir setzen im Binomialsatz x = –1 und y = 1. Dann ergibt sich:
0 = (–1+1)n
¦ ¨© k¸¹ ( 1) k 1n k ¦ ¨© k¸¹ ( 1) k .
Die Binomialzahlen ¨ ¸ sind definiert als die Anzahl der k-elementigen Teilmengen ei©k¹
ner n-elementigen Menge. Man spricht manchmal auch von den „ungeordneten Auswahlen
ohne Wiederholung“ von k Objekten einer n-elementigen Menge. Wir interessieren uns
jetzt noch für die Auswahlen mit Wiederholungen.
Beispiel: Wir betrachten alle 15 ungeordneten Auswahlen mit Wiederholungen von vier
Elementen der Menge {A, B, C}:
AAAA AAAB AAAC AABB AABC AACC ABBB ABBC
ABCC ACCC BBBB BBBC BBCC BCCC CCCC.
Mit dem folgenden Satz erhalten wir eine allgemeine Formel für die Auswahlen mit
4.2.5 Satz. Die Anzahl der ungeordneten Auswahlen mit Wiederholung von k Objekten
aus einer Menge von n Objekten ist
§ n  k  1·
¨ k ¸.
Beweis. Wir konstruieren eine eindeutige Zuordnung (formal mathematisch gesprochen eine „bijektive Abbildung“) zwischen der Menge aller ungeordneten Auswahlen, die wir betrachten, und der Menge aller binären (n+k–1)-Tupel mit genau k Einsen. Da die Anzahl
dieser (n+k–1)-Tupel gleich
¨ k ¸
ist, ist damit die Behauptung bewiesen.
Da wir ungeordnete Auswahlen betrachten, können wir diese so beschreiben, dass wir
zuerst die Objekte der ersten Art, dann die der zweiten Art und so weiter aufschreiben.
(Vergleichen Sie das obige Beispiel.) Wir ordnen nun jeder solchen Auswahl eine binäre
Folge zu; diese ist wie folgt definiert:
Wenn n1 die Anzahl der Objekte der ersten Art ist, dann beginnt die Folge mit n1
Einsen; nach dieser Folge von Einsen folgt eine Null.
Wenn n2 die Anzahl der Objekte des zweiten Typs ist, dann wird die Folge mit n2
Einsen fortgesetzt; dann kommt eine Null.
Mit anderen Worten: Die Folgen von Einsen entsprechen den Folgen von Objekten des
gleichen Typs, während die Nullen als Trennzeichen zwischen Zeichen verschiedenen
Typs dienen. Zum Beispiel gehört zu der Auswahl ABCC die binäre Folge 101011. (Beachten Sie, dass gewisse ni gleich Null sein können; in diesem Fall stehen in der binären
Folge Nullen direkt beieinander. Zum Beispiel entspricht der Auswahl AACC der Folge
110011.)
Da jede Auswahl aus genau k Objekten besteht, hat jede binäre Folge genau k Einsen; da man n–1 Trennzeichen braucht, um die unterschiedlichen Objekttypen zu trennen,
hat jede binäre Folge genau n–1 Nullen. Insbesondere hat jede binäre Folge die Länge
n+k–1.
Da man umgekehrt jeder binären Folge der Länge n+k–1 mit genau n–1 Nullen eindeutig eine ungeordnete Auswahl mit Wiederholungen von k Objekten aus einer
n-elementigen Menge zuordnen kann, ist die Behauptung bewiesen.
In diesem Abschnitt soll die Summenformel 4.1.1 verallgemeinert werden. Wenn wir die
Mächtigkeit der Vereinigung der drei endlichen Mengen A, B, C bestimmen wollen, gehen wir so vor:
~A  B  C~=~A~+ ~B~ + ~C~ – ~A  B~ – ~A  C~ – ~B  C~ + ~A  B  C~.
Dies wollen wir jetzt auf die Vereinigung beliebig vieler Mengen A1, A2, ..., As verallgemeinern.
4.3.1 Siebformel. Seien A1, A2, ..., As beliebige endliche Mengen. Dann gilt:
~A1  A2  ...  As~ = D1 – D2 + D3 – D4 r ... + (1)s1Ds.
Dabei erhält man Di auf folgende Weise:
(a) Man bildet den Durchschnitt von je i der Mengen A1, A2, ..., As.
(b) Man bestimmt die Mächtigkeit dieser Durchschnitte.
(c) Man addiert diese Mächtigkeiten.
Zum Beispiel ist D1 die Summe der Mächtigkeiten der Mengen A1, A2, ..., As.
Bemerkung. Man kann sich den Satz so vorstellen, dass D1 den Wert der linken Seite nur
sehr grob angibt (1. Approximation). Durch den Korrekturterm D2 wird die linke Seite
schon etwas besser approximiert (2. Approximation). Genauer gesagt gilt: Bei der i-ten
Approximation werden die Elemente der Vereinigung genau einmal gezählt, die im Durchschnitt von höchstens i der Mengen A1, A2, ..., As liegen.
Beweis der Siebformel. Sei s ein beliebiges Element der Vereinigung A1  A2  ...  As.
Wir müssen uns davon überzeugen, dass s in dem Ausdruck auf der rechten Seite genau
einmal gezählt wird.
Das Element s sei in genau r der Mengen A1, A2, ..., As enthalten; ohne Beschränkung der Allgemeinheit sei s in A1, ..., Ar enthalten. Dann wird s in D1 genau r mal
§r·
gezählt, nämlich in jeder Menge A1, ..., Ar genau einmal. In D2 wird s genau ¨¨ ¸¸ mal
gezählt, nämlich in jedem Durchschnitt von jeweils zwei der Mengen A1, ..., Ar genau
einmal. Entsprechend wird s in D3 genau ¨¨ ¸¸ mal gezählt, in jedem Durchschnitt von
jeweils drei der Mengen A1, ..., Ar genau einmal. Und so weiter. In Dr wird s genau
¨¨ ¸¸ mal gezählt, nämlich im Durchschnitt aller r Mengen A1, ..., Ar genau einmal. Im
©r¹
Durchschnitt von mehr als r der Mengen A1, ..., As ist s nicht enthalten, das heißt, für
i > r ist Di = 0.
Insgesamt wird s auf der rechten Seite also genau
§r· § r · § r·
¨¨ ¸¸  ¨¨ ¸¸ + ¨¨ ¸¸ # ... + (1)r1 ¨¨ ¸¸
©1¹ © 2 ¹ © 3 ¹
mal gezählt. Da nach 4.2.4 die alternierende Summe aller Binomialkoeffizienten gleich 0
ist, ist obige Summe gleich
r §r·
k §r·
¨¨ 0 ¸¸  ¦ ¨¨ k ¸¸(1) = ¨¨ 0 ¸¸  0 = 1.
© ¹ k 0© ¹
Das Element s wird also auch auf der rechten Seite genau einmal gezählt. Damit ist die
Siebformel bewiesen.
4.3.2 Korollar. Seien A1, A2, ..., As beliebige Teilmengen einer n-elementigen Menge A.
~A \ (A1  A2  ...  As)~ = n  D1 + D2  D3 + D4 # ... + (1)sDs.
Dabei werden die Di genauso wie in der Siebformel gebildet.
Eine interessante Anwendung der Siebformel ist die Bestimmung der Anzahl gewisser Permutationen.
Eine Permutation einer endlichen Menge M ist eine bijektive Abbildung der Menge
M in sich. Das heißt: Jedem Element aus M wird ein Element von M so zugeordnet,
dass keine zwei Elemente das gleiche Bild haben.
Zum Beispiel ist die Abbildung S: {1, 2, 3, 4, 5} o {1, 2, 3, 4, 5}, definiert durch
S(1) = 2, S(2) = 4, S(3) = 3, S(4) = 5, S(5) = 1,
eine Permutation. Wir können diese Permutation auch nach folgendem Muster notieren:
§ 1 2 3 4 5·
S = ¨¨
© 2 4 3 5 1¹
Die Regel dabei lautet: Schreibe die Elemente von M der Reihe nach in die erste Zeile;
unter jedes Element der oberen Zeile schreibe das Bild dieses Elementes.
Da Permutationen bijektive Abbildungen einer Menge in sich sind, ergibt sich, dass die
Hintereinanderausführung von Permutationen einer Menge M wieder eine Permutation
der Menge M ist. Ferner ist die zu einer Permutation inverse Abbildung ebenfalls eine
Permutation. Mit anderen Worten: Die Permutationen einer Menge M bilden bezüglich
der Hintereinanderausführung eine „Gruppe“; man nennt sie die symmetrische Gruppe
4.3.3 Satz. Die Anzahl der Permutationen einer n-elementigen Menge ist n!.
Beispiel: Um 100 Menschen auf 100 Stühle zu setzen, gibt es genau 100! | 10158 Möglichkeiten.
Beweis. Wir überlegen uns systematisch, wie viele Möglichkeiten es für eine Permutation
S einer n-elementigen Menge M gibt. Ohne Einschränkung der Allgemeinheit können
wir M = {1, 2, 3, ..., n} wählen. Wir überlegen uns der Reihe nach, wie viele Möglichkeiten es für die Bilder der Elemente 1, 2, 3, ..., n gibt.
Für das Bild des ersten Elements 1 gibt es n Möglichkeiten.
Für das Bild von 2 stehen noch n–1 Möglichkeiten zur Verfügung, nämlich alle außer
dem Bild S(1) des ersten Elements.
Für das Bild von 3 stehen nur noch n–2 Möglichkeiten zur Verfügung, nämlich alle
außer den bereits vergebenen, das heißt den Bildern S(1) und S(2).
Für das vorletzte Element n–1 stehen gerade noch 2 Elemente als Bilder zur Auswahl, da bereits n–2 Elemente vergeben sind (die Bilder von 1, 2, ..., n–2).
Das Bild des letzten Elements ist vollständig determiniert.
Also gibt es insgesamt genau n  (n–1)  (n–2)  ...  2  1 = n! Möglichkeiten für die
Auswahl einer beliebigen Permutation S von M.
Sei S eine Permutation der Menge M = {1, 2, 3, ..., n}. Wir nennen ein Element i von
M einen Fixpunkt von S, falls die Permutation S das Element i auf sich abbildet, falls
also S(i) = i gilt.
Zum Beispiel ist bei obiger Permutation das Element 3 ein Fixpunkt. Dagegen hat die
§1 2 3 4 5·
©5 3 1 2 4¹
überhaupt keinen Fixpunkt.
Wir werden im Folgenden die Anzahl der Permutationen ohne jeden Fixpunkt bestimmen.
Es gibt zahlreiche Einkleidungen dieses Problems:
(a) Eine unaufmerksame Sekretärin soll n Briefe in n Umschläge stecken. Wie viele
Möglichkeiten gibt es, dies so zu machen,

References: § 5
 § 5

§ 4
 § 4
 § 5

§ 0

§ 49

§ 5
 § 5
 § 5
 § 5

§ 1

§1