27 rote oder grüne Punkte auf ein rechteckiges Raster von 3 x 9 verteilt

Neue Frage »

Zuse123 Auf diesen Beitrag antworten »
27 rote oder grüne Punkte auf ein rechteckiges Raster von 3 x 9 verteilt
Aufgabe: 27 Punkte werden in einem rechteckigen Raster mit drei Zeilen und
neun Spalten angeordnet. Jeder Punkt wird entweder rot oder grün gefärbt. Beweisen Sie, dass es ein monochromatisches Rechteck gibt, d.h. ein Rechteck, bei welchem alle Eckpunkte dieselbe Farbe haben.

Ich scheitere leider bereits an der Aufgabenstellung. Was ich aus der Aufgabe ableite: Man kann diese 27 farbigen Punkte auf verschiedene Weisen auf das Rechteck verteilen. So wie ich es verstehe, werden diese Punkte auf Eckpunkte gesetzt. Davon gibt es 40 Stück bei 9 Spalten und 4 Zeilen. Nach welchen Kriterien werden diese denn gesetzt? Wie viele rote und wie viele grüne Punkte gibt es? Ich weiß nicht.. aber irgendwie verstehe ich das Problem nicht so ganz.
HAL 9000 Auf diesen Beitrag antworten »

"Raster" ist ein feststehender Begriff. Ehe ich das lange erkläre, ein Bild mit einem solchen Raster, versehen mit einer Beispielfärbung und darin gefundenem monochromatischen Rechteck:

[attach]52683[/attach]


Hinweis zur Lösung: Überlege dir, wieviel mögliche Färbungen EINER Spalte es gibt, d.h., von den darin liegenden drei Punkten. Und dann bist du ja gerade mit dem Schubfachprinzip unterwegs, was du hoffentlich nicht vergessen hast.


P.S.: Mit etwas längerer Argumentation kann man sogar beweisen, dass es bereits auf einem 3x7-Raster ein solches monochromatisches Rechteck geben muss. Auf einem 3x6-Raster aber noch nicht, wie meine Beispielfärbung beweist, wenn man sie auf die linken 6 Spalten reduziert.
Zuse12345 Auf diesen Beitrag antworten »

OK, ich hatte eine falsche Vorstellung davon, was ein Raster ist.
Habe die Aufgabe mit deiner Erklärung sofort lösen können. War ja nicht sonderlich schwierig.
Vielen Dank! smile

Jedoch bin ich gerade am rätseln, wie es denn sein kann, dass es solch ein Rechteck auch stets auf einem 3x7 Raster gibt. Es gibt ja 2^3, also 8 mögliche Färbungen pro Spalte. D.h. damit ich das Schubfachprinzip anwenden kann, müsste es 9 solcher Spalten geben.
Zuse12345 Auf diesen Beitrag antworten »

Ach, mir fällt gerade eine Lösung ein, aber ich weiß nicht, ob die Argumentation mathematisch korrekt ist. Man könnte argumentieren, dass der erste Punkt der Spalte (oben) entweder rot oder grün ist. Also hat man 2 Fälle:
Der erste Punkt (von oben) der Spalte ist entweder rot oder grün:
1. Fall:
R
X
X
2. Fall:
G
X
X

Für die restlichen Spalte (die Punkte oben sind jeweils mit X abgebildet) kann es 4 mögliche Färbungen geben, wobei in 2 Färbungen die Farbe der Punkte gleich ist.
D.h. man hat bei 7 Spalten stets 2 Spalten, die mindestens in 2 Punkten (der gleichen Höhe) die gleiche Farbe aufweisen.

Illustration.:
R - R - R - R - G - G - X
R - R - G - G - G - R - X
R - G - R - G - R - G - X

Die letzte Spalte muss entweder (G - G - G) oder (G - R - R) sein oder eine Wiederholung der vorherigen Spalten sein, daher ist spätestens mit dieser Spalte ein monochromatisches Rechteck vorhanden.
HAL 9000 Auf diesen Beitrag antworten »

Ja, so kann es wohl gehen. Meine Begründung war etwas anders:

Ich betrachte zunächst den Fall, dass es keine monochromatischen Spalten gibt, dafür gibt es aber nur Färbungen, womit es bei 7 Spalten laut Schubfachprinzip zwei gleichgefärbte Spalten gibt (d.h., es läuft so ähnlich wie im Originalbeweis mit 9 Spalten), und damit auch ein monochromatisches Rechteck.

Im anderen Fall hat man also mindestens eine monochromatische Spalte, o.B.d.A. RRR. Damit nun kein monochromatisches Rechteck unter Beteiligung genau dieser Spalte entsteht, darf es in allen 6 Restspalten jeweils nur maximal ein R geben. Nun gibt es aber nur 3+1=4 mögliche Färbungen mit maximal einem R, womit es wiederum nach Schubfachprinzip unter den 6 Restspalten zwei gleichgefärbte geben muss, die dann ein grünes monochromatisches Rechteck ergeben.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »