Zum Inhalt springen
Inhaltsverzeichnis öffnen
Kapitel 8Fortgeschritten23 Min.

Die Färbung passend entwerfen

Schachbrettfärbungen und Überdeckungen · Abschnitt 31 von 60

Gelöstes Beispiel

Streifen statt Schachbrett

Problem. Du willst horizontale und vertikale Dominos unterscheiden.

Idee. Färbe ganze Zeilen abwechselnd (Streifen).

  • Horizontaler Domino: zwei Felder derselben Farbe.
  • Vertikaler Domino: je ein Feld beider Farben.

Das Schachbrett sieht beide Lagen gleich – die Streifen nicht.

Gelöstes Beispiel

Eine gedachte Schnittlinie (Randlemma)

Idee. Schau nur auf eine Region mit FF Feldern.

  • Innere Dominos (beide Felder drin): tragen 22 bei.
  • Randkreuzende Dominos (genau ein Feld drin): tragen 11 bei.

Also F=2i+cF=2i+c. Modulo 2: Fc(mod2)F\equiv c\pmod2.

Die Anzahl der „Grenz-Dominos“ hat dieselbe Parität wie die Feldzahl.

Checkliste

Eine Färbung prüfen – Mini-Check

  • Welche Bilanz hat ein erlaubter Stein?

  • Gilt diese Bilanz in jeder Lage und Orientierung?

  • Trennt die Färbung wirklich die Fälle, die ich unterscheiden will?

  • Ist mein Schluss nur notwendig – oder schon hinreichend?