Grundsatz: Bei Zustandsrätseln bringt man Gegenstände oder Personen nach festen Regeln von einem Ort an einen anderen und soll es mit den wenigsten Zügen schaffen. Der Trick: Behandle jede Anordnung als Zustand und jede erlaubte Handlung als Zug. Das Rätsel ist gelöst, wenn du vom Anfangszustand über erlaubte Züge zum Zielzustand kommst. Der kürzeste Weg ist die Lösung.
Vorgehen
- Zustand beschreiben: Wer oder was befindet sich wo? (Bei einem Fährmann mit $n$ Gegenständen gibt es $2^{n+1}$ Anordnungen, denn der Fährmann und jeder Gegenstand sind je an einem von zwei Ufern.)
- Verbotene Zustände streichen: Anordnungen, in denen eine Regel verletzt wird, sind ausgeschlossen.
- Erlaubte Züge verbinden und den kürzesten Weg suchen. Rückwärtszüge sind erlaubt und oft nötig: Manchmal muss man etwas zurückbringen, um weiterzukommen.
- Kontrollieren: Prüfe nach jedem Zug den neuen Zustand, und zwar auch das Ufer, das du zurücklässt.
Hilfreiche Beobachtung bei Verbotsregeln: Ein Gegenstand, der in zwei Verbotspaaren vorkommt, darf mit keinem der anderen Gegenstände allein bleiben. Bei der ersten Fahrt bleiben aber zwei Gegenstände zurück. Prüfe darum, welche Paare dabei erlaubt wären, und nimm den Gegenstand mit, ohne den das Zurückbleiben erlaubt ist.
Ausgearbeitetes Beispiel 1: Türme von Hanoi
Drei Stäbe, Scheiben verschiedener Grösse. Es darf nur eine Scheibe pro Zug bewegt werden, nie eine grössere auf eine kleinere. Ziel: den ganzen Turm von Stab A nach Stab C bringen. Gesucht ist die minimale Zugzahl für 3 Scheiben ($S_1$ klein bis $S_3$ gross).
Idee: Um die grösste Scheibe zu bewegen, müssen alle anderen auf dem Hilfsstab liegen. Man verschiebt also den Teilturm aus 2 Scheiben nach B, dann die grösste Scheibe nach C, dann den Teilturm von B nach C.
- 2 Scheiben brauchen 3 Züge (kleine Scheibe zur Seite, grössere ans Ziel, kleine darauf).
- Also für 3 Scheiben: $3 + 1 + 3 = 7$ Züge.
Allgemein ist die minimale Zugzahl für $n$ Scheiben das Doppelte der Zahl für $n-1$ Scheiben plus 1:
$$z_n = 2 \cdot z_{n-1} + 1$$
Daraus folgt:
$$z_n = 2^n - 1$$
Die Folge lautet 1, 3, 7, 15, 31, 63, … Die Scheibe $S_k$ (von klein nach gross gezählt) wird genau $2^{n-k}$-mal bewegt: bei 3 Scheiben die kleinste $2^{2} = 4$-mal, die mittlere zweimal, die grösste genau einmal.
Ausgearbeitetes Beispiel 2: Brücke mit Taschenlampe
Vier Personen müssen bei Nacht über eine Brücke. Es gibt nur eine Lampe, höchstens zwei gehen gleichzeitig, und die Lampe muss immer mitgetragen werden. Zwei gemeinsam gehen so schnell wie der Langsamere. Zeiten: 1, 3, 6 und 7 Minuten.
Naheliegend: Der Schnellste begleitet alle: $3 + 1 + 6 + 1 + 7 = 18$ Minuten.
Besser: Die beiden Langsamsten gehen zusammen, sodass ihre Zeiten nicht doppelt anfallen.
- 1 und 3 gehen hinüber: 3 Minuten.
- 1 kehrt zurück: 1 Minute.
- 6 und 7 gehen hinüber: 7 Minuten.
- 3 kehrt zurück: 3 Minuten.
- 1 und 3 gehen hinüber: 3 Minuten.
Summe: $3 + 1 + 7 + 3 + 3 = 17$ Minuten.
Für vier Personen mit Zeiten $a \le b \le c \le d$ vergleichst du zwei Pläne: Plan 1 (der Schnellste begleitet jeden) braucht
$$2a + b + c + d$$
Plan 2 (die zwei Langsamsten gehen zusammen) braucht
$$a + 3b + d$$
Der kleinere Wert ist das Minimum. Bei drei Personen ($a \le b \le c$) begleitet der Schnellste erst die zweite Person, kehrt zurück und begleitet die dritte: $a + b + c$ ist das Minimum. Typischer Fehler: die langsamsten Personen einzeln begleiten, statt sie gemeinsam gehen zu lassen.
Ausgearbeitetes Beispiel 3: Zwei Messbehälter
Zwei Behälter fassen 5 und 3 Liter und haben keine Skala. Erlaubte Schritte (jeder zählt als ein Zug): einen Behälter ganz füllen, einen Behälter ganz leeren, von einem in den anderen giessen, bis der Empfänger voll oder der Spender leer ist. Gesucht: genau 1 Liter in einem Behälter, mit möglichst wenigen Schritten.
Zustand = (Inhalt 5-Liter-Behälter, Inhalt 3-Liter-Behälter). Start (0, 0).
- 3-Liter-Behälter füllen: (0, 3).
- In den 5-Liter-Behälter giessen: (3, 0).
- 3-Liter-Behälter füllen: (3, 3).
- In den 5-Liter-Behälter giessen, bis er voll ist: (5, 1).
Nach 4 Schritten liegt genau 1 Liter im kleinen Behälter. Weniger geht nicht: Schreibt man alle Zustände nach 1, 2 und 3 Schritten auf, kommt keiner mit 1 Liter vor. Dieses systematische Aufschreiben der Zustände nach jeder Schrittzahl beweist die Minimalität.
Welche Mengen lassen sich mit zwei Messbehältern abmessen?
Bei den Messbehältern lohnt sich vor dem Probieren eine Überlegung: Füllen füllt bis zum Rand, Leeren bis auf null, Umgiessen bis zum Rand oder bis zur Leere. Alle diese Schritte erzeugen nur Mengen, die sich aus den beiden Fassungsvermögen durch Addieren und Subtrahieren bilden lassen. Haben beide Behälter einen gemeinsamen Teiler, sind alle erreichbaren Mengen Vielfache dieses Teilers. Der grösste gemeinsame Teiler (ggT) der beiden Fassungsvermögen ist der kleinste messbare Schritt. Alle Vielfachen des ggT bis zur Grösse des grösseren Behälters lassen sich abmessen.
Beispiel: Behälter mit 10 und 4 Litern. Der ggT ist 2. Messbar sind 2, 4, 6, 8 und 10 Liter, aber nie 3, 5, 7 oder 9 Liter. Mit 10 und 3 Litern ist der ggT 1, also lässt sich jede ganze Menge bis 10 Liter messen.
Typischer Fehler: stundenlang weiterprobieren, obwohl die gesuchte Menge gar nicht erreichbar ist. Prüfe zuerst, ob die Menge ein Vielfaches des ggT ist. Ist sie es, suche mit der Zustandsliste den kürzesten Weg.
Typische Fehler
- Eine Fahrt zurück als «Rückschritt» vermeiden, obwohl sie nötig ist.
- Beim Prüfen der Regeln nur das Ufer ansehen, auf das man fährt, nicht das zurückgelassene.
- Eine Lösung nach dem ersten Erfolg übernehmen, ohne zu prüfen, ob es kürzer geht.