Klassifikations-Training

Auf $\mathbb Z^2$ sind die umkehrbaren Züge $(\pm2,0)$ und $(0,\pm3)$ erlaubt. Charakterisiere alle von $(0,0)$ erreichbaren Punkte.

Erlaubt sind auf $\mathbb Z^2$ die umkehrbaren Züge $(1,1)$ und $(1,-1)$. Zeige, dass $(x,y)$ genau dann von $(0,0)$ erreichbar ist, wenn $x+y$ gerade ist.

Auf der Zahlengeraden sind umkehrbare Schritte der Längen 6 und 9 erlaubt. Welche ganzen Zahlen sind von 0 aus erreichbar?

Auf $\mathbb Z$ ist der umkehrbare Zug $x\leftrightarrow x+5$ erlaubt. Zeige, dass jeder Zustand genau eine Normalform in $\{0,1,2,3,4\}$ besitzt.

Auf einem Weg mit $n\ge2$ Lampen schaltet ein Zug zwei benachbarte Lampen um. Start ist „alle aus“. Beweise: Genau die Muster mit gerader Anzahl angeschalteter Lampen sind erreichbar.

Auf drei Haufen mit nichtnegativen Größen darf ein Stein zwischen benachbarten Haufen in beide Richtungen verschoben werden. Charakterisiere die von $(a,b,c)$ erreichbaren Zustände.

Auf $\mathbb Z^2$ sind die umkehrbaren Züge $(2,1)$ und $(1,2)$ erlaubt. Beweise: $(x,y)$ ist genau dann von $(0,0)$ erreichbar, wenn $x+y$ durch 3 teilbar ist.

Formuliere eine belastbare Checkliste für eine Genau-dann-wenn-Charakterisierung von Erreichbarkeit und erläutere die Rolle der Invariante.