Hans Walser, [20160829]
KO-Turnier
Anregung: M. L., F.
1 Problemstellung
An einem KO-Turnier nehmen 2n Spieler teil.
Die Paarungen fŸr die erste Runde werden zufŠllig zusammengestellt.
Die Abbildung 1 zeigt ein Beispiel fŸr 16 Spieler. Der beste Spieler ist mit 1 bezeichnet, der schlechteste mit 16.
Wie geht es in der zweiten Runde weiter?
Abb. 1: Beispiel einer Ausgangslage
Fragen:
a) Wie viele Runden braucht das Turnier?
b) Mit welcher Wahrscheinlichkeit Pb kommt der zweitbeste Spieler ins Finale?
c) Welches ist der schlechteste Spieler, der noch ins Finale kommen kann? Mit welcher Wahrscheinlichkeit Pc kommt dieser Spieler ins Finale?
2 Ergebnisse
a) Es braucht n Runden
b)
c)
Der Spieler mit dem Rang 2n-1 + 1 ist der
schlechteste Spieler, der noch ins Finale kommen kann. Das ist der beste
Spieler in der rangmŠ§ig zweiten HŠlfte. Dieser Spieler kommt mit der
Wahrscheinlichkeit 
ins Finale.
3 Bearbeitung
a) Beweis induktiv. Jede Verdoppelung der Spielerzahl benštigt eine zusŠtzliche Runde.
b) Der zweitbeste Spieler kommt ins Finale, wenn er bei der ersten Runde nicht in derselben BaumhŠlfte des Turnier-Organigramms ist wie der beste Spieler. Es gibt dazu 2n-1 gŸnstige und 2n – 1 mšgliche FŠlle. Die Abbildung 2 zeigt einen fŸr den zweitbesten Spieler gŸnstigen Fall, die Abbildung 3 einen fŸr den zweitbesten Spieler ungŸnstigen Fall.
Abb. 2: Der zweitbeste Spieler kommt ins Finale
Abb. 3: Der zweitbeste Spieler kommt nicht ins Finale
c)
Der beste Spieler in der rangmŠ§ig
zweiten HŠlfte kommt dann ins Finale, wenn in der
ersten Runde alle besseren Spieler in der anderen HŠlfte des Turnier-Organigramms
sind. FŸr einen noch schlechteren Spieler kann diese Bedingung nicht erfŸllt
sein. Es geht jetzt darum, die 2n
Spieler in zwei Gruppen zu je 2n-1
Spieler aufzuteilen. Dazu gibt es 
Mšglichkeiten. Zwei davon sind gŸnstig
(Bester Spieler in der ersten HŠlfte und Spieler im Rang 2n-1+ 1 in der zweiten HŠlfte oder umgekehrt).
Die Abbildung 4 zeigt einen fŸr den Spieler im Rang 2n-1+ 1 gŸnstigen Fall, die
Abbildung 5 einen ungŸnstigen Fall.
Abb. 4: GŸnstiger Fall fŸr den besten Spieler in der rangmŠ§ig zweiten HŠlfte
Abb. 5: UngŸnstiger Fall fŸr diesen Spieler
Die Tabelle 1 gibt die Werte fŸr die Wahrscheinlichkeiten in b) und c) in AbhŠngigkeit von n.
|
n |
Anzahl Spieler |
Pb |
Pc |
|
1 |
2 |
1 |
1 |
|
2 |
4 |
0.6666666667 |
0.3333333333 |
|
3 |
8 |
0.5714285714 |
0.02857142857 |
|
4 |
16 |
0.5333333333 |
0.0001554001554 |
|
5 |
32 |
0.5161290323 |
3.327341955*10-9 |
|
6 |
64 |
0.5079365079 |
1.091331253*10-18 |
|
7 |
128 |
0.5039370079 |
8.350331114*10-38 |
|
8 |
256 |
0.5019607843 |
3.467010377*10-76 |
|
9 |
512 |
0.5009784736 |
4.232326780*10-153 |
|
10 |
1024 |
0.5004887586 |
4.463035913*10-307 |
|
|
|
0.5 |
0 |
Tab. 1: Numerische Werte