Kombinatorik: Anwendung Schubfachprinzip (geometrisch)
Neue Frage »

15.10.2014, 17:12 Noel93 Auf diesen Beitrag antworten »
Kombinatorik: Anwendung Schubfachprinzip (geometrisch)
Meine Frage:
Guten Abend!

Leider komme ich bei folgender Übungsaufgabe nicht weiter:

In ein quadratisches, 30x30cm Brett werden wahllos sieben Nägel geschlagen.
Zeige, dass es immer mindestens zwei Nägel gibt, die höchstens 20cm voneinander entfernt eingeschlagen wurden.


Meine Ideen:
Das ganze riecht verdächtig nach Schubfachprinzip. Ich hab also geguckt ob man die 900cm² irgendwie in "Fächer" unterteilen kann um die Nägel (bzw die Fläche des Radius-10cm-Kreises um sie) dann in diese einzuordnen.

Nur leider kann es ja auch sein, dass ein Nagel direkt an den Rand geschlagen wird - es liegt also nicht die gesamte Kreisfläche um diesen Nagel auch auf der Brettfläche. Sonst könnte man ja nen leichten Beweis durch Widerspruch erbringen: sieben Kreise macht eine Mindestfläche von ~2100cm², 900cm² reichen also definitiv nicht aus.

Leider klappt kein Ansatz. zB hab ich überlegt, dass man im flächenmäßig "besten" Fall vier Nägel in die vier Brettecken und die restlichen drei ebenfalls an den Rand hauen könnte - die Fläche der Kreise um diese Nägel, die sich auch auf dem Brett befindet, wäre dann 4?1/4+3?1/2 Kreise, macht eine Fläche von 2 1/2?314= 785cm². Leider ist das unter 900cm² und daher kein Beweis, dass zwei Nägel näher als 20cm aneinanderliegen.

Ein anderer Ansatz war, dass ich das Brett zu einem 50x50cm Brett mache, damit die über den Rand des Bretts herausstehende Kreisfläche auf meinem "neuen" Brett liegt. So kann ich 7?314= 2198cm² als von Nägeln "besetzte" Fläche errechnen, leider ist das "neue" Brett aber auch 2500cm² groß, da würden die sieben Kreise also AUCH draufpassen.

Leider fällt mir kein anderer Ansatz ein. Ich habe schon überlegt, statt Kreisen mit Radius 10 einfach Rechtecke um die Nägel zu legen, deren Diagonale jeweils 20cm lang ist (es wären also ?200??200 Quadrate), aber ich bin mir nicht sicher ob das dann den angesprochenen Fall abdecken würde (Nagel am Rand ? "besetzte" Fläche um den Nagel ist teilweise nicht auf dem Brett, weshalb nur eine Teilfläche des Kreises bzw. Quadrats um den Nagel von der zur Verfügung stehenden Brettfläche abgezogen werden kann. Oder hab ich da nen Denkfehler, dass das ein Problem macht?

Danke im Voraus!
15.10.2014, 17:54 HAL 9000 Auf diesen Beitrag antworten »

Die Idee der Unterteilung in Rechtecke ist gut. Jetzt überleg mal:

Du hast sieben Nägel, und willst das Schubfachprinzip anwenden, so dass in einem Rechteck mindestens zwei Nägel sind.

Das erfordert, dass deine Unterteilung in (maximal) sechs Rechtecke geschieht. Tja, und wie unterteilt man nun eine 30x30-Fläche zweckmäßig so in sechs Rechtecke, dass die Diagonalen nicht so groß werden? Augenzwinkern


P.S.: Grad mal noch abgecheckt, dass es nicht eine der aktuellen Olympiadeaufgaben ist. Augenzwinkern
15.10.2014, 18:16 Noel93 Auf diesen Beitrag antworten »

Hm,eigentlich kriege ich nur vier Quadrate mit ausreichenden Maßen auf mein Brett. Aber hätte dann nicht in der Aufgabe auch was von fünf oder sechs Nägeln stehen können? Wäre doch das selbe Ergebnis, oder? verwirrt
15.10.2014, 18:21 HAL 9000 Auf diesen Beitrag antworten »
ohne Worte
code: 
1:
2:
3:
4:
5:
6:
7:

+---+---+---+
|   |   |   |
|   |   |   |
+---+---+---+
|   |   |   |
|   |   |   |
+---+---+---+
15.10.2014, 18:29 Noel93 Auf diesen Beitrag antworten »

Sprich, bei 2 x 3 Kästchen hätte jedes eine Größe von 15*10cm und daher nur eine Diagonale von ~18cm, was zu wenig ist. Also wäre selbst einmalige Bestückung aller Kästchen (6 Nägel) schon ausreichend, um zu beweisen dass mindestens zwei näher als 20cm beieinander sind.
Richtig verstanden? geschockt
15.10.2014, 18:35 HAL 9000 Auf diesen Beitrag antworten »
Schubfachprinzip verstanden?
Nein, nicht 6 Nägel , sondern 7 Nägel - einer mehr als die Anzahl der Schubfächer!!! Ansonsten aber richtig.
 Anzeige 
 
15.10.2014, 18:48 Noel93 Auf diesen Beitrag antworten »

Alles klar, Denkfehler meinerseits. Hammer So machts Sinn, danke!
15.10.2014, 19:01 HAL 9000 Auf diesen Beitrag antworten »

Dass es nicht immer Rechtecke sind, sondern man manchmal auch tiefer in die Trickkiste greifen muss, zeigt dieses schöne Beispiel:

IMO Auswahlklausur 2000 Schubfachprinzip


EDIT:

Übrigens reichen tatsächlich bereits 6 Nägel: Dazu zerlegt man das Feld in zwei Rechtecke mit den Maßen 15 x 13 und drei Rechtecke mit den Maßen 10 x 17, dann sind nämlich die Diagonalenlängen und beide kleiner als 20, wie gewünscht. Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

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


MatheBoard » Hochschulmathematik » Stochastik & Kombinatorik » Kombinatorik: Anwendung Schubfachprinzip (geometrisch)