Äquivalenzklassen schöner Bretter

Äquivalenzrelation und Klassenbildung

Zwei Färbungen von Brettern, die sich durch Vertauschen von Zeilen oder Spalten ineinander überführen lassen, sind entweder beide schön oder beide unschön, da die Vertauschung von Zeilen und Spalten rechteckerhaltend ist: Bei der Vertauschung können Rechtecke, deren Ecken vier gegebene Felder des Brettes sind, zwar ihre Lage und Form ändern, aber diese vier Felder bilden entweder sowohl vor als auch nach einer oder mehreren Vertauschungen ein Rechteck, oder sie bilden nie eines.

Das Vertauschen beliebiger Zeilen und Spalten ist eine äquivalente Umformung einer Färbung bezüglich ihrer Schönheit. Die Überführbarkeit zweier Färbungen ineinander durch Vertauschungen erfüllt die Eigenschaften einer Äquivalenzrelation:

Reflexivität

Eine Färbung kann auf triviale Weise in sich selbst überführt werden, indem die Anzahl der angewandten Vertauschungen Null ist.

Symmetrie

Kann Färbung A in Färbung B überführt werden, dann ist dies auch umgekehrt möglich.

Transitivität

Kann Färbung A durch Vertauschungen von Spalten und Zeilen in Färbung B und jene wiederum durch andere Vertauschungen in Färbung C überführt werden, dann gibt es mit der Nacheinanderausführung beider Vorgänge eine Folge von Vertauschungen, die A in C überführt.

(Danke an Lutz für die Einführung der mathematischen Begriffe in die Diskussion.)

Die Menge aller Färbungen zerfällt damit in Äquivalenzklassen. Um schöne Färbungen eines Brettes gegebener Größe mit einer gegebenen Zahl von Farben zu finden, genügt es, einen Vertreter jeder Klasse zu betrachten. Alle schönen Färbungen ergeben sich, indem man alle gefundenen schönen Vertreter von Äquivalenzklassen allen möglichen äquivalenten Umformungen (Kombinationen von Zeilen- und Spalten-Vertauschungen) unterzieht.

Ordnungsrelation und ausgezeichneter Vertreter einer Klasse

Jeder möglichen Färbung eines n×m-Brettes läßt sich eineindeutig eine natürliche Zahl zuordnen. Im Fall von zwei Farben kann man die Farben als gesetzte bzw. nicht gesetzte Bits interpretieren. Die Bitfolge, die sich ergibt, wenn man alle Zeilen der Reihe nach, beginnend bei der obersten, von links nach rechts durchläuft, stellt dann die zugeordnete Zahl im Binärsystem dar. Analog kann man im Fall von k Farben verfahren: Man gibt den Farben Werte von 0 bis k-1 und interpretiert die Folge dieser Werte als Zahlendarstellung zur Basis k.

Genau wie die natürlichen Zahlen lassen sich alle möglichen Färbungen eines Brettes ordnen. Eine Färbung A soll genau dann »kleiner« bzw. »größer« als eine Färbung B heißen, wenn die ihr zugeordnete natürliche Zahl kleiner bzw. größer als die B zugeordnete Zahl ist.

Ebenso wie jede endliche Menge natürlicher Zahlen ein kleinstes Element enthält, enthält jede Äquivalenzklasse von Färbungen eines Brettes eine kleinste Färbung. Es scheint im allgemeinen relativ kompliziert zu sein, zu jeder beliebigen Färbung den kleinsten Vertreter der gleichen Äquivalenzklasse zu finden bzw. zu entscheiden, ob eine gegebene Färbung der kleinste Vertreter ihrer Klasse ist. Es ist jedoch in vielen Fällen möglich, anhand folgender Kriterien zu erkennen, daß es zu einer gegebenen Färbung mindestens eine kleinere äquivalente Färbung gibt:

Ordnung der Zeilen

Es existiert mindestens eine kleinere äquivalente Färbung, wenn die Zeilen einer Färbung nicht monoton steigend von oben nach unten geordnet sind.

Gestalt der Zeilen

Es existiert mindestens eine kleinere äquivalente Färbung, wenn Spalten des Brettes so vertauscht werden können, daß eine Zeile kleiner wird, während alle darüberstehenden unverändert bleiben. Innerhalb der Abschnitte einer Zeile, wo alle darüberstehenden Zeilen jeweils konstante Farbwerte haben, müssen die Farbwerte also nach rechts monoton steigend geordnet sein.

Man kann sich gezielt auf die Untersuchung möglichst kleiner Färbungen aus jeder Äquivalenzklasse beschränken. Durchläuft man alle möglichen Färbungen beginnend mit der kleinsten, wird man in den meisten Fällen feststellen können, daß es eine kleinere äquivalente Färbung gibt, die bereits untersucht wurde. Insbesondere ist es möglich, von vornherein nur Färbungen zu betrachten, von denen man anhand der genannten Kriterien nicht sofort sagen kann, daß es eine kleinere äquivalente Färbung gibt.