Invarianten

Eine Invariante ist eine Eigenschaft, die durch keinen erlaubten Spielzug verändert wird. Verschiebe die Kacheln des Puzzles, schneide Felder aus dem Brett oder füge in Königsberg Brücken hinzu. Die Seite zeigt dir dabei stets die Invariante: die Parität der Fehlstände, schwarze gegen weiße Felder oder die Landmassen mit einer ungeraden Anzahl an Brücken. Wenn sie sich zwischen Start und Ziel unterscheidet, führt keine Abfolge von Zügen dorthin.

Rechenbeispiel — Invarianten

Fehlstände	1
Die Invariante: Fehlstände mod 2	ungerade
Züge bis zur Lösung	unerreichbar

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Invarianten

Eine Invariante ist eine Größe, die durch keinen erlaubten Zug verändert wird. Hat sie zu Beginn einen bestimmten Wert und am Ziel einen anderen, ist das Ziel unerreichbar. Dabei ist völlig egal, welche Züge du versuchst, und du musst nichts ausprobieren, um das sicher zu wissen.

Was die einzelnen Symbole bedeuten

I: die Invariante: hier die Parität der Fehlstände, die Differenz zwischen schwarzen und weißen Feldern oder die Anzahl der Landmassen mit einer ungeraden Brückenzahl
d(v): der Grad einer Landmasse v: wie viele Brücken dort enden

Woher die Formel kommt

Warum ein Zug die Parität bewahrt. Lies die acht Kacheln zeilenweise ab und ignoriere dabei die Lücke. Ein seitlicher Zug verändert diese Reihenfolge überhaupt nicht. Ein Zug nach oben oder unten verschiebt eine Kachel um drei Plätze. Sie zieht an den beiden Kacheln vorbei, die zwischen ihrem alten und neuen Platz liegen. Jedes dieser beiden Paare gewinnt oder verliert einen Fehlstand. Die Gesamtzahl ändert sich also um −2, 0 oder +2, aber niemals um einen ungeraden Wert. Die gelöste Stellung hat 0. Daher ist eine Position mit einer ungeraden Anzahl unerreichbar. Dass jede Stellung mit einer geraden Anzahl tatsächlich erreichbar ist, stellt den schwierigeren Teil dar. Für das 8-Puzzle zeigt die Suche auf dieser Seite genau das.
Warum ein Dominostein die Differenz bewahrt. Auf einem Schachbrett haben die Nachbarn jedes Feldes die jeweils andere Farbe. Ein Dominostein bedeckt zwei benachbarte Felder, also ein schwarzes und ein weißes. Das Auslegen von Dominosteinen ändert deshalb niemals die Differenz zwischen den verbleibenden schwarzen und weißen Feldern. Eine fertige Parkettierung lässt nichts unbedeckt und hat somit eine Differenz von 0. Sie benötigt daher von Beginn an eine Differenz von 0: exakt gleich viele Felder der einen wie der anderen Farbe.
Warum höchstens zwei ungerade Landmassen. Folge dem Weg. Jedes Mal, wenn er eine Landmasse passiert, kommt er über eine Brücke an und verschwindet über eine andere. Die Brücken an einer Landmasse werden also in Paaren genutzt. Ausnahmen bilden nur der Start, wo eine beim Verlassen genutzt wird, und das Ende, wo eine bei der Ankunft dient. Endet der Weg dort, wo er begann, hat jede Landmasse eine gerade Anzahl an Brücken. Andernfalls weisen genau der Start und das Ende eine ungerade Anzahl auf. Die Umkehrung gilt ebenfalls, wenn die Brücken alles miteinander verbinden. Die Seite findet den Weg, indem sie ihn in Schleifen aufbaut und diese aneinanderfügt.

Die Hälfte eines 3 × 3-Schiebepuzzles kann niemals erreicht werden, und du kannst ohne Suchen erkennen, welche Hälfte das ist 🖖

Klick auf 7 und 8 getauscht und versuche, es zu lösen. Zähle die Kachelpaare, die in der falschen Reihenfolge stehen, zeilenweise gelesen: hier eines, die 8 vor der 7. Ein seitlicher Zug verändert diese Zahl nicht. Ein Zug nach oben oder unten führt eine Kachel an zwei anderen vorbei und ändert die Anzahl so um 0 oder 2. Die Zahl bleibt also für immer ungerade, während die gelöste Stellung 0 aufweist. Diese Seite hat auch alle Positionen ausgehend von der Lösung durchsucht. 181.440 der 362.880 Anordnungen sind erreichbar, exakt diejenigen mit einer geraden Anzahl. Die zwei am weitesten entfernten benötigen 31 Züge. Das 15-Puzzle eroberte 1880 Amerika. In den 1890er Jahren bot Sam Loyd 1.000 $ für das Rückgängigmachen eines Tauschs von 14 und 15. Niemand konnte diesen Preis jemals gewinnen.

