Koordinaten als Färbung

Gitterwege und geometrische Parität · Abschnitt 33 von 60

Intuition

Das Schachbrett – als Formel

Du brauchst kein gemaltes Brett. Die Farbe eines Gitterpunkts $(x,y)$ steckt in einer einzigen Zahl:

$x+y$ gerade → Farbe A
$x+y$ ungerade → Farbe B

Das ist genau die Schachbrettfärbung – berechenbar und beweisbar.

Gelöstes Beispiel

Beispiel: Ein Schritt zur Seite

Zug. Von $(x,y)$ nach $(x+1,y)$ .

Rechnung. $x+y$ steigt um 1 → die Parität wechselt → die Farbe wechselt.

Dasselbe gilt für jeden Schritt um 1 nach links, rechts, oben oder unten. Nachbarn haben immer verschiedene Farben.

Satz

Endpunktregel

Bei Wegen aus orthogonalen Einheitsschritten gilt: $\text{Weglänge}\equiv\Delta x+\Delta y\pmod2.$

Kurz: Die Farben von Start und Ziel bestimmen, ob die Länge gerade oder ungerade sein muss.

Beweis

Warum Umwege nichts ändern

Jeder Schritt wechselt die Farbe. Kommst du am Ende wieder auf demselben Endpunkt an, musst du insgesamt eine gerade Anzahl von Farbwechseln gemacht haben – sonst wärst du auf der anderen Farbe gelandet. Umwege ändern die Länge also nur um gerade Zahlen.