TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 302

Aus VoWi
Wechseln zu: Navigation, Suche

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.

WS08 Beispiel 207[Bearbeiten]

Lösungsvorschlag[Bearbeiten]

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[Bearbeiten]

Lösungsweg[Bearbeiten]

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[Bearbeiten]

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!