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

Unter n Mannschaften wird ein Turnier ausgetragen, und es haben insgesamt schon n + 1

Spiele stattgefunden. Man zeige, dass mindestens eine Mannschaft dann bereits an mindestens 3 Spielen teilgenommen hat.

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

Man kann das Ganze als schlichten Graphen interpretieren. Der Graph ist schlicht, weil es keine Mehrfachkanten (keine zwei Mannschaften spielen zweimal gegeneinander) und keine Schlingen (keine Mannschaft spielt gegen sich selbst) gibt.

Man kann die Angabe über einen indirekten Beweis zeigen:

Man nimmt an, bei n Knoten und n+1 Kanten ist der maximale Knotengrad = 2 (für alle Knoten). Ein wenig umformuliert lautet die Behauptung: In einem schlichten Graphen mit n Knoten und maximalem Knotengrad = 2 kann es n+1 Kanten geben.

Diese Behauptung lässt sich mit dem Handschlaglemma auf einen Widerspruch führen, indem man die maximal möglichen Kanten für den Extremfall berechnet, wenn alle Knoten Knotengrad = 2 haben.

$2*\left|E\right|=\sum _{v\in V(G)}d(v)$
$2*\left|E\right|=\sum _{1}^{n}2$
$2*\left|E\right|=n*2$
$\left|E\right|=n$

Das heißt, selbst im Extremfall, wenn alle n Knoten Knotengrad = 2 haben, kann es maximal n Kanten geben. Wenn es n+1 Kanten geben soll, muss der Knotengrad von mindestens 2 Knoten mindestens 3 sein. Umformuliert auf das Fussballbeispiel bedeutet das, dass bei n Mannschaften die alle nur maximal zweimal gespielt haben, können erst n Spiele stattgefunden haben. Wenn aber bereits n+1 Spiele gespielt wurden, haben bereits mindestens 2 Mannschaften mindestens dreimal gespielt.

mfg, --W wallner

Lösungsvorschlag

Lösungsweg

Mannschaften: n

Spiele: n+1

Annahme: alle Mannschaften spielen gleich oft

1. Runde: n Mannschaften treffen in ${n \over 2}$ Spielen aufeinander.

2. Runde: n Mannschaften treffen in ${n \over 2}$ Spielen aufeinander.

Spiele: nach 2 Runden sind ${n \over 2}+{n \over 2}={2n \over 2}=n$ Spiele absolviert. Wobei jede Mannschaft 2-mal angetreten ist.

Wenn n+1 Spiele absolviert worden sind müssen 2 Mannschaften 3mal gespielt haben.

Beispiel

Fußball Weltmeisterschaft 1998

Gruppe B: Italien, Chile, Kamerun, Österreich

--> n = 4

--> wenn nun n+1 Spiele (5) absolviert sind, muss mind. 1 Mannschaft mind. 3mal gespielt haben.

folgende Spiele absolviert:

Spiel 1: Italien – Chile 2:2 (1:1)
Spiel 2: Kamerun – Österreich 1:1 (0:0)
Spiel 3: Chile – Österreich 1:1 (0:0)
Spiel 4: Italien – Kamerun 3:0 (1:0)
Spiel 5: Italien – Österreich 2:1 (1:0)

Italien: 3 Spiele
Chile: 2 Spiele
Kaerun: 2 Spiele
Österreich: 3 Spiele

--> Vorraussetzung erfüllt!