Schneide zwei gegenüberliegende Ecken eines Schachbretts ab, und keine Dominoparkettierung überlebt 🖖

Klick auf Gegenüberliegende Ecken. Das gesamte Brett lässt sich mit 32 Dominosteinen auf 12.988.816 Arten bedecken. Schneide zwei gegenüberliegende Ecken ab, und es lässt sich überhaupt nicht mehr belegen. Beide Ecken haben die gleiche Farbe. Es verbleiben also 30 Felder der einen Farbe gegen 32 der anderen, und jeder Dominostein bedeckt von jeder Farbe eines. Schneide stattdessen die beiden Ecken an den Enden einer Kante ab, also eine von jeder Farbe. Nun gibt es 2.436.304 Parkettierungen. Klick dann auf Abgesperrte Ecke: 30 und 30, perfekt ausgeglichen, und dennoch gibt es keine. Das Eckfeld hat nämlich keinen Nachbarn mehr. Die Farbzählung kann die Unmöglichkeit eines Bretts beweisen. Sie kann aber niemals beweisen, dass es möglich ist.

Der Königsberger Rundgang scheitert an einer Rechnung, die du im Kopf lösen kannst 🖖

Klick auf Königsberg. Die Insel hat 5 Brücken und jede der drei anderen Landmassen hat 3. Ein Weg, der jede Brücke einmal überquert, erreicht und verlässt jede passierte Landmasse. Er nutzt ihre Brücken also in Paaren. Nur dort, wo der Weg beginnt und wo er endet, darf eine übrig bleiben. Höchstens zwei Landmassen dürfen also eine ungerade Anzahl aufweisen, und hier haben das alle vier. Euler klärte dies in einer Arbeit aus dem Jahr 1735. Füge eine Brücke zwischen den beiden Ufern hinzu, mit dem + neben B–C. Zwei ungerade Landmassen bleiben übrig, und die Seite findet den Weg von A nach D. Die vier Anzahlen ergeben zusammen immer das Doppelte der Brückenzahl. Darum treten die ungeraden Werte stets paarweise auf.

Aufgabe vollständig gelöst

Konnte jemand Sam Loyds 1.000 $ gewinnen? 4 Schritte
Tausche auf dem 4 × 4-Brett nur die 14 und 15 und belasse die Lücke in ihrer Ecke. Sam Loyd bot jedem 1.000 $, der das Puzzle wieder in den gelösten Zustand schieben konnte. War das überhaupt möglich?

Öffne diese Aufgabe im Tool
1. Auf dem 3 × 3-Brett dieser Seite war die Invariante die Parität der Fehlstände:
  
  $3 wide: a vertical slide passes 2 tiles \Rightarrow Δ I \in {- 2, 0, + 2}$
2. Auf einem vier Felder breiten Brett führt ein Zug nach oben oder unten eine Kachel an drei anderen vorbei. Die Anzahl ändert sich also um einen ungeraden Wert, und die Lücke wechselt die Zeile:
  
  $4 wide: a vertical slide passes 3 tiles \Rightarrow Δ I \in {- 3, - 1, + 1, + 3}, Δ row = \pm 1$
3. Jeder Zug ändert entweder beide Paritäten oder keine von beiden. Ihre Summe, modulo 2 genommen, ändert sich also nie:
  
  $I + row of the blank (mod 2) never changes$
4. Vergleiche die beiden Positionen, wobei sich die Lücke bei beiden in Zeile 4 befindet:
  
  $solved: 0 + 4 = 4 (even), 14 \leftrightarrow 15 : 1 + 4 = 5 (odd)$
Antwort

Niemand konnte gewinnen: Der Tausch liegt auf der falschen Seite der Invariante. Genau die Hälfte der 16! Anordnungen, 10.461.394.944.000, ist von der Lösung aus erreichbar. Klick auf 7 und 8 getauscht für die 3 × 3-Version der gleichen Falle.

$unreachable; \frac{16 !}{2} = 10, 461, 394, 944, 000 arrangements can be reached$

Lernpfad

Beweismethoden

Quellen (3)

The parity argument for the 15-puzzle, the history (made in upstate New York in the 1870s, a craze in early 1880, analysed in the American Journal of Mathematics that year) and Sam Loyd's later $1,000 prize for a swap that cannot be done: K. Conrad, "The 15-Puzzle (and Rubik's Cube)", expository notes, University of Connecticut.
Euler's paper on the seven bridges of Königsberg, which reduced the walk to the number of bridges at each land mass: L. Euler, "Solutio problematis ad geometriam situs pertinentis", Commentarii academiae scientiarum Petropolitanae 8, 128–140 (written 1735, published 1741); Eneström number E53, The Euler Archive.
The number of domino tilings of square boards, with 12,988,816 for the 8 × 8 chessboard: OEIS Foundation, "A004003: Number of domino tilings (or dimer coverings) of a 2n X 2n square", The On-Line Encyclopedia of Integer Sequences.

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.