+0  
 
0
816
2
avatar+200 

Auf einem Stammtisch treffen n Personen zusammen. Jede Person hat mehr als \(\frac{n+1}{2}\) Bekannte unter den n Personen.

Zu zeigen ist, dass man die Personen so an einen runden Tisch platzieren kann, dass jeder zwischen zwei Freunden sitzt.

 

 

Das ist hauptsächlich eine Knobelaufgabe an diejenigen von euch, die gerne auch mal etwas anderes machen, als stur zu rechnen. Keinen Frust schieben, falls ihr sie nicht schafft! Sie ist anspruchsvoll.

 30.03.2016
 #1
avatar+10390 
0

Hallo melwei!

 

Auf einem Stammtisch treffen n Personen zusammen. Jede Person hat mehr als (n+1)/2 Bekannte unter den n Personen.

Zu zeigen ist, dass man die Personen so an einen runden Tisch platzieren kann, dass jeder zwischen zwei Freunden sitzt.

 

Wenn es n = 3 Personen sind, hat jeder (n+1)/2 = (3+1)/2 = 2 Bekannte.

Wenn sie zu dritt am Tisch sitzen, hat jeder zwei Freunde neben sich.

 

Das wäre eine Lösung. Interessant wäre zu prüfen, ob es noch weitere Möglichkeiten gibt !

 

Gruß asinus :- )

laugh !

 31.03.2016
bearbeitet von asinus  31.03.2016
 #2
avatar+200 
0

Ich fürchte, du hast mich missverstanden. Zu beweisen ist, dass man diese n Personen für jedes BELIEBIGE n so um den Tisch verteilen KANN, dass jede der n Personen zwischen zwei Freunden sitzt. Das ist nämlich so, auch bei anderen Werten für n (Habe da nur als Rätsel reingestellt und kenne den Beweis). Ich werde die Aufgabe nochmal reinstellen, damit sie nicht direkt als "abgehakte Aufgabe" ignoriert wird smiley

 

Auch bei n=4 ist es trivial, da jeder mindestens (sorry meinte mindestens, nicht mehr als blush) 2,5; also 3 Freunde hat.

n=5 ist dann schon ein Stück vertrackter....

 

Das wäre dann:

Person 1 wird auf einen beliebigen Platz gesetzt.

Eine mit Person 1 befreundete Person wird daneben gesetzt (nennen wir sie mal Person 2).

Person 2 hat noch 2 andere Freunde (mindestens), davon setzen wir einen - Person 3 - auf den nächsten Platz.

Person 3 hat unter den übrigen beiden noch mindestens einen Freund (hat ja mindestens 3 insgesamt), der auf dem nächsten Platz landet.

Eine Person steht noch. Sie hat drei Freunde unter den 4 sitzenden Personen, also sitzen irgendwo zwei nebeneinander, da setzt sie sich zwischen.

Dann sitzen alle 5 Leute zwischen zwei Freunden.

 

Auf diese komplizierte Weise kann man das ganze mit etwas Trickserei weiterspinnen bis zu 9 Personen. Aber danach braucht man schon eine andere Methode...

Und das ganze in allgemein ist schon verdammt schwer :)

melwei  31.03.2016

55 Benutzer online