Probleme in Parität übersetzen

Erkennungssignale und Problemübersetzung · Abschnitt 6 von 60

Strategie

Die Drei-Zeilen-Übersetzung

Zustand: Welche Zahl, Anzahl oder Farbe beobachte ich?
Operation: Bleibt ihre Parität bei jedem erlaubten Schritt gleich – oder wechselt sie?
Ziel: Hat das Ziel dieselbe Parität wie der Start – oder eine andere?

Gelöstes Beispiel

Beispiel: Münzen umdrehen

Aufgabe. Anfangs liegen 12 Münzen mit der Zahl nach oben. In jedem Zug drehst du genau zwei Münzen um. Kann am Ende genau eine Münze Kopf zeigen?

Übersetzung in drei Zeilen.

Zustand: Anzahl der Köpfe.
Operation: Ein Zug ändert diese Anzahl um $-2$ , $0$ oder $2$ – die Parität bleibt also gerade.
Ziel: 1 Kopf ist ungerade – und damit unerreichbar.

Antwort. Nein.

Typische Operationen und ihre Wirkung

Was du tust	Was mit der Parität passiert
$+1$ oder $-1$	wechselt
$+2$ , $-2$ , $+4$ , …	bleibt
mit 2 multiplizieren	wird gerade
zwei Lampen/Schalter umlegen	Anzahl leuchtender ändert sich gerade
aufs Nachbarfeld gehen	Farbe wechselt (beim Schachbrett)