stopsoftwarepatents.eu petition banner

Schöne Bretter

Diese Aufgabe wurde ursprünglich von Micha in thur.org.lug gestellt, ihr Maintainer im Web ist Thomas.

Aufgabenstellung

Gegeben sei ein n×m-Brett. Jedes Feld soll mit einer von k Farben gefärbt werden, so daß es am Ende »schön« aussieht. Dabei sei ein Brett »schön«, wenn man kein Rechteck findet, dessen vier Ecken sich in vier verschiedenen Feldern befinden, die alle die gleiche Farbe haben.

Die Frage ist nun: Gibt es bei gegebener Brettgröße eine schöne Färbung?

Beispiele

Für 4×4-Bretter mit zwei Farben lassen sich Lösungen von Hand finden. Im folgenden sind einige schöne und einige unschöne 4×4-Bretter aufgeführt, bei letzteren sind die störenden Rechtecke eingezeichnet.

Schöne 4×4-Bretter
[Schönes 4×4-Brett] [Schönes 4×4-Brett] [Schönes 4×4-Brett]
Unschöne 4×4-Bretter
[Unschönes 4×4-Brett] [Unschönes 4×4-Brett] [Unschönes 4×4-Brett]

Lösung

Äquivalenzklassen

Lösungen für eine bestimmte Brettgröße und Farbenzahl lassen sich in Klassen unterteilen, wobei die Mitglieder jeder Klasse durch einfache Operationen ineinander überführbar sind und sich für jede Klasse ein ausgezeichneter Vertreter bestimmen läßt. Auf diese Weise kann man die Vielzahl von Lösungen handhabbar machen.

Größtmögliche schöne Bretter für 2 Farben

Mit Hilfe des Äquivalenzklassen-Formalismus läßt sich zeigen, daß bei gegebener Farbenzahl nicht beliebig große Bretter schön gefärbt werden können. Für den Fall von genau zwei Farben gibt es die vollständigen Nachweise der Grenzen. Bis hier braucht man noch keinen Computer.