Aufgabe mit Beweis im Rahmen Diskreter Mathematik

Neue Frage »

Silas Auf diesen Beitrag antworten »
Aufgabe mit Beweis im Rahmen Diskreter Mathematik
Hallo, ich sitze gerade vor einer Aufgabe, bei der ich gar nicht weiß, wie ich anfangen soll.

Zur Zeit besuche ich eine Veranstaltung zur Diskreten Mathematik. Wir haben gerade solche Sachen wie Schubfachprinzip, Cliquen/Anticliquen etc.

Hier ist die Aufgabe.
Beweise: Unter je zehn Punkten aus ZxZ gibt es stets zwei, bei denen der Punkt, der die Strecke zwischen diesen beiden Punkten im Verhältnis 2:1 teilt, ebenfalls aus ZxZ ist.

Wie soll ich da anfangen?
AD Auf diesen Beitrag antworten »

Zitat:
Original von Silas
Beweise: Unter je zehn Punkten aus ZxZ gibt es stets zwei, bei denen der Punkt, der die Strecke zwischen diesen beiden Punkten im Verhältnis 2:1 teilt, ebenfalls aus ZxZ ist.

2:1 heißt, dass die Strecke in drei gleiche Teile geteilt wird, und der fragliche Punkt einer der beiden mittleren Teilungspunkte ist. Also irgendwie geht es bei den Ausgangskoordinaten um modulo 3, vielleicht bringt dich dieser Hinweis auf die Sprünge. Ach ja, Schubfachprinzip noch als zweiten Hinweis... Augenzwinkern
Silas Auf diesen Beitrag antworten »

Also, ich denke die ganze Zeit daran, dass ich, um das Schubfachprinzip nutzen zu können, mehr Objekte als Kategorien brauche.

Meine Objekte sind doch die zehn Punkte. Und irgendwie brauche ich nun noch meine Kategorien, und zwar so, dass in eine der Kategorien zwei Punkte fallen.

Aber was für Kategorien sind das? 9? Und wie sind die Kategorien "beschriftet"?

Bei modulo 3 können die Reste 0,1 oder 2 auftreten. Hm...
AD Auf diesen Beitrag antworten »

Zitat:
Original von Silas
Bei modulo 3 können die Reste 0,1 oder 2 auftreten. Hm...

Und das sowohl für x- als auch für die y-Koordinaten der Punkte...
Silas Auf diesen Beitrag antworten »

Rest 0,1,2 für die x-Koordinaten und
Rest 0,1,2 für die y-Koordinaten.

Also irgendwie habe ich da 9 Kategorien: 0,0 ; 0,1 ; 0,2 ; 1,0 ; 1,1 ; 1,2 ; 2,0 ; 2,1 ; 2,2.

Denke ich da richtig oder bin ich auf dem Holzweg?
AD Auf diesen Beitrag antworten »

Naja, das ist doch der richtige Weg...

Vielleicht fehlen dir die richtigen geometrischen Vorüberlegungen, warum man hier so vorgeht:

Der Punkt teile die Strecke mit und im Verhältnis 2 : 1, d.h. .

Dann gilt und , wie man sich leicht mit Koordinatengeometrie ausrechnen kann. Somit ist bei gegebenen genau dann der Fall, wenn und beide erfüllt sind.
 
 
Silas Auf diesen Beitrag antworten »

Das habe ich, glaub ich verstanden.

Deine Rechnung verstehe ich. Jetzt noch mal zum Schubfachprinzip. Ich betrachte nur die x-Koordinaten.

Es können beim Teilen durch 3 folgende Fälle eintreten.
1. Beide x-Werte haben den Rest 0.
2. Eine der beiden hat den Rest 0, die andere den Rest 1.
3. Eine der beiden hat den Rest 0, die andere den Rest 2.
4. Beide haben den Rest 1.
5. Eine der beiden hat den Rest 1, die andere den Rest 2.
6. Beide haben den Rest 2.

Das sind 6 Kategorien, wenn man so will. Da ich 10 Punkte habe, packe ich erstmal in jede Kategorie ein x-Werte-Päarchen. Dann habe ich noch 4 x-Werte-Päarchen zu verteilen. Packe ich 3 davon jeweils in die Kategorien 2,3 und 5, dann bleibt noch ein x-Werte-Päarchen für die Kategorien 1,4 oder 6. Aber in diesen Kategorien haben beide x-Werte ja stets denselben Rest.

Das gilt analog für die y-Werte. Deshalb finde ich bei 10 Punkten stets 2 Punkte, deren x-Werte beim Teilen durch 3 denselben Rest haben und deren y-Werte beim Teilen durch 3 denselben Rest haben. Und damit auch immer einen Punkt Q, der im Verhältnis 2:1 teilt und zu Z gehört.
AD Auf diesen Beitrag antworten »

Ich muss mich korrigieren: Du bist doch auf dem Holzweg.

Ich habe deine obige Aufzählung (0,0),(0,1),... (2,2) so verstanden, dass du die Punkte (also deren (x,y)-Koordinaten) in Kategorien einteilst, so klappt es nämlich auch.

Stattdessen sind das bei dir die x-Koordinaten von zwei Punkten eines Punktpaares - ich weiß nicht, wohin das führen soll. unglücklich


Zitat:
Original von Silas
Da ich 10 Punkte habe, packe ich erstmal in jede Kategorie ein x-Werte-Päarchen. Dann habe ich noch 4 x-Werte-Päarchen zu verteilen.

Völlig falsche Betrachtungsweise: Die Punkte sind fest vorgegeben, deren Kategorien liegen also bereits bei Definition der Kategorien fest, da gibt's nix zuzordnen a la "pro Kategorie ein Punkt". Diese Art Betrachtungen haben nichts, aber auch gar nichts mit dem Schubfachprinzip zu tun.
Silas Auf diesen Beitrag antworten »

Also, ich das jetzt so gemacht, dass ich neun Kategorien habe:

0,0 ; 0,1 ; 0,2 ; 1,0 usw.

In der ersten Kategorie sind z. B. alle Punkte, deren x-Werte beim Teilen durch 3 den Rest 0 haben und deren y-Werte beim Teilen durch 3 den Rest 0 haben.

Bei zehn Punkten liegen in irgendeiner Kategorie also mindestens zwei Punkte, deren jeweilige x-Werte den gleichen Rest beim Teilen durch 3 haben und deren jeweilige y-Werte den gleichen Rest beim Teilen durch 3 haben.

Und dann greift ja wieder dein Vorschlag der Koordinatenberechnung des Punktes, der die Strecke der beiden Punkte, die in derselben Kategorie liegen, im Verhältnis 2:1 teilt.
AD Auf diesen Beitrag antworten »

Jepp, das ist es. Freude
Silas Auf diesen Beitrag antworten »

Vielen Dank für deine Hilfe.
Neue Frage »
Antworten »



Verwandte Themen

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