| Autor |
Beitrag |
    
anonym
| | Veröffentlicht am Mittwoch, den 14. März, 2001 - 18:15: | 
|
gegeben seien 2n verschiedene punkte A1 ,
A2,..., A2n, n>1 des Raumes.
V sei die Menge aller Verbindungsstrecken
Ai Aj (i!=j).
Man zeige: Ist M eine Teilmenge von V mit mindestens n2+1 Elementen, dann gibt es mindestens 3 punkte Ar , As , At
(r!=s!=t), so dass ArAs, ArAt, AsAt Elemente von M sind.
Kann man n2+1 durch eine kleinere Zahl ersetzen?
Wenn ja durch welche?
Wenn nein, wieso nicht?
danke im vorraus |
siegfried
| | Veröffentlicht am Donnerstag, den 15. März, 2001 - 17:02: |
|
Was meinst Du mit 'n{2}+1 durch eine kleinere Zahl ersetzen'? |
Zaph (Zaph)
| | Veröffentlicht am Samstag, den 17. März, 2001 - 17:03: |
|
Das geht mit Induktion über n.
Umformulierung der Behauptung: Wenn kein Dreieck in M existiert, dann ist die Anzahl der Verbindungsstrecken in M kleinergleich n^2.
Induktionsanfang kannst du selbst!
Induktionsschritt n->n+1:
Es seien A_1,..., A_[2n+2] gegeben, einige dieser Punkte seien durch Strecken verbunden, und es existiere kein Dreieck. Zeige: Für die Menge M aller Verbindungsstrecken gilt |M| <= (n+1)^2.
Annahme: |M| >= (n+1)^2 + 1.
Wähle zwei Punkte A_i und A_j aus, die durch eine Strecke verbunden sind und entferne diese samt aller Verbindungsstrecken zu diesen beiden Punkten.
In dem so reduzierten Gebilde existiert erst recht kein Dreieck. Nach IV gibt es also maximal n^2 Verbindungsstrecken.
Von den Punkten A_i und A_j gehen dann also mindestens 2n+1 Strecken zu den restlichen 2n Punkten. Also gibt es unter den restlichen Punkten mindestens einen Punkt A_k, der mit beiden Punkten A_i und A_j verbunden ist.
A_i, A_j, A_k bilden ein Dreieck. Widerspruch.
Besser als n^2 geht nicht:
Zerlege die 2n Punkte in zwei Gruppen mit je n Punkten. Verbinde alle Punkte der einen Gruppe mit jeweils allen Punkten der zweiten Gruppe. Das sind n^2 Verbindungsstrecken, und es gibt kein Dreieck. |
anon
| | Veröffentlicht am Freitag, den 23. März, 2001 - 17:44: |
|
danke |
|
