Problem 1868

Solution:

Wir werden die Behauptung verallgemeinern. Dazu lassen wir zu, dass das $m \times n$ Rechteck auf beiden Seiten gefärbt wird und dass einige der Einheitsquadrate transparent sind. Solche Felder brauchen nur auf einer Seite gefärbt zu werden und sehen dann auf beiden Seiten gleich aus. Ein nicht transparentes Einheitsquadrat muss dagegen auf beiden Seiten gefärbt werden, allerdings nicht notwendigerweise mit der gleichen Farbe.

Nun sei $A$ die Anzahl aller solcher Färbungen der Oberseite, bei denen es wenigstens einen schwarzen Pfad von der linken zur rechten Seitenkante des Rechtecks gibt. Entsprechend sei $B$ für die Unterseite definiert. Ferner sei $C$ die Anzahl aller Färbungen, bei denen es zwei schwarze Pfade von der linken zur rechten Seitenkante des Rechtecks gibt, und zwar einen auf der Ober- und einen auf der Unterseite, die kein gemeinsames transparentes Quadrat enthalten. Schließlich sei $D$ die Anzahl aller Färbungen dieses Rechtecks. Wir werden (I) $A \cdot B \geq C \cdot D$ beweisen und haben damit die ursprüngliche Behauptung als Spezialfall gezeigt, in dem alle Felder transparent sind. Hier gilt nämlich $A=B=N, C=M, D=2^{m n}$.

Den Beweis von (I) führen wir mit vollständiger Induktion nach der Anzahl $k$ der transparenten Felder. Für $k=0$ ist $A=B=N \cdot 2^{m n}, C=N^{2}$ und $D=\left(2^{m n}\right)^{2}$, so dass in (I) Gleichheit gilt. Nun nehmen wir an, dass die Behauptung für $k$ erfüllt ist, und betrachten ein Rechteck mit $k+1$ transparenten Feldern. Die Anzahlen $A, B, C, D$ gelten nun für dieses Rechteck. Wir wählen ein transparentes Einheitsquadrat $t$ und machen es undurchsichtig. Für das so entstandene Rechteck seien die jeweiligen Anzahlen mit $A^{\prime}, B^{\prime}, C^{\prime}, D^{\prime}$ bezeichnet und nach Induktionsannahme gilt $A^{\prime} \cdot B^{\prime} \geq C^{\prime \prime} \cdot D^{\prime}$.

Nun ist offensichtlich $D^{\prime}=2 \cdot D$. Für jede in $A$ gezählte Färbung existieren genau zwei Färbungen von $A^{\prime}$, nämlich dadurch unterschieden, dass $t$ von unten schwarz oder weiß gefärbt wird. Umgekehrt kann man zwei in $A^{\prime}$ gezählten Färbungen, die sich nur in der Farbe der Unterseite eines Quadrats unterscheiden, eine in $A$ gezählte Färbung zuordnen. Also ist $A^{\prime}=2 \cdot A$ und entsprechend $B^{\prime}=2 \cdot B$. Zum Beweis von (I) für $k+1$ genügt also der Nachweis von $C^{\prime} \geq 2 \cdot C$.

Dazu sei $t$ wieder transparent. Weil in $C$ nur solche Färbungen gezählt werden, die wenigstens einen schwarzen Pfad oben und unten enthalten, wobei diese sich nicht in einem transparenten Quadrat schneiden, kann $t$ höchstens auf einem dieser Pfade, oBdA auf dem oberen, liegen. Machen wir also $t$ undurchsichtig und behalten seine Farbe oben bei, können wir seine Unterseite schwarz oder weiß färben, so dass beide Färbungen in $C^{\prime}$ gezählt werden. Dabei liefern verschiedene in $C$ gezählte Färbungen stets verschiedene Paare von Färbungen, die in $C^{\prime}$ gezählt werden. Damit ist alles gezeigt.