Turnierbäume: Freilose, Setzlisten und warum die Zahlen Zweierpotenzen sein müssen

Der Baum halbiert sich, also muss er bei einer Zweierpotenz beginnen

Eine K.-o.-Runde paart alle und schickt die Hälfte nach Hause. Beginne mit 16, und du erhältst 8, dann 4, dann 2, dann 1: vier Runden, keine Reste, niemand ohne Gegner. Beginne mit 12, und die zweite Runde hat 6, die dritte 3 — und nun lassen sich drei Spieler nicht paaren. Die Struktur schließt nur, wenn jede Runde bis nach unten eine gerade Zahl Überlebender hat, und die einzigen Zahlen mit dieser Eigenschaft sind die Zweierpotenzen. Das ist keine von Veranstaltern gewählte Konvention, sondern das, was wiederholtes Halbieren tut — und deshalb hat jeder veröffentlichte Turnierbaum, den du je gesehen hast, 8, 16, 32, 64 oder 128 Plätze.

Die Rundenzahl folgt aus demselben Argument. Fasst der Baum 2^r Meldungen, braucht es r Halbierungen bis zu einem einzigen Sieger, also ist r der Logarithmus zur Basis 2 der Baumgröße, und für eine beliebige Meldezahl n ist die Baumgröße die kleinste Zweierpotenz, die nicht unter n liegt. Ausgeschrieben: Runden = aufgerundet(log2 n), Größe = 2^aufgerundet(log2 n). Zwölf Meldungen spielen also einen 16er-Baum über 4 Runden; 100 Meldungen einen 128er über 7; 129 Meldungen einen 256er über 8. Dieser letzte Sprung ist das ganze Problem in einer Zeile — die 129. Meldung fügt dem Spielplan keine Partie hinzu, sondern eine komplette Runde.

Freilose sind genau die Lücke zur nächsten Zweierpotenz

Hat der Baum 2^aufgerundet(log2 n) Plätze und sind nur n davon mit echten Meldungen besetzt, bleiben die übrigen Plätze leer. Jedem leeren Platz steht eine echte Meldung gegenüber, die dadurch ohne Spiel weiterkommt — und das ist ein Freilos. Die Freilosanzahl ist also die Subtraktion und nichts weiter: Freilose = 2^aufgerundet(log2 n) − n. Dreiundzwanzig Meldungen in einem 32er-Baum ergeben 9 Freilose; 48 in einem 64er 16; 100 in einem 128er 28. Die Zahl ist knapp über einer Zweierpotenz am größten und auf einer exakt null — deshalb erzeugen 129 Meldungen 127 Freilose, also mehr Freilose als Personen, die in Runde eins tatsächlich spielen.

Die erste Runde ist um genau denselben Betrag kleiner als der halbe Baum. Erhalten b Meldungen ein Freilos, spielen die übrigen n − b, und sie bestreiten (n − b)/2 Partien; setzt man b = 2^r − n ein, ergibt sich Erstrundenpartien = n − 2^(r − 1), also n minus der halbe Baum. Bei 100 Meldungen sind das 100 − 64 = 36 Partien, und die Probe schließt: 36 × 2 = 72 Personen spielen, 28 setzen aus, 72 + 28 = 100, und 36 + 28 = 64 Überlebende gehen in Runde zwei — genau der halbe Baum, wo die saubere Zweierpotenzstruktur wieder einsetzt. Ab Runde zwei gibt es überhaupt keine Freilose mehr, weil das Feld konstruktionsbedingt wieder eine Zweierpotenz ist.

Die Setzreihenfolge entsteht aus einer Rekursion, nicht aus einer auswendig gelernten Liste

Beginne mit einem Baum der Größe eins: Die Setzreihenfolge ist [1]. Zum Verdoppeln nimm jede Setzung s in einem Baum, der gleich die Größe m hat, und ersetze sie durch das Paar (s, m + 1 − s). Eine Verdopplung ergibt [1, 2]. Zwei ergeben [1, 4, 2, 3]. Drei ergeben [1, 8, 4, 5, 2, 7, 3, 6]. Vier ergeben 1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11. Fünf ergeben 1, 32, 16, 17, 8, 25, 9, 24, 4, 29, 13, 20, 5, 28, 12, 21, 2, 31, 15, 18, 7, 26, 10, 23, 3, 30, 14, 19, 6, 27, 11, 22. Nichts wird auswendig gelernt und nichts nachgeschlagen; die Rekursion sind vier Zeilen Code und liefert die Standardreihenfolge für jede Baumgröße.

