Das Spernersche Lemma
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
Title |
| |
Alternative Title |
| |
Author | ||
License | No Open Access License: German copyright law applies. This film may be used for your own use but it may not be distributed via the internet or passed on to external parties. | |
Identifiers | 10.3203/IWF/D-1504 (DOI) | |
IWF Signature | D 1504 | |
Publisher | ||
Release Date | ||
Language | ||
Producer | ||
Production Year | 1982 |
Technical Metadata
IWF Technical Data | Film, 16 mm, LT, 108 m ; F, 10 min |
Content Metadata
Subject Area | |||||
Genre | |||||
Abstract |
| ||||
Keywords |
| ||||
IWF Classification |
|
00:11
EckeSchnittpunktSierpinski triangle
01:05
Ecke
01:26
EckeSierpinski triangle
03:09
EckeLinieSierpinski triangleTrail
07:56
Sierpinski triangle
09:05
Mathematics
Transcript: German(auto-generated)
00:18
Zwei Kinder spielen hier ein Brettspiel.
00:22
Worum geht es dabei? Zunächst sehen wir, das Spielfeld, ein großes rotes Dreieck, ist durch schwarze Linien in kleine Dreiecke unterteilt. Die Kinder setzen abwechselnd blaue, gelbe oder schwarze Steine auf die Schnittpunkte dieser Linien.
00:41
Was ist das Ziel dabei? Jeder Spieler versucht seine Steine so zu legen, dass kein Dreieck entsteht, das alle drei Farben, blau, gelb und schwarz, an den Ecken hat. Derjenige, der als Erster ein solches Dreieck bildet, hat verloren. Wir sehen, wie vorsichtig die Kinder setzen.
01:02
Je mehr Steine auf dem Brett stehen, desto länger müssen die Kinder überlegen. In dieser Stellung entsteht nun ein Dreieck mit den Ecken blau, gelb und schwarz.
01:21
Wir nennen es kurz vollständig gefärbtes Dreieck. Welches sind die Regeln des Spiels? Die Ecken des Dreiecks müssen unterschiedlich gefärbt sein. Für die Seiten dazwischen dürfen nur die Farben der zugehörigen Ecken verwendet werden. Also hier nur schwarze und gelbe Steine.
01:48
Die Anordnung der Steine auf der jeweiligen Seite ist dabei beliebig.
02:06
Im Inneren des Spielfeldes sind nun keine weiteren Regeln mehr zu beachten. Hier dürfen Steine aller drei Farben völlig beliebig gesetzt werden. Die beiden Kinder spielen nun das Spiel weiter, indem sie abwechselnd Steine beliebiger Farben auf die noch freien Punkte setzen.
02:28
Noch sehen wir kein vollständig gefärbtes Dreieck auf dem Brett. Es wird immer schwieriger, ein solches vollständig gefärbtes Dreieck zu vermeiden.
03:01
Da ist es passiert. Ein vollständig gefärbtes Dreieck ist entstanden. Der rechte Spieler hat verloren. Muss nun immer ein Spieler verlieren. Das ist in der Tat der Fall. Diese Aussage ist die entscheidende Aussage des Spernerschen Lemmas. Hier wieder unser Spielfeld.
03:22
Ein großes Dreieck, dessen Ecken mit den Farben blau, gelb und schwarz versehen sind. Die Seiten zwischen je zwei solcher Ecken besitzen nur die Farben dieser Ecken.
03:40
Im Inneren des großen Dreiecks darf ganz beliebig mit allen drei Farben gefärbt werden. Unter diesen Voraussetzungen, so die Behauptung des Spernerschen Lemmas, existiert mindestens ein, genauer, ungerade viele vollständig gefärbte Teildreiecke.
04:01
Wie in unserem Beispiel dieses hier. Wie können wir dies einsehen? Wir entwerfen ein Verfahren, mit dem man vollständig gefärbte Dreiecke findet.
04:22
Dazu betrachten wir uns zunächst die untere Seite und fragen nach der Anzahl der blau-gelb Übergänge. Es gibt ungerade viele, denn wandert man auf der Zickzacklinie vom linken zum rechten Ende, so wird dabei die weiße Linie ungerade oft überschritten, in unserem Beispiel fünfmal.
04:51
Bei unserem Beweisverfahren konstruieren wir Wege von einem Teil Dreieck zum anderen nach folgender Regel. Es dürfen nur solche Seiten überquert werden, deren eines Ende blau und deren anderes gelb ist.
05:10
Diese Seiten können wir uns gewissermaßen durchlässig vorstellen. Gestartet wird jeder Weg am unteren Rand des großen Dreiecks, und zwar ebenfalls auf einer blau-gelben Seite.
05:31
Durch unsere Konstruktionsregel und den Anfangspunkt ist also der Verlauf eines jeden Weges eindeutig festgelegt. Kann ein Weg fortgesetzt werden, so muss neben der blau-gelb begrenzten Anfangsseite eine weitere blau-gelbe Seite im Teil Dreieck vorhanden sein.
05:46
Das heißt, der dritte Eckpunkt muss entweder gelb oder blau sein.
06:05
Wird hierbei wirklich mindestens ein Weg in einem vollständig gefärbten Dreieck enden? Der erste Weg ist es nicht. Er kehrt an den unteren Rand zurück. Der zweite Weg hingegen endet in einem vollständig gefärbten Dreieck. Ebenso der dritte. Und der vierte.
06:34
Jeder Weg, der nicht an den unteren Rand zurückführt, endet hier in einem vollständig gefärbten Dreieck.
06:45
Warum ist das so? Kein Weg kann wegen der fehlenden Gelb- bzw. Blaufärbung das große Dreieck über eine dieser beiden Seiten verlassen.
07:04
Außerdem kann kein Weg in einen anderen einmünden, also auch keine solche Schleife auftreten, da ein solches Teil Dreieck keine drei blau-gelben Seiten besitzen kann.
07:27
Ein Weg, der nicht an den unteren Rand zurückkehrt, muss aus diesen Gründen und weil er wegen der endlichen Anzahl der Eckpunkte auch nur endlich viele blau-gelbe Seiten überschreiten kann, innerhalb des großen Dreiecks enden.
07:45
Für das Ende des Weges kommt aber nur ein vollständig gefärbtes Dreieck in Frage. Erinnern wir uns. Es gab ungeradzahlig viele blau-gelbe Seiten auf dem unteren Rand des Dreiecks, also ungeradzahlig viele Startmöglichkeiten.
08:09
Davon werden geradzahlig viele für die rückkehrenden Wege verbraucht. Es bleiben also ungeradzahlig viele Wege übrig, die nicht an den unteren Rand zurückkehren, also in einem vollständig gefärbten Dreieck enden.
08:28
Das heißt, es existiert eine ungerade Anzahl von vollständig gefärbten Dreiecken.
08:41
Es ist nicht weiter tragisch, dass unser Verfahren unter Umständen nicht alle vollständig gefärbten Dreiecke findet. Diese restlichen treten in Paaren auf. Sie sind jeweils durch einen Weg miteinander verbunden.