TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 185

Aus VoWi
Zur Navigation springen Zur Suche springen

Zeigen Sie mithilfe des Schubfachprinzips: Unter je neun Punkten in einem Würfel der Kantenlänge 2 gibt es stets zwei Punkte, deren Abstand höchstens \sqrt{3} ist.

Hilfreiches[Bearbeiten]

Schubfachprinzip[Bearbeiten]

Definition Schubfachprinzip: Seien m (verschiedene) Objekte in n disjunkte Mengen ("Kategorien", "Schubfächer") eingeteilt. Wenn m > n ist, so gibt es mindestens eine Kategorie, die mindestens zwei Objekte enthält.

Lösung[Bearbeiten]

Allgemeine Betrachtung[Bearbeiten]

Für die Lösung dieser Aufgabe sollte man sich den Quader und die Punkte vorstellen können. In der Angabe gegeben ist ein Würfel (Quader), mit der Kantenlänge 2. Hier handelt es sich aber nicht um einen Spielwürfel mit Augen sondern um eine geometrische Figur, in deren Raum 9 Punkte angeordnet sind. Die Aufgabe ist nun, zu zeigen, dass es zwei Punkte gibt, deren Abstand höchstens \sqrt{3} ist.

Stellen wir uns also einen Quader vor. Der einfachste Fall ist, dass wir in jedes Eck einen Punkt geben, um die Punkte möglichst weit von einander zu platzieren. Der Quader hat jedoch nur 8 Ecken! Somit wird schon hier klar, dass der minimale Abstand weniger als 2, also der Seitenlänge, sein muss. Den 9. Punkt könnte man in der Mitte des Quaders geben, damit er wieder maximal weit von allen anderen Punkten entfernt ist. Der Abstand vom Punkt in der Mitte des Quaders zu einem Punkt in einer der Ecken ist mit Hilfe des Satz von Pythagoras leicht zu berechnen (es handelt sich hierbei um die halbierte Raumdiagonale): \frac{d}{2} = \frac{\sqrt{3} \cdot 2}{2} = \sqrt{3} Somit ist der Punkt in der Mitte des Würfels nur \sqrt{3} von anderen Punkten entfernt. Da es nicht möglich ist, die Punkte weiter von einander anzuordnen, ist der Abstand zwischen zwei Punkten somit höchstens \sqrt{3}.

Anwendung des Schubfachprinzips[Bearbeiten]

Nun überlegen wir uns die Lösung mit Hilfe des Schubfachprinzips. Dazu teilen wir den Quader in weitere Teilquader auf. Diese Aufteilung ist die Anwendung des ersten Teils des Schubfachprinzips. Das Volumen des Quaders ist 2 \cdot 2 \cdot 2 = 8. Es bietet sich nun also an, den Quader einfach in der Länge und Breite jeweils zu halbieren, womit dann 8 Quader mit einer Seitenlänge von 1 entstehen. Diese 8 Quader sind unsere Schubfächer, in den wir unseren ursprünglichen Quader aufgeteilt haben. Nach dem wir n = 8 Schubfächer haben, aber m = 9 Punkte, kommt in ein Schubfach immer ein zweiter Punkt hinein. Positioniert man in diesem Schubfach die zwei Punkte nun wieder größtmöglich entfernt, ergibt sich wieder die Raumdiagonale als größtmögliche Entfernung: d = \sqrt{3} \cdot 1 = \sqrt{3}. Somit gibt es immer zwei Punkte, deren Abstand höchstens \sqrt{3} ist.

-- Superwayne (Diskussion) 19:43, 16. Nov. 2014 (CET)