Färbungsmethoden
Christian Lindorfer
9. Juni 2015
Inhaltsverzeichnis
1 Einleitung
2
2 Überdeckungen des Schachbretts
2
3 Monochromatische Rechtecke
4
4 Das Museumsproblem
5
5 Punkte in der Ebene
7
Abbildungsverzeichnis
1
2
3
4
5
6
7
8
9
10
11
12
13
Schachbrett mit 2 fehlenden Ecken . . . . . . . . . . . . . . . . .
Färbung mit a Farben . . . . . . . . . . . . . . . . . . . . . . . .
Aufteilung des m × n Schachbretts . . . . . . . . . . . . . . . . .
Das Rechteck rechts unten . . . . . . . . . . . . . . . . . . . . . .
Beispiele für monochromatische Rechtecke . . . . . . . . . . . . .
Alle 8 verschiedenen Spalten . . . . . . . . . . . . . . . . . . . . .
Beispiele für Ohren eines Polygons (rot) . . . . . . . . . . . . . .
Beispiel zu Lemma 1 Fall 2, Trennlinie rot . . . . . . . . . . . . .
Beispiel für 3-Färbung eines Polygons . . . . . . . . . . . . . . .
Beispiel für Polygon mit 3n Ecken, das genau n Wärter benötigt
Sechseck und Färbungen
in den einzelnen Fällen . . . . . . . . .
√
Kreis mit Radius 3 um v0 . . . . . . . . . . . . . . . . . . . . .
Färbung und Abstandsberechnung . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 2
. 3
. 3
. 4
. 4
. 5
. 5
. 6
. 7
. 7
. 8
. 9
. 10
Literatur
[1] Albrecht Beutelspacher, Marc-Alexander Zschiegner: Diskrete Mathematik für Einsteiger. Springer, 2014.
[2] Engel, Arthur: Problem Solving Strategies. Springer, 1998.
1
1
Einleitung
Häufig können interessante mathematische Probleme durch Einführen einer Hilfsfunktion
auf einfache Weise gelöst werden. Diese Hilfsfunktion kann in manchen Fällen durch eine
Färbung realisiert werden. Ich werde in dieser Seminararbeit einige Fälle auswählen, bei
denen die Methode zu schönen Lösungen führt. Dazu ein einführendes Beispiel:
Beispiel 1. Gegeben sei ein normales (8 × 8) Schachbrett und Dominosteine (2 × 1). Klarerweise kann man dieses Schachbrett lückenlos mit Dominosteinen überdecken, so dass sich
keine zwei Dominosteine überlappen. Nun werden wie in Abbildung 1 dargestellt zwei gegenüberliegende Ecken entfernt. Lässt sich das Schachbrett immer noch lückenlos mit den
Dominosteinen überdecken?
Abbildung 1: Schachbrett mit 2 fehlenden Ecken
Quelle: Beutelspacher, Zschiegner: Diskrete Mathematik für Einsteiger
Man wird schnell feststellen, dass das nicht möglich ist. Das wollen wir nun mit einer
Färbungsmethode beweisen. Dabei liefert die Färbung des Schachbretts schon eine gute
Hilfestellung.
Wie man leicht überprüfen kann haben die zwei entfernten Eckfelder die selbe Farbe,
oBdA sei diese schwarz. Da das komplette Schachbrett gleich viele weiße wie schwarze Felder
besitzt, haben wir jetzt 32 weiße und 30 schwarze Felder. Nun überdeckt man mit jedem
Dominostein genau ein weißes und ein schwarzes Feld. Mit 30 Dominosteinen hat man also
alle schwarzen Felder überdeckt, es sind noch 2 weiße Felder übrig, die nicht mit einem
Dominostein überdeckt werden können, daher kann nie das gesamte Brett mit Dominosteinen
überdeckt werden.
2
Überdeckungen des Schachbretts
Wir wollen nun Überdeckungen bei Schachbrettern verallgemeinern. Ein m × n-Schachbrett
ist ein Schachbrett mit m Zeilen und n Spalten. Die Frage ist nun, ob ein solches m × nSchachbrett mit verallgemeinerten Dominosteinen der Größe a × 1 mit festem a überdeckt
werden kann. Dazu existiert der folgende Satz:
Satz 1. Ein m × n-Schachbrett kann genau dann lückenlos ohne Überschneidungen mit
a × 1-Dominosteinen überdeckt werden, wenn gilt: a | m oder a | n
Beweis. Sei zunächst die rechte Seite erfüllt, also oBdA gelte a | m. Offensichtlich kann nun
jede Spalte der Länge m mit Dominosteinen der Länge a überdeckt werden. Dadurch erhält
man eine Überdeckung des gesamten Schachbretts.
Sei nun das m × n-Schachbrett lückenlos mit a × 1-Dominosteinen überdeckt. Wir färben
nun das Schachbrett mit a Farben (1, 2, 3, ..., a). Dazu beginnen wir links oben mit der Farbe
2
1 und erhöhen dann sowohl nach rechts und nach unten die vorhergehende Zahl jeweils um
1, also: 1, 2, 3, ..., a, 1, 2, ... wie in Abbildung 2 dargestellt.
Abbildung 2: Färbung mit a Farben
Quelle: Beutelspacher, Zschiegner: Diskrete Mathematik für Einsteiger
Es ist leicht zu sehen, dass jeder Dominostein der Länge a genau ein Feld jeder Farbe
überdeckt. Damit also das Schachbrett komplett überdeckt werden kann, muss jede Farbe
exakt gleich oft vorkommen. Wir wollen jetzt untersuchen, was in der rechten unteren Ecke
passiert.
Abbildung 3: Aufteilung des m × n Schachbretts
Quelle: Beutelspacher, Zschiegner: Diskrete Mathematik für Einsteiger
Sei m = ha + b die Anzahl der Zeilen und n = ka + c die Anzahl der Spalten, wobei
b, c ∈ {0, 1, ..., a−1}. Es ist klar, dass in den ersten ka Spalten jede Farbe gleich oft vorkommt
(nämlich genau k mal in jeder Zeile). Wir betrachten nun die restlichen c Spalten. Hier gilt
nach dem selben Argument, dass in den ersten ha Zeilen jede Farbe gleichhäufig vorkommt.
Daher genügt es, das Rechteck in der rechten unteren Ecke zu untersuchen, das b Zeilen und
c Spalten hat. Dieses Rechteck ist in Abbildung 3 dargestellt.
Falls b = 0 oder c = 0, dann ist entweder m oder n durch a teilbar und wir sind fertig.
Betrachte also b > 0 und c > 0 Sei nun oBdA c ≥ b. Wir beweisen nun die folgende
Behauptung: In dem Rechteck in Abbildung 4 mit b Zeilen und c Spalten kommt die Farbe
c häufiger vor als die Farbe a.
Da c < a ist, kommt in der ersten Zeile des Rechtecks a nicht vor und in jeder Zeile
tritt jede Farbe höchstens einmal auf. Die Farbe c kommt in jeder Zeile genau einmal vor,
3
Abbildung 4: Das Rechteck rechts unten
Quelle: Beutelspacher, Zschiegner: Diskrete Mathematik für Einsteiger
da c ≥ b gilt. Daraus folgt nun, dass die Farbe c häufiger vorkommt als die Farbe a. Also
kommen nicht alle Farben gleich häufig vor, und damit ist im Fall b 6= 0 und c 6= 0 keine
Überdeckung möglich.
Satz 2. Ein m × n-Schachbrett sei lückenlos durch eine Mischung aus 4 × 1- und 2 × 2Steinen überdeckt. Nun wird ein 4 × 1-Stein entfernt und durch einen 2 × 2-Stein ersetzt.
Dann gilt: Mit dem neuen Set kann man das Schachbrett nicht überdecken.
Beweis. Wir färben das Schachbrett mit den vier Farben 1, 2, 3, 4 wie im vorigen Satz. Jeder
4×1-Dominostein überdeckt alle vier Farben, während ein 2×2-Stein zwei Felder der gleichen
Farbe überdeckt und dafür eine Farbe gar nicht enthält. Daher kann der 4 × 1-Stein nicht
durch einen 2 × 2-Stein ersetzt werden.
3
Monochromatische Rechtecke
Wir betrachten nun wieder Schachbretter beliebiger Größe, bei denen jedes Feld entweder
schwarz oder weiß gefärbt ist. Wir beschäftigen uns mit der Frage, ob bei einem beliebig
gefärbten Schachbrett ein Rechteck (mindestens Größe 2 × 2) existiert, dessen Eckfelder
alle mit der selben Farbe gefärbt sind. Ein solches Rechteck nennen wir monochromatisch.
Beispiele für monochromatische Rechtecke sind in Abbildung 5 zu sehen.
Abbildung 5: Beispiele für monochromatische Rechtecke
Quelle: Beutelspacher, Zschiegner: Diskrete Mathematik für Einsteiger
Satz 3. Ein Schachbrett mit einer Größe von mindestens 3 × 7 Feldern enthält immer ein
monochromatisches Rechteck.
Beweis. Wir betrachten für ein Schachbrett beliebiger Größe ein Teilbrett mit 3 Zeilen und
7 Spalten.
1. Feststellung: Keine Spalte kommt doppelt vor, sonst gibt es ein monochromatisches
Rechteck.
2. Feststellung: Es gibt genau 23 = 8 verschiedene mögliche Spalten, diese sind in Abbildung 6 dargestellt.
4
3. Feststellung: Sowohl die rein weiße als auch die rein schwarze Spalte können nicht
auftreten: Tritt eine Spalte mit einer Farbe auf, darf keine weitere Spalte mit zwei
Feldern dieser Farbe auftreten, sonst hätten wir ein monochromatisches Rechteck.
Daher kann es höchstens fünf Spalten geben, was einen Widerspruch zur Annahme
ergibt.
Jetzt bleiben aber nur sechs verschiedene Spalten übrig, daher muss jeder Streifen der Länge
7 mindestens ein monochromatisches Rechteck enthalten.
Abbildung 6: Alle 8 verschiedenen Spalten
Quelle: Beutelspacher, Zschiegner: Diskrete Mathematik für Einsteiger
4
Das Museumsproblem
In Museen muss jeder Winkel dauerhaft überwacht werden. Wir gehen nun davon aus, dass
das Museum ein Polygon mit n Ecken als Grundriss besitzt, die Wächter nehmen wir als
statisch an. Uns interessiert nun, wie viele Wächter man benötigt, um ein beliebig geformtes
Museum lückenlos überwachen zu können.
Dazu eine etwas ”mathematischere”Formulierung:
Gegeben sei eine polygonale Fläche G. Wähle möglichst wenige Punkte p1 , p2 , ..., pk in G,
sodass jeder Punkt in G durch eine Gerade, die ganz in G mit einem pi verbunden werden
kann.
Dazu benötigen wir zuerst ein paar wichtige Begriffe zum Thema Triangulierungen:
Definition 1. Ein Polygon P hat ein Ohr am Eckpunkt v, falls das Dreieck geformt aus v
und den benachbarten Eckpunkten vollständig in P liegt.
Abbildung 7: Beispiele für Ohren eines Polygons (rot)
Lemma 1. In einem einfachen Polygon P mit mehr als drei Ecken existieren immer mindestens zwei disjunkte Ohren (also Ohren, die keine gemeinsame Kante haben)
Beweis. Der Beweis ist eine Induktion über die Anzahl der Eckpunkte von P .
Für die Induktionsbasis n = 4 gilt die Aussage: Ein konvexes Viereck kann beliebig in
zwei Dreieck als Ohren zerlegt werden. Bei einem konkaven Viereck sind immer 3 Ecken
konvex (Innenwinkel < π) und die an die nicht konvexe Ecke angrenzenden Ecken sind
disjunkte Ohren.
Der Satz gelte für alle Polygone mit bis zu n Ecken. Sei nun ein Polygon P mit n + 1
Ecken gegeben. Sei v1 v2 v3 eine konvexe Ecke.
5
1. Fall: v1 v2 v3 ist ein Ohr. Durch das Entfernen des Ohrs entsteht ein Polygon P 0 mit
n Eckpunkten. Mit der Induktionsvoraussetzung besitzt P 0 zwei disjunkte Ohren, nur
eines davon kann die neue Kante v1 v3 enthalten, daher hat auch P zwei Ohren.
2. Fall: v1 v2 v3 ist kein Ohr. Es muss also mindestens ein Eckpunkt im Inneren des Dreiecks v1 v2 v3 existieren. Sei v4 der Punkt im Dreieck, der minimalen Abstand zu v2
besitzt. Trenne P durch die Strecke v2 v4 (muss im Inneren von P liegen) in zwei kleinere Polygone P 0 und P 00 wie in Abbildung 8 dargestellt. Ist entweder P 0 oder P 00 ein
Dreieck, so gehe zu Fall 1. Sonst gilt: P 0 und P 00 haben mindestens vier Ecken. Damit
haben sie laut Induktionsvoraussetzung jeweils mindestens zwei disjunkte Ohren, von
denen wie im Fall 1 maximal eines die neue Kante v2 v4 enthalten kann. Also müssen
in P schon vor dem Zerlegen zwei disjunkte Ohren gewesen sein.
Abbildung 8: Beispiel zu Lemma 1 Fall 2, Trennlinie rot
Aus diesem Lemma können wir nun relativ einfach den folgenden wichtigen Satz folgern:
Satz 4. Jedes einfache Polygon P kann trianguliert werden.
Beweis. Der Beweis erfolgt wieder durch vollständige Induktion über die Anzahl der Eckpunkte n von P
Für die Induktionsbasis n = 3 ist die Aussage trivial.
Der Satz gelte für alle Polygone mit bis zu n Eckpunkten. Sei P ein Polygon mit n + 1
Eckpunkten. Laut Lemma 1 existiert ein Ohr in P . Durch Abtrennen des Ohrs (Dreiecks)
entsteht ein Polygon P 0 mit n Eckpunkten, dieses kann laut Induktionsvoraussetzung trianguliert werden. Die Triangulierung von P 0 ergibt zusammen mit der Kante, an der das Ohr
abgetrennt wurde eine Triangulierung von P .
Satz 5. Die Eckpunkte eines triangulierten Polygons P lassen sich so mit drei Farben
einfärben, dass für jedes Dreieck der Triangulierung die 3 Eckpunkte unterschiedliche Farben
haben.
Beweis. Auch hier wird wieder über die Anzahl der Ecken n von P induziert.
Für n = 3 färbt man die drei Ecken mit den drei Farben.
Die Aussage gelte für Polygone mit bis zu n Eckpunkten. Sei P Polygon mit n + 1
Eckpunkten. Wähle eine beliebige Kante v1 v2 aus der Triangulierung. Diese Kante teilt das
Polygon in zwei Polygone P 0 und P 00 mit weniger Eckpunkten. Laut Induktionsvoraussetzung
lassen sich diese Polygone 3-färben. Die Farben werden dabei so gewählt, dass die Eckpunkte
v1 und v2 in P und P 0 jeweils die gleiche Farbe erhalten. Das Zusammenfügen von P 0 und
P 00 zu P liefert dann die Behauptung.
6
Abbildung 9: Beispiel für 3-Färbung eines Polygons
Satz 6. Zur Bewachung eines einfachen Polygons mit n Seiten sind bn/3c Wächterpunkte
stets ausreichend und manchmal notwendig.
Beweis. Zu einem einfachen Polygon lässt sich laut Satz 4 immer eine Triangulierung, also
eine Zerlegung des Polygons in Dreiecke, konstruieren.
Außerdem lassen sich die Eckpunkte des Polygons laut Satz 5 so mit 3 Farben färben,
dass jedes Dreieck der Triangulierung 3 verschiedenfarbene Eckpunkte besitzt.
Nun muss eine Farbe existieren, mit der ≤ n/3 Ecken des Polygons gefärbt wurden. An
diese Ecken werden die Wächter platziert. Da nun jedes Dreieck einen Punkt dieser Farbe
besitzt, muss jedes Dreieck, von einem Wächter überblickt werden können. Also wird das
gesamte Polygon von den Wächterpunkten überwacht. Nun soll noch ein Beispiel angegeben
werden, für das diese Schranke tatsächlich angenommen wird.
Abbildung 10: Beispiel für Polygon mit 3n Ecken, das genau n Wärter benötigt
Quelle: http://de.wikipedia.org/wiki/Problem_der_Museumsw%C3%A4chter
Bei dem in Abbildung 10 dargestellten Polygon können nie zwei Zacken mit einem
Wächter überblickt werden. Daher werden mindestens n Wächterpunkte benötigt, also nach
dem ersten Teil des Beweises genau n.
5
Punkte in der Ebene
Probleme, die auf der Färbung der Ebene basieren stellen ein aktuelles Forschungsgebiet
der Mathematik dar. Ein berühmtes Beispiel dafür ist der Vier-Farben-Satz, der besagt,
dass vier Farben immer ausreichen, eine beliebige Landkarte in der Euklidischen Ebene so
einzufärben, dass keine zwei angrenzenden Länder die gleiche Farbe bekommen. Der VierFarben-Satz war das erste große mathematische Problem, das mit Hilfe von Computern
gelöst wurde.
Die folgenden Sätze beantworten ähnliche Probleme der Färbungstheorie und führen auf
ein bis heute ungelöstes Problem:
7
Satz 7. Alle Punkte der Euklidischen Ebene R2 seien mit zwei Farben gefärbt. Dann gibt
es ein gleichseitiges Dreieck, dessen Ecken alle die gleiche Farbe haben.
Beweis. Die Farben seien rot und blau. Wir betrachten ein regelmäßiges Sechseck zusammen
mit seinem Mittelpunkt wie in Abbildung 11 dargestellt. Sei v0 der Mittelpunkt des Sechsecks
und seien v1 , v2 , ..., v6 die im Gegenuhrzeigersinn numerierten Eckpunkte des Sechsecks. OBdA sei v0 rot gefärbt. Sind zwei nebeneinanderliegende Eckpunkte des Sechsecks rot gefärbt
entsteht ein rotes gleichseitiges Dreieck. Daher kann jede rote Ecke nur blaue Nachbarecken
hat. Daraus ergeben sich die folgenden Fälle (siehe Abbildung 11):
1. Fall: Es gibt 3 aufeinanderfolgende blaue Ecken, seien diese v1 , v2 und v3 . Dann gilt: v5
muss rot sein, sonst wäre v1 v3 v5 ein blaues gleichseitiges Dreieck. Daher müssen aber
die Nachbarn von v5 , also v4 und v6 blau sein, wodurch v2 v4 v6 ein blaues gleichseitiges
Dreieck bildet.
2. Fall: Es gibt keine 2 aufeinanderfolgenden blauen Ecken. Dann sind die Ecken des
Sechsecks abwechselnd blau und rot gefärbt, da keine zwei benachbarten Felder blau
oder rot sein können. Nun bilden sowohl die blauen als auch die roten Ecken des
Sechsecks gleichseitige Dreiecke.
3. Fall: Es gibt 2, aber keine 3 aufeinanderfolgenden blauen Ecken. Seien v1 und v2 blau.
Dann müssen v6 und v3 rot sein, da es keine 3 aufeinanderfolgenden blauen Punkte
geben kann. Daraus folgt aber wieder, dass v4 und v5 blau sind. Betrachte nun die
zusätzlichen Punkte v7 und v8 , die sich ergeben, wenn v0 an v2 v3 bzw. v3 v4 gespiegelt
wird. Diese neuen Punkte können nicht blau sein, da sonst v1 v4 v7 bzw. v2 v5 v8 blaue
gleichseitige Dreiecke wären. Sind aber beide Punkte rot, so ergibt v0 v7 v8 ein rotes
gleichseitiges Dreieck.
(a) Sechseck
(b) Fall 1
(c) Fall 2
(d) Fall 3
Abbildung 11: Sechseck und Färbungen in den einzelnen Fällen
8
Satz 8. Alle 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 grün. Angenommen, je zwei Punkte vom Abstand
1 haben verschiedene Farben. Wir betrachten einen beliebigen Punkt v0 der Ebene, oBdA
sei dieser rot gefärbt. Von v0 ausgehend betrachten wir ein gleichseitiges Dreieck v0 v1 v2 der
Seitenlänge 1. Laut Annahme haben v0 , v1 und v2 verschiedene Farben, also sei v1 blau
und v2 grün. Sei v3 der Punkt, der durch Spiegelung von v0 an der Strecke v1 v2 entsteht.
√
Wieder nach Annahme muss v3 rot gefärbt sein. Der Abstand von v0 und v3 beträgt 3.
Da das Dreieck beliebig gewählt werden kann, müssen
√ alle Punkte auf dem in Abbildung 5
dargestellten Kreis mit Mittelpunkt v0 und Radius 3 rot gefärbt sein. Auf diesem Kreis
gibt es aber zwei Punkte mit Abstand 1, was einen Widerspruch zur Annahme ergibt.
Abbildung 12: Kreis mit Radius
√
3 um v0
Nun stellt sich die Frage, wie viele Farben mindestens benötigt werden, um die Ebene so
zu färben, dass keine zwei Punkte mit Abstand 1 die selbe Farbe haben. Das Problem konnte
bis heute nicht gelöst werden, gehört also zu den noch offenen Problemen der Mathematik,
allerdings lässt sich die Lösung auf einen der Werte 4, 5, 6 und 7 einschränken. Dazu verhelfen
Satz 8 und der folgende Satz 9:
Satz 9. Alle Punkte der Ebene können so mit 7 Farben gefärbt werden, dass keine zwei
Punkte mit Abstand 1 die selbe Farbe haben.
Beweis. Der Beweis erfolgt durch Angabe eines Beispiels. Man betrachte eine Überdeckung
der Ebene mit regelmäßigen Sechsecken der Seitenlänge 2/5 (Bienenwaben). Zur Färbung
startet man bei einem beliebigen Sechseck und färbt dieses mit Farbe 1. Nun werden die 6
angrenzenden Sechsecke mit den restlichen 6 Farben gefärbt. Mit diesem aus 7 Sechsecken
bestehenden größeren ”Parkettstein”kann man nun durch Translation wie in Abbildung 13
die gesamte Ebene überdecken. Es ist dabei egal, welche Farbe der Rand
der Sechsecke
√
besitzt, da bei dieser Färbung keine Zahl im offenen Intervall I = (4/5, 28/5) als Abstand
von 2 Punkten derselben Farbe auftritt:
Seien P1 und P2 zwei Punkte derselben Farbe. Dann unterscheiden wir zwei Fälle:
1. Fall: P1 und P2 befinden sich im selben Sechseck. Der Durchmesser des Sechsecks
beträgt 4/5, daher ist der Abstand von P1 und P2 ≤ 4/5
2. Fall: P1 und P2 befinden sich in unterschiedlichen Sechsecken. Klarerweise genügt es bei
der Bestimmung des Mindestabstands von zwei Sechsecken gleicher Farbe, Sechsecke
in benachbarten Parkettsteinen zu betrachten. Bei einer Färbung wie in Abbildung ist
der Abstand von zwei Feldern der gleichen Farbe in zwei benachbarten Parkettsteinen
unabhängig von der ausgewählten Farbe von P1 und P2 und der Auswahl der
√ benachbarten Parkettsteine. Dieser in Abbildung 13 dargestellte Abstand beträgt 28/5, wie
mit Hilfe des Satzes von Pythagoras leicht bestimmt werden kann.
9
√
Also gilt insgesamt: Der Abstand von zwei Punkten ist entweder ≤ 4/5 oder ≥ 28/5, liegt
also nicht in I. Also existieren unabhängig von der Färbung der Ränder der Sechsecke keine
zwei gleichfabigen Punkte mit Abstand 1.
(a) Färbung und Parkettsteine
(b) Minimaler Abstand gleichfarbiger Sechsecke
Abbildung 13: Färbung und Abstandsberechnung
10
© Copyright 2024 ExpyDoc
