+211 Hallo zusammen,
Hier kommt mal wieder die Aufgabe mit dem Stammtisch, damit sie nicht in Vergessenheit gerät. Das letzte mal wurde eine Antwort gegeben, die leider nur einen Fall betrachtet hat. Deshalb hier noch einmal:
Auf einem Stammtisch treffen n Personen zusammen. Jede Person hat mindestens \(\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.
Und zwar bei beliebigem n!
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.
+211 Entschuldigung, ich meinte Freunde, nicht Bekannte. Jetzt aber richtig:
Auf einem Stammtisch treffen n Personen zusammen. Jede Person hat mindestens \(\frac{n+1}{2}\) Freunde unter den n Personen.
Zu zeigen ist, dass man die Personen so an einen runden Tisch platzieren kann, dass jeder zwischen zwei Freunden sitzt.
Und zwar bei beliebigem n!
+26367 Auf einem Stammtisch treffen \(n\) Personen zusammen.
Jede Person hat mindestens \(\uparrow \frac{n+1}{2} \uparrow \) Freunde unter den n Personen.
Zu zeigen ist, dass man die Personen so an einen runden Tisch platzieren kann,
dass jeder zwischen zwei Freunden sitzt.
Und zwar bei beliebigem \(n\) !
Wenn wir ein \(n\)-Eck haben und jede Verbindung zu jeder anderen Ecke ziehen, so haben wir maximal \(n-1\)Verbindungen an jeder Ecke. Jede Verbindung bedeutet Freund sein miteinander. Oder anders gesagt, jede Person kann maximal \(n-1 \)Freunde haben.
Wir müssen nun zeigen das \(n-1\) immer größer oder gleich der Mindestanzahl der Freunde ist, die jede Person haben darf für ein beliebiges \(n > 2\). Dann haben wir eine allgemeine Lösung für \(n\ge 3\).
Wir können formulieren:
\(n-1 ~\ge ~ \uparrow \frac{n+1}{2} \uparrow\)
wobei \(\uparrow \dots \uparrow \) aufrunden bedeutet.
Für \(n=3\) gilt direkt
\(n-1 ~\ge~ \uparrow \frac{n+1}{2} \uparrow \\ 3-1 ~\ge~ \uparrow \frac{3+1}{2} \uparrow \\ 2 ~\ge~ 2\)
Das ist richtig. Die Ungleichung gilt also für \(n=3\).
Allgemein kann man zeigen:
\(n-1 ~\ge~ \uparrow \frac{n+1}{2} \uparrow ~<~ \underbrace{\frac{n+1}{2} + \frac12}_{=\frac{n+2}{2}}~ (\text{aufgerundet}) \)
Wenn wir \(n-1 ~\ge~\frac{n+2}{2}\) zeigen, so ist auch \(n-1 ~\ge~ \uparrow \frac{n+1}{2} \uparrow\),
da \(\uparrow \frac{n+1}{2} \uparrow ~<~ \frac{n+1}{2} + \frac12 \)
Beweis:
\(\begin{array}{rcll} n-1 &\ge& \frac{n+2}{2} \quad | \quad \cdot 2\\ 2n-2 &\ge& n+2 \\ 2n-n &\ge& 2+2 \\ n &\ge& 4 \end{array}\)
Die Ungleichung gilt für \( n \ge 4\). Für \(n=3\) haben wir sie direkt bewiesen. Somit gilt:
Die maximale Anzahl der Verbindungen(Freunde) an jeder Person im \(n\)-Eck beträgt \(n-1\)und\( \boxed{~ n-1 ~\ge~ \uparrow \frac{n+1}{2} \uparrow \qquad n\ge 3 ~}\)
Für \( n=4,~ n=5\) und \(n=6\) zeigen die Bilder die Verbindungen(Freunde)
Für \( n = 4\) ergeben sich je Person \(3\) Freunde.
Für \(n=5\) ergeben sich je Person \(4\) Freunde.
Für \(n=6\) ergebn sich je Person \(5\) Freunde.
Der Polygonring definiert, das die Personen jeweils zwischen zwei Freunden sitzen.
Es gibt minimalere Lösungen, was die jeweilige Anzahl der Freunde betrifft, doch das ist hier nicht gefordert.
+211 Oh Mann, ich war wohl immer noch nicht verständlich.
Zu zeigen ist, dass man sie so platzieren kann, dass jeder direkt neben zwei Freunden sitzt 
Hoffe, dass das jetzt verständlich ist....
+26367 Oh Mann, ich war wohl immer noch nicht verständlich.
Zu zeigen ist, dass man sie so platzieren kann, dass jeder direkt neben zwei Freunden sitzt.
Hallo melwei,
meine Lösung beinhaltet doch gerade dies. Im Polygonring(braune Linie links und rechts von jeder Person (Ecke) ausgehend), den es für jedes n gibt sind ja immer 2 Freunde nebeneinander links und rechts von jeder Person angeordnet.
Das sieht man an den Verbindungen. Eine Verbindung bedeutet ist Freund von...mit und vis versa.
+26367 Für n=6 ergeben sich je Person 5 Freunde.
Äh.... Für mich sind es da mindestens , also mindestens 4 Freunde.
Hallo melwei,
mindestens 4 Freunde bedeutet doch mathematisch gesehen 4 oder mehr Freunde und nicht genau 4 Freunde, oder ?
Für n=6 ergeben sich je Person 5 Freunde:
5 Freunde sind doch mindestens 4 Freunde oder mehr, oder ?
Heureka