Lies die Sechzehner-Zeile als acht Erstrundenpartien, und das Muster springt ins Auge: 1 gegen 16, 8 gegen 9, 4 gegen 13, 5 gegen 12, 2 gegen 15, 7 gegen 10, 3 gegen 14, 6 gegen 11. Jede Paarung summiert sich zu 17, also Baumgröße plus eins, denn genau das erzwingt die Ersetzung s zu (s, m + 1 − s). Es ist auf jeder Ebene des Baums dieselbe Regel: Die stärkste verbliebene Setzung eines Blocks trifft stets auf die schwächste verbliebene, in jeder Runde, ohne dass jemand eine zweite Regel aufschreiben müsste.

Was die Setzung wirklich garantiert — geprüft, nicht behauptet

Schick die erzeugte Reihenfolge durch ein paar Zusicherungen, und der Entwurf zeigt sich. Zerlege die Sechzehner-Reihenfolge in Blöcke: Jeder Block gleicher Größe summiert sich zur selben Zahl — 17 je Paar, 34 je Viertel, 68 je Hälfte, 136 für den ganzen Baum —, stets Blockgröße mal (n + 1) geteilt durch 2. Nimm die beste Setzung jedes Blocks, und du erhältst die Setzreihenfolge eines halb so großen Baums zurück: Die Zweierblöcke ergeben 1, 8, 4, 5, 2, 7, 3, 6, also die Achter-Reihenfolge; die Viererblöcke ergeben 1, 4, 2, 3. Der Baum ist selbstähnlich — genau das, was eine Verdopplungsrekursion erzeugen sollte.

Die Garantie, die wirklich interessiert, folgt unmittelbar. Die Nummern 1 und 2 sitzen in gegenüberliegenden Hälften, können sich also, wenn beide weitergewinnen, nicht vor dem Finale treffen; die Nummern 1, 2, 3 und 4 sitzen in vier verschiedenen Vierteln, zwei von ihnen können sich also nicht vor dem Halbfinale treffen. Verfolgt man die frühestmöglichen Gegner der Nummer 1 im Sechzehner-Baum, ergibt sich 16 in Runde eins, 8 oder 9 in Runde zwei, eine von 4, 5, 12, 13 im Halbfinale und 2 oder 3 erst im Finale. Das ist der Sinn der Setzung, präzise formuliert: Sie schützt den Favoriten nicht vor starken Gegnern, sie schiebt sie auf, damit die besten Partien des Turniers am Ende stehen und nicht in der Auftaktrunde.

Die Setzung verteilt auch die Freilose ohne eigene Regel. Fülle einen 128er-Baum mit den Meldungen 1 bis 100 und Phantommeldungen 101 bis 128, erzeuge die Reihenfolge mit der Rekursion und lies ab, welche echten Meldungen gegen Phantome gepaart sind: Es sind genau die Setzungen 1 bis 28, zusammenhängend und der Reihe nach. Niemand musste entscheiden, dass die Freilose an die Topgesetzten gehen — dieselbe Ersetzung, die s mit m + 1 − s paart, stellt die höchsten Setzungen den höchstnummerierten Plätzen gegenüber, und genau die sind leer. Das lohnt sich in jedem Werkzeug zu prüfen, denn ein Generator, der Freilose an beliebige Meldungen vergibt, hat die Setzung kaputtgemacht und nicht bloß die Freilose.

Gesamtzahl der Partien: n − 1, für jedes n, in einer Zeile

