Add to Watchlist

Das Spernersche Lemma

214 views

Citation of segment
Purchasing a DVD Granting licences Cite video

Automated Media Analysis

Beta
Recognized Entities
Speech transcript
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, daß 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 den jeweiligen Seiten 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. Muß 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 solchen Ecken besitzen nur die Farben dieser Ecken. Im Inneren des großen Dreiecks darf 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 zunächst die untere Seite und fragen nach der Anzahl der Blau-Gelb-Übergänge. Es gibt ungerade viele; denn. . . wandert man auf der Zick-Zack-Linie 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 Teildreieck 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 muß neben der blau-gelb begrenzten Anfangsseite eine weitere blau-gelbe Seite im Teildreieck vorhanden sein, d. h. der dritte Eckpunkt muß 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 Teildreieck keine drei
blau-gelben Seiten besitzen kann. Ein Weg, der nicht an den unteren Rand zurückkehrt, muß aus diesen Gründen, und weil er wegen der endlichen Anzahl der Eckpunkte auch nur endlich viele Blau-Gelb-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; d.h., es existiert eine ungerade Anzahl von vollständig gefärbten Dreiecken. Es ist nicht weiter tragisch, daß unser Verfahren unter Umständen nicht alle vollständig gefärbten Dreiecke findet. Die restlichen treten in Paaren auf. Sie sind jeweils durch einen Weg miteinander verbunden.
Computer animation
Schnittpunkt
Sierpinski triangle
Meeting/Interview
Triangle
Ecke
Meeting/Interview
Sierpinski triangle
Computer animation
Triangle
Ecke
Sierpinski triangle
Computer animation
Ecke
Triangle
Trail
Sierpinski triangle
Computer animation
Triangle
Linie
Trail
Sierpinski triangle
Computer animation
Triangle
Mathematics
Sierpinski triangle
Computer animation
Mathematics
Triangle

Metadata

Formal Metadata

Title Das Spernersche Lemma
Alternative Title The Sperner Lemma
Author Dröge, Walter
Göttlich, Helmut
Wille, Friedrich
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.
DOI 10.3203/IWF/D-1504
IWF Signature D 1504
Publisher IWF (Göttingen)
Release Date 1983
Language German
Producer Gesamthochschule Kassel, Interdisziplinäre Arbeitsgruppe Mathematisierung
IWF
Production Year 1982

Technical Metadata

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

Content Metadata

Subject Area Mathematics
Abstract 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.
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 Topologie
Beweis, operativer
Scarf-Algorithmus
Dreieck, vollständig bewertetes
Triangulierung
Spernersches Lemma
Sperner's lemma
triangulation
triangle
Scarf's Algorithm
topology

Recommendations

Loading...
Feedback
AV-Portal 3.5.0 (cb7a58240982536f976b3fae0db2d7d34ae7e46b)

Timings

  410 ms - page object