We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Das Spernersche Lemma

00:00

Formal Metadata

Title
Das Spernersche Lemma
Alternative Title
The Sperner Lemma
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
IWF SignatureD 1504
Publisher
Release Date
Language
Producer
Production Year1982

Technical Metadata

IWF Technical DataFilm, 16 mm, LT, 108 m ; F, 10 min

Content Metadata

Subject Area
Genre
Abstract
German
German
Voraussetzungen und Aussage des Spernerschen Lemmas für den zweidimensionalen Fall werden in einem Brettspiel veranschaulicht. Im Trick werden die für das Lemma wesentlichen, vollständig bewerteten (gefärbten) Dreiecke nach dem Scarf-Algorithmus aufgesucht, und in dem folgenden operativen Beweis wird die Aussage des Spernerschen Lemmas verifiziert.
English
English
Conditions and message of the Sperner Lemma for the two dimensional case are demonstrated in a board game. In a trick film the (coloured) triangles for the most part fully valuated for the Lemma, are sought in accordance with the Scarf-Algorithm and the statement of the Sperner Lemma verified in the following operative proof.
Keywords
German
German
English
English
IWF Classification
German
German
English
English
EckeSchnittpunktSierpinski triangle
Ecke
EckeSierpinski triangle
EckeLinieSierpinski triangleTrail
Sierpinski triangle
Mathematics
Transcript: German(auto-generated)
Zwei Kinder spielen hier ein Brettspiel.
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.
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.
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.
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.
Die Anordnung der Steine auf der jeweiligen Seite ist dabei beliebig.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Das heißt, der dritte Eckpunkt muss entweder gelb oder blau sein.
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.
Jeder Weg, der nicht an den unteren Rand zurückführt, endet hier in einem vollständig gefärbten Dreieck.
Warum ist das so? Kein Weg kann wegen der fehlenden Gelb- bzw. Blaufärbung das große Dreieck über eine dieser beiden Seiten verlassen.
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.
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.
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.
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.
Das heißt, es existiert eine ungerade Anzahl von vollständig gefärbten Dreiecken.
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.