Jede Partie in einem K.-o.-Turnier scheidet genau einen Teilnehmer aus — das bedeutet K. o. Am Ende ist genau ein Teilnehmer nicht ausgeschieden, also sind es genau n − 1, die ausgeschieden sind. Ein Ausscheiden je Partie heißt damit genau n − 1 Partien, gleichgültig wie groß der Baum, wie viele Freilose, wie gesetzt wird. Dreiundzwanzig Meldungen spielen 22 Partien; 100 Meldungen spielen 99; 129 Meldungen spielen 128. Du musst die Runden nie aufaddieren, und die Freilose gehen überhaupt nicht in die Rechnung ein, denn ein Freilos ist keine Partie und scheidet niemanden aus.

Dasselbe Abzählargument bepreist die anderen Formate. Im Doppel-K.-o. muss jeder außer dem Sieger zweimal verlieren, es sind also 2(n − 1) Niederlagen zu erzeugen, und da jede Partie genau eine Niederlage hervorbringt, braucht der Spielplan 2n − 2 Partien. Gewinnt der aus der Verliererrunde kommende Finalist das große Finale, hat er dem bis dahin ungeschlagenen Spieler die erste Niederlage beigebracht, und es wird ein Rücksetzspiel für die zweite ausgetragen — in diesem Fall 2n − 1 Partien. Beide Zahlen sind exakt, und welche gilt, entscheidet sich am Tag selbst. Jeder gegen jeden ist ein anderes Tier: Jedes Paar trifft sich einmal, die Anzahl ist also C(n,2) = n(n − 1)/2 und wächst quadratisch. Bei 100 Meldungen sind das 4 950 Partien gegen 99 im K.-o.-System, ein Faktor von genau 50.

Ein Format anhand der Zahlen wählen

Die drei Formate tauschen Partien gegen Information. Das K.-o.-System ist das billigstmögliche Turnier — n − 1 Partien, aufgerundet(log2 n) Runden — und liefert genau eine verlässliche Tatsache: wer gewonnen hat. Alles unterhalb des ersten Platzes ist ein Artefakt der Auslosung: Die unterlegenen Halbfinalisten werden nicht gegeneinander gereiht, und eine starke Meldung, die in Runde zwei auf den Sieger trifft, endet ununterscheidbar von einer schwachen. Doppel-K.-o. kauft eine zweite Chance für ungefähr die doppelte Partienzahl und rund eine Runde mehr und beseitigt den schlimmsten Ausfallmodus: eine gute Meldung, die an einem einzigen schlechten Tag scheitert.

Jeder gegen jeden liefert eine vollständige Rangliste und stellt sie quadratisch in Rechnung. Zwölf Meldungen spielen 66 Partien statt 11; 23 spielen 253 statt 22; 48 spielen 1 128 statt 47. Es braucht außerdem n − 1 Runden bei geradem n und n Runden bei ungeradem n, denn bei ungeradem Feld setzt in jeder Runde jemand aus. Der praktische Kompromiss der meisten großen Veranstaltungen ist eine Gruppenphase mit anschließendem Baum: Jeder gegen jeden in kleinen Gruppen erzeugt billig eine vertretbare Rangfolge, und das K.-o.-System kostet danach je ausgeschiedenem Qualifikanten eine Partie. Was auch immer du wählst: Rechne die Partienzahl aus, bevor du die Halle buchst — der Unterschied zwischen 99 und 4 950 ist kein Planungsdetail.

Häufige Fragen

Wie viele Freilose braucht ein Turnier mit 23 Meldungen?

Neun. Die Baumgröße ist die kleinste Zweierpotenz, die nicht unter 23 liegt, also 32, und die Freilosanzahl ist das minus die Meldezahl: 32 − 23 = 9. Die Formel ist allgemein — Freilose = 2^aufgerundet(log2 n) − n — und sie ist eine Subtraktion, keine Faustregel. Die erste Runde umfasst dann n minus den halben Baum, also 23 − 16 = 7 Partien, und die Rechnung schließt: 7 × 2 = 14 Personen spielen, 9 erhalten ein Freilos, 14 + 9 = 23, und 7 + 9 = 16 Überlebende gehen in die zweite Runde, genau der halbe Baum. Ab da gibt es keine Freilose mehr, weil das Feld wieder eine Zweierpotenz ist. Das ganze Turnier läuft über 5 Runden und 22 Partien.

Wie lautet die Standard-Setzreihenfolge für einen 16er-Baum?

