Erreichbarkeits-Training

Eine Zahl darf modulo 4 jeweils um 2 verändert werden. Zeichne den Zustandsgraphen und bestimme seine Zusammenhangskomponenten.

Begründe allgemein: Sind alle Züge umkehrbar, dann ist Erreichbarkeit symmetrisch und zerlegt den Zustandsraum in Zusammenhangskomponenten.

Eine positive ganze Zahl darf vorwärts entweder verdoppelt oder um 1 erhöht werden. Welche möglichen unmittelbaren Vorgänger hat das Ziel 20?

Eine Zahl startet bei 1 und darf verdoppelt oder um 1 erhöht werden. Finde eine Zugfolge mit möglichst wenigen Zügen zu 10 und beweise ihre Minimalität.

Auf zwei Haufen ist nur der umkehrbare Zug $(a,b)\leftrightarrow(a+2,b-2)$ erlaubt. Erkläre, warum die Zustände mit fester Summe noch in mehrere Erreichbarkeitsklassen zerfallen.

Für ganzzahlige Paare ist der Zug $(a,b)\leftrightarrow(a+2,b-2)$ erlaubt. Beweise: Zwei Zustände sind genau dann verbunden, wenn ihre Summen und die Parität ihrer ersten Koordinaten übereinstimmen.

Auf der Zustandsmenge $\{0,1,2,3\}$ ist nur der Zug $x\mapsto x+1$ erlaubt, solange das Ergebnis höchstens 3 ist. Warum ist die ungerichtete Zusammenhangskomponente keine korrekte Erreichbarkeitsklasse?

Jemand behauptet beim Zug $(a,b)\leftrightarrow(a+4,b-4)$: „Gleiche Summe charakterisiert Erreichbarkeit.“ Widerlege die Behauptung und verbessere sie zu einer Genau-dann-wenn-Aussage.