Problem des Monats April 2004

Ein Tennisturnier wird im K.o.-System ausgetragen, d.h. ein Spieler scheidet bei seiner ersten Niederlage sofort aus dem Turnier aus. Meist ist die Anzahl der eingeladenen Spieler eine Zweierpotenz. Wenn z.B.  64  Spieler teilnehmen, gibt es eine erste Runde mit  32  Spielen, eine zweite Runde mit  16  Spielen usw. Aber für das folgende Problem sollen auch beliebige andere Möglichkeiten offenstehen, das Turnier zu organisieren (nur das K.o.-System soll gelten).

Wie soll man ein Turnier mit  100  Spielern organisieren, so dass möglichst wenig Spiele erforderlich sind?

Wie lautet die allgemeine Lösung für  n  Spieler?

Lösung

Es ist vollkommen gleichgültig, wie das Tennisturnier organisiert wird.  100  Spieler erfordern immer genau  99  Spiele.  n  Spieler erfordern immer genau  n - 1  Spiele.

Es gibt dafür eine ganz einfache Begründung, aber es sollen zunächst drei Beispiele angegeben werden, die diese Lösung vermuten lassen:

1. Um möglichst schnell auf ein Rundensystem mit einer Zweierpotenz für die Spieleranzahl zu kommen, finden in einer "Vorrunde"  36  Spiele statt. In dieser Runde schauen also  28  Spieler zu ( 28  "Freilose"). Danach sind noch  64  Spieler im Turnier, die in Runden zu  32, 16, 8, 4, 2  Spielen sowie dem Finale den Gesamtsieger ermitteln. In der Summe kommt man auf  99  Spiele.
   
   
2. Auch folgender Ablauf ist denkbar: In jeder Runde werden soviele Paarungen wie möglich ausgetragen. Ist vor Beginn einer Runde die Anzahl der verbliebenen Spieler ungerade, gibt es ein Freilos. Das läuft bei  100  Spielern so ab:
   
   1. Runde:  50  Spiele  -  danach noch  50  Spieler im Turnier
   2. Runde:  25  Spiele  -  danach noch  25  Spieler im Turnier
   3. Runde:  12  Spiele  -  1  Freilos  -  danach noch  13  Spieler im Turnier
   4. Runde:  6  Spiele  -  1  Freilos  -  danach noch  7  Spieler im Turnier
   5. Runde:  3  Spiele  -  1  Freilos  -  danach noch 4  Spieler im Turnier
   Halbfinale:  2  Spiele  -  danach noch  2  Spieler im Turnier
   Finale:  1  Spiel  -  1  Sieger
   
   Insgesamt werden  99  Spiele ausgetragen.
   
   
3. Die beiden ersten Beispiele basieren auf einem "Rundensystem", aber auch ganz andere Systeme führen zum gleichen Ergebnis. Man könnte mit einem einzigen Spiel beginnen und ab dann jeweils dem Gewinner einen weiteren Teilnehmer für das nächste Spiel zulosen. Hier sieht man sofort, dass  99  Spiele gespielt werden. (Dieses Spielsystem hat natürlich zwei praktische Nachteile: Das Turnier dauert sehr lange, und der Gesamtsieger könnte sowohl  99  Spiele bestreiten müssen als auch nur ein einziges, oder irgendeine Anzahl dazwischen.)

Die einfachste Begründung dafür, dass bei  n  Spielern genau  n - 1  Spiele im K.o.-System benötigt werden, lautet so: Jeder Spieler außer dem Gesamtsieger verliert genau ein Spiel, und umgekehrt hat jedes Spiel genau einen Verlierer. Mathematisch ausgedrückt, gibt es eine bijektive Abbildung zwischen der Menge aller Verlierer und der Menge aller Spiele.