Einfarbige Rechtecke

[Rainer ausdemSpring]

Ein sehr einfaches Rätsel für Schüler:

Auf einem unendlichen Schachbrett sind die Felder in einer von n Farben gefärbt.
Zeige, daß es auf dem Schachbrett ein Rechteck aus Feldern (mit senkrechten/waagerechten Kanten) gibt, bei dem alle Eckfelder die selbe Farbe haben.

Rainer

[Ralf Beyer]

Am 03.02.23 um 15:23 schrieb Rainer ausdemSpring:

Die Triviallösung mit 1x1 Rechtecken ist vermutlich nicht gemeint...

Es gibt aber auch ein Rechteck mit 4 verschiedenen Eckfeldern, die alle die gleiche Farbe haben.

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

Das läßt sich mit 2x Schubfachprinzip zeigen:

Von je n+1 waagerecht nebeneinander liegenden Feldern haben mindestens 2 die gleiche Farbe.

Es gibt insgesamt n^(n+1) Möglichkeiten, eine Reihe mit n+1 Feldern in n Farben einzufärben.

Stapelt man also 1 + n^(n+1) waagerechte Reihen mit je n+1 Feldern senkrecht übereinander,
sind mindestens 2 davon identisch eingefärbt.

Selektiert man von 2 identisch gefärbten Reihen jeweils 2 verschiedene, an gleicher waagerechter
Position liegende, gleichfarbige Felder, so bilden die selektierten Felder ein Rechteck mit
4 gleich gefärbten Eckfeldern.

QED Ralf