1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11 — als acht Erstrundenpartien gelesen: 1 gegen 16, 8 gegen 9, 4 gegen 13, 5 gegen 12, 2 gegen 15, 7 gegen 10, 3 gegen 14, 6 gegen 11. Statt sie auswendig zu lernen, erzeuge sie: Beginne mit der Liste [1] und ersetze wiederholt jede Setzung s durch das Paar (s, m + 1 − s), wobei m die Größe ist, die die Liste gleich erreicht. Vier Verdopplungen ergeben die obige Reihenfolge, fünf die Reihenfolge für 32 Gesetzte und so weiter. Das Ergebnis ist prüfbar statt geglaubt — jede Erstrundenpaarung summiert sich zu 17, jedes Listenviertel zu 34 und jede Hälfte zu 68, die Nummern 1 und 2 landen in gegenüberliegenden Hälften und die Nummern 1 bis 4 in vier verschiedenen Vierteln.

Warum werden die Topgesetzten gegen die Letztgesetzten gepaart?

Um die Begegnungen zwischen starken Meldungen so weit wie möglich nach hinten zu schieben. 1 gegen 16 und 2 gegen 15 zu paaren, soll den Favoriten keinen leichten Auftakt schenken; es ist die einzige Art, sie so zu platzieren, dass sie sich nicht früh treffen können. Die Rekursion, die die Reihenfolge erzeugt, setzt die Nummern 1 und 2 in gegenüberliegende Hälften und die Nummern 1, 2, 3, 4 in vier verschiedene Viertel: Nummer 1 kann 2 oder 3 nur im Finale treffen und keine von 4, 5, 12 oder 13 vor dem Halbfinale. Verfolgt man die frühestmöglichen Gegner der Nummer 1 im 16er-Baum, ergibt sich 16 in Runde eins, 8 oder 9 in Runde zwei, eine von 4, 5, 12, 13 im Halbfinale und 2 oder 3 im Finale. Das Entwurfsziel ist ein Turnier, dessen beste Partien am Ende stattfinden — und es entsteht automatisch aus einer einzigen Ersetzungsregel.

Wie viele Partien braucht mein Turnier?

Beim K.-o.-System n − 1, und es gibt nichts nachzuschlagen. Jede Partie scheidet genau einen Teilnehmer aus, am Ende bleibt genau einer übrig, also haben genau n − 1 Ausscheidungen und damit n − 1 Partien stattgefunden. Freilose ändern nichts daran, denn ein Freilos ist keine Partie. Doppel-K.-o. verlangt, dass alle außer dem Sieger zweimal verlieren, also 2(n − 1) Niederlagen und damit 2n − 2 Partien; gewinnt die aus der Verliererrunde kommende Meldung das große Finale, wird ein Rücksetzspiel ausgetragen und die Gesamtzahl beträgt 2n − 1. Jeder gegen jeden lässt jedes Paar einmal spielen, also C(n,2) = n(n − 1)/2 Partien, über n − 1 Runden bei geradem n und n Runden bei ungeradem n. Bei 100 Meldungen kosten die drei Formate 99, 198 oder 199 und 4 950 Partien.

Sollen die Freilose an die Topgesetzten gehen?

Sie tun es bereits, wenn du den Baum richtig baust — du musst es nie gesondert entscheiden. Fülle den Baum bis zu seiner Zweierpotenzgröße mit Phantommeldungen auf, die höher nummeriert sind als die echten, erzeuge die Setzreihenfolge mit der Verdopplungsrekursion und lies ab, wer gegen ein Phantom antritt. Bei 100 Meldungen in einem 128er-Baum sind das genau die Setzungen 1 bis 28, zusammenhängend und der Reihe nach, denn dieselbe Ersetzung, die s mit m + 1 − s paart, stellt die höchsten Setzungen den höchstnummerierten Plätzen gegenüber — und genau die sind leer. Daraus folgt zweierlei. Erstens stammen die Zahl der Freilose und die Identität ihrer Empfänger aus einer Konstruktion, nicht aus zwei Regeln, die sich widersprechen können. Zweitens hat ein Generator, der Freilose über beliebige Meldungen streut, auch die Setzung zerstört und gehört ersetzt.