TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 192

Bei einem Turnier muss jeder Spieler genau einmal gegen jeden der anderen Spieler antreten. Zeigen Sie: Zu jedem Zeitpunkt des Turniers gibt es mindestens zwei Spieler die dieselbe Anzahl von Spielen bestritten haben.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösungsvorschlag von Ryus

Dies lässt sich mit einem indirekten Beweis zeigen. Wir gehen also vom Gegenteil aus und führen dies zu einem Widerspruch. Wir gehen also davon aus, dass alle Spieler eine unterschiedliche Anzahl von Spielen gespielt haben. Die Mindestanzahl an gespielten Spielen lautet 0 und die Maximalanzahl n-1, wobei n die Anzahl der Spieler ist. Im (n-1)-Fall hätte also jener Spieler bereits mit allen anderen Spielern gespielt. Somit gibt es genau n Möglichkeiten (0 bis (n-1)), wie viele Spiele ein Spieler gespielt haben kann.

Es gibt genau n Spieler. Da jeder Spieler eine unterschiedliche Anzahl an Spielen gespielt hat, muss es also genau einen geben, der 0 Spiele gespielt hat, einen der 1 Spiel gespielt hat, einen der 2 Spiele gespielt hat usw. bis n-1. Jener letzte Spieler, der n-1 Spiele gespielt hat, hat also mit allen anderen Spielern gespielt. Dies ist aber ein Widerspruch, da es auch einen Spieler gibt, der 0 Spiele gespielt hat und daher gar nicht mit dem anderen gespielt haben kann! Damit ist unsere Annahme falsch, es kann nicht sein, dass alle Spieler eine unterschiedliche Anzahl haben, daher muss es mindestens zwei Spieler geben, die die gleiche Anzahl haben.

Das ganze lässt sich auch als graphentheoretisches Problem modellieren, wobei die Fragestellung dort dann wäre "Zeigen Sie, dass in einem schlichten, ungerichteten Graphen immer zwei Knoten gibt, die den gleichen Knotengrad haben". Von daher ist die Aufgabe eigentlich äquivalent zu Beispiel 301 und Beispiel 304

Lösungsvorschlag von Heholord

Bei n Teilnehmern ergibt sich die Anzahl der Spiele aus: $\sum _{k=1}^{n}(n-k)$ oder umgeformt $n^{2}-\sum _{k=1}^{n}k$.

Jetzt müssen zu jedem Spiel 2 Spieler antreten, das heißt die Anzahl der pro Kopf gespielten Spiele sind $2*(n^{2}-\sum _{k=1}^{n}k)$ und diese Anzahl ist immer größer als n. Das heißt, dass mindestens 2 Spieler die selbe Anzahl an Spielen gespielt haben muss. Gilt natürlich wie bei der obigen Lösung nur wenn mind. 2 Spieler spielen.

LG Heholord