Hex

Hex wird auf einem rautenförmigen Spielbrett $B$ gespielt (vgl. Applet unten). Die Randfelder links und rechts sind weiß, die unten und oben schwarz. Die eigentlichen Spielfelder sind zunächst grau. Im Spiel färben die Spieler abwechselnd je ein noch graues Feld weiß beziehungsweise schwarz. Gewonnen hat, wer zuerst einen durchgehenden Weg in seiner Farbe zwischen den Seiten seiner Farbe erzeugt hat. Das Spiel endet unentschieden, falls alle Felder schwarz oder weiß gefärbt sind und keiner der Spieler gewonnen hat.

Ziel ist es zu beweisen, dass dies nicht auftritt. Dazu nehmen wir an, dass $B$ vollständig gefärbt ist und konstruieren folgende Neufärbung von $B$:

Alle Felder die schwarz sind und vom unteren Rand über schwarze Felder erreichbar sind, färben wir rot. Alle Felder, die weiß sind und vom linken Rand über weiße Felder erreichbar sind, färben wir grün. Alle übrigen Felder färben wir blau. Außerdem konstruieren wir zwischen den Ecken $V$ und den Kanten $K$ der Felder von $B$ folgende Relation $R\subset V\times K$: Für $v\in V$ und $k\in K$ gelte $v \sim_R k$ genau dann, wenn $v$ Endpunkt von $k$ ist und $k$ zwischen einem roten und einem grünen Feld verläuft.

• Zeigen Sie, dass für jede Kante $k\in K$ gilt, dass $|\{v\in V:v \sim_R k\}|$ gerade ist.
• Zeigen Sie, dass es bei einem Unentschieden genau eine Ecke $v\in V$ gibt, für die $|\{k\in K:v \sim_R k\}|$ ungerade ist.
• Schlussfolgern Sie, dass ein Unentschieden bei Hex nicht auftreten kann.

Im nachfolgenden Applet kann man das Spielbrett über das “Spielende” hinaus weiter colorieren. Damit erhält man eine vollständige Färbung, von welcher in der obigen Aufgabe ausgegangen wird:

Hex.cdy (Dieses Applet kann in Cinderella ausgeführt werden.)