Modulare Invarianten

Schubfachprinzip und modulare Invarianten · Abschnitt 55 von 64

Definition

Modularer Invariant

Eine Zustandsgröße ist modulo $m$ invariant, wenn jeder erlaubte Zug ihren Wert um ein Vielfaches von $m$ verändert.

Gelöstes Beispiel

Beide Züge verändern eine Zahl um ein Vielfaches von 3. Der Rest modulo 3 bleibt daher unter beliebig vielen Zügen erhalten.

Gelöstes Beispiel

Bei Schritten $(2,1)$ und $(1,2)$ wächst $x+y$ stets um 3. Die Koordinatensumme modulo 3 ist ein Invariant.

Achtung

Verschiedene Invariantenreste beweisen Unerreichbarkeit. Gleiche Reste garantieren umgekehrt noch keine Zugfolge.