Kapitel 10Fortgeschritten25 Min.
Eine Invariante finden und beweisen
Zustände und Paritätsinvarianten · Abschnitt 38 von 60
Checkliste
Was kannst du messen? (Kandidaten)
Summe oder Differenz aller Zahlen
Anzahl markierter, leuchtender oder umgedrehter Dinge
Parität einer Teilmenge oder Farbklasse
Koordinatensumme oder Abstand modulo 2
Entscheidungsweg
Vom Zug zum Beweis – dein Plan
- 1
Welche Daten ändert ein Zug?
- 2
Wie ändert sich dein Kandidat in jedem möglichen Fall?
- 3
Ist die Änderung immer gerade? → Parität bleibt.
- 4
Start und Ziel verschieden? → Ziel unmöglich.
Typischer Fehler
Nicht nur die „typischen“ Züge prüfen
Eine Invariante muss bei jeder erlaubten Zugart und in jedem lokalen Fall halten. Ein einziges Gegenbeispiel (z. B. ein seltener Zug) macht den ganzen Beweis kaputt.