Zustand, Zug und Messgröße
Zustände und Paritätsinvarianten · Abschnitt 37 von 60
Intuition
Der Fingerabdruck, der bleibt
Stell dir vor, du darfst Lampen umschalten, Münzen drehen oder Zahlen ändern. Es gibt so viele mögliche Zustände, dass du sie nie alle durchprobieren willst.
Trick: Finde eine Messgröße, die bei jedem erlaubten Zug gleich bleibt. Dann können Start und Ziel nur dann zusammenpassen, wenn sie denselben Fingerabdruck haben.
Definition
Invariante
Eine Größe oder Eigenschaft heißt invariant, wenn sie durch keinen erlaubten Zug verändert wird.
Oft bleibt nicht der genaue Wert – sondern nur die Parität (gerade/ungerade) oder ein Rest modulo 2.
Gelöstes Beispiel
Beispiel: Zwei Lampen umschalten
Regel. In einem Zug schaltest du genau zwei Lampen um.
Messgröße. Anzahl leuchtender Lampen.
Wirkung. Die Anzahl ändert sich um , oder – immer gerade.
Invariante. Die Parität der Anzahl leuchtender Lampen bleibt gleich. Startest du mit 0 leuchtenden, kannst du nie genau 1 leuchtende haben.
Achtung
Zustand ≠ Messgröße
Die Invariante ist nur ein Fingerprint, nicht das ganze Foto. Viele verschiedene Lampenmuster können dieselbe gerade Anzahl leuchtender Lampen haben. Gleiche Invariante heißt: „noch möglich“ – nicht „schon bewiesen“.