Tableaux de tournoi : exemptions, têtes de série, et pourquoi les nombres doivent être des puissances de deux

Le tableau se divise par deux, il doit donc partir d'une puissance de deux

Un tour à élimination apparie tout le monde et renvoie la moitié chez elle. Pars de 16 et tu obtiens 8, puis 4, puis 2, puis 1 : quatre tours, aucun reste, personne d'inoccupé. Pars de 12 et le deuxième tour en compte 6, le troisième 3, et voilà trois joueurs impossibles à apparier. La structure ne se referme que si chaque tour a un nombre pair de survivants jusqu'en bas, et les seuls effectifs qui possèdent cette propriété sont les puissances de deux. Ce n'est pas une convention choisie par les organisateurs : c'est ce que fait la division par deux répétée, et c'est pourquoi tout tableau publié que tu as vu compte 8, 16, 32, 64 ou 128 places.

Le nombre de tours découle du même argument. Si le tableau contient 2^r inscrits, il faut r divisions par deux pour atteindre un vainqueur unique : r vaut donc log2 de la taille du tableau, et pour un effectif n quelconque la taille du tableau est la plus petite puissance de deux non inférieure à n. Autrement dit : tours = plafond(log2 n), taille = 2^plafond(log2 n). Douze inscrits jouent donc un tableau de 16 sur 4 tours ; 100 inscrits un tableau de 128 sur 7 ; 129 inscrits un tableau de 256 sur 8. Ce dernier saut résume tout le problème : le 129e inscrit n'ajoute pas un match au calendrier, il y ajoute un tour entier.

Les exemptions sont exactement l'écart jusqu'à la puissance de deux supérieure

Si le tableau a 2^plafond(log2 n) places et que seules n sont occupées par de vrais inscrits, les places restantes sont vides. Chaque place vide fait face à un inscrit réel, qui avance donc sans jouer : c'est une exemption. Le nombre d'exemptions est donc la soustraction, rien de plus : exemptions = 2^plafond(log2 n) − n. Vingt-trois inscrits dans un tableau de 32 donnent 9 exemptions ; 48 dans un tableau de 64 en donnent 16 ; 100 dans un tableau de 128 en donnent 28. Le nombre est maximal juste au-dessus d'une puissance de deux et nul exactement sur l'une d'elles, ce qui explique que 129 inscrits produisent 127 exemptions — plus d'exemptions que de personnes jouant réellement au premier tour.

Le premier tour est plus petit que la moitié du tableau d'exactement la même quantité. Si b inscrits sont exemptés, les n − b autres jouent, et ils jouent (n − b)/2 matchs ; en remplaçant b = 2^r − n on obtient matchs du premier tour = n − 2^(r − 1), soit n moins la moitié du tableau. Pour 100 inscrits cela fait 100 − 64 = 36 matchs, et la vérification boucle : 36 × 2 = 72 personnes jouent, 28 sont exemptées, 72 + 28 = 100, et 36 + 28 = 64 rescapés entrent au deuxième tour — exactement la moitié du tableau, là où la structure en puissance de deux reprend proprement. À partir du deuxième tour il n'y a plus aucune exemption, car l'effectif est de nouveau une puissance de deux par construction.

L'ordre des têtes de série sort d'une récurrence, pas d'une liste apprise

Pars d'un tableau à une place : l'ordre des têtes est [1]. Pour le doubler, prends chaque tête s d'un tableau qui va atteindre la taille m et remplace-la par la paire (s, m + 1 − s). Un doublement donne [1, 2]. Deux donnent [1, 4, 2, 3]. Trois donnent [1, 8, 4, 5, 2, 7, 3, 6]. Quatre donnent 1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11. Cinq donnent 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. Rien n'est appris par cœur, rien n'est cherché ailleurs : la récurrence tient en quatre lignes de code et produit l'ordre standard pour n'importe quelle taille de tableau.

Lis la ligne à seize têtes comme huit affiches de premier tour et le motif saute aux yeux : 1 c. 16, 8 c. 9, 4 c. 13, 5 c. 12, 2 c. 15, 7 c. 10, 3 c. 14, 6 c. 11. Chaque affiche totalise 17, soit la taille du tableau plus un, car c'est exactement ce qu'impose la substitution s vers (s, m + 1 − s). C'est la même règle à chaque niveau de l'arbre : la meilleure tête restante d'un bloc affronte toujours la plus faible restante, à chaque tour, sans qu'on ait à écrire une seconde règle.

Ce que le placement garantit réellement, vérifié plutôt qu'affirmé

Passe l'ordre engendré par quelques assertions et le dessin se révèle. Découpe l'ordre à seize têtes en blocs : tout bloc de même taille totalise le même nombre — 17 par paire, 34 par quart, 68 par moitié, 136 pour le tableau entier — soit toujours la taille du bloc multipliée par (n + 1) divisé par 2. Prends la meilleure tête de chaque bloc et tu retrouves l'ordre d'un tableau deux fois plus petit : les blocs de deux donnent 1, 8, 4, 5, 2, 7, 3, 6, c'est-à-dire l'ordre à huit têtes ; les blocs de quatre donnent 1, 4, 2, 3. Le tableau est auto-similaire, ce qu'une récurrence par doublement doit précisément produire.

La garantie qui intéresse vraiment en découle immédiatement. Les têtes 1 et 2 occupent des moitiés opposées : si toutes deux continuent de gagner, elles ne peuvent se croiser avant la finale ; les têtes 1, 2, 3 et 4 occupent quatre quarts différents, donc deux d'entre elles ne peuvent se rencontrer avant les demi-finales. Retracer les adversaires possibles les plus précoces de la tête 1 dans le tableau à seize donne 16 au premier tour, 8 ou 9 au deuxième, l'une de 4, 5, 12, 13 en demi-finale, et 2 ou 3 seulement en finale. Voilà le sens exact du placement : il ne protège pas le favori des adversaires forts, il les repousse, pour que les meilleurs matchs du tournoi tombent à la fin plutôt qu'au premier tour.

Le placement répartit aussi les exemptions sans règle supplémentaire. Remplis un tableau de 128 avec les inscrits 1 à 100 et des inscrits fantômes 101 à 128, engendre l'ordre par la récurrence, et lis quels inscrits réels affrontent un fantôme : ce sont exactement les têtes 1 à 28, contiguës, dans l'ordre. Personne n'a eu à décider que les exemptions iraient aux meilleures têtes — la substitution qui apparie s avec m + 1 − s place les têtes les plus hautes en face des places les plus élevées, qui sont précisément les places vides. Cela mérite vérification dans l'outil que tu utilises, car un générateur qui distribue les exemptions à des inscrits arbitraires a cassé le placement, pas seulement les exemptions.

Total des matchs : n − 1, pour tout n, en une ligne

Chaque match d'un tournoi à élimination directe élimine exactement un inscrit — c'est ce que veut dire élimination directe. À la fin, exactement un inscrit n'a pas été éliminé, donc exactement n − 1 l'ont été. Une élimination par match signifie donc exactement n − 1 matchs, quelle que soit la taille du tableau, quelles que soient les exemptions, quel que soit le placement. Vingt-trois inscrits jouent 22 matchs ; 100 inscrits en jouent 99 ; 129 inscrits en jouent 128. Tu n'as jamais à additionner les tours, et les exemptions n'entrent pas du tout dans le calcul, car une exemption n'est pas un match et n'élimine personne.

Le même argument de comptage tarife les autres formats. En double élimination, tout le monde sauf le champion doit perdre deux fois : il faut produire 2(n − 1) défaites, et comme chaque match produit exactement une défaite, le calendrier demande 2n − 2 matchs. Si le finaliste issu du tableau des perdants gagne la grande finale, il inflige au joueur jusque-là invaincu sa première défaite, et un match de remise à zéro se joue pour lui en donner une deuxième — 2n − 1 matchs dans ce cas. Les deux chiffres sont exacts, et lequel s'applique se décide le jour même. Le toutes rondes est une autre bête : chaque paire se rencontre une fois, donc le compte vaut C(n,2) = n(n − 1)/2, qui croît quadratiquement. À 100 inscrits, cela fait 4 950 matchs contre 99 pour une élimination directe, un facteur exactement 50.

Choisir un format à partir des nombres

Les trois formats échangent des matchs contre de l'information. L'élimination directe est le tournoi le moins cher possible — n − 1 matchs, plafond(log2 n) tours — et elle produit exactement un fait fiable : l'identité du vainqueur. Tout ce qui suit la première place est un artefact du tirage : les demi-finalistes battus ne sont pas départagés entre eux, et un inscrit fort qui croise le champion au deuxième tour finit de façon indiscernable d'un faible. La double élimination achète une seconde chance pour à peu près deux fois plus de matchs et environ un tour de plus, et elle supprime le pire mode de défaillance : un bon inscrit sorti par une seule mauvaise journée.

Le toutes rondes donne un classement complet et le facture de façon quadratique. Douze inscrits jouent 66 matchs au lieu de 11 ; 23 en jouent 253 au lieu de 22 ; 48 en jouent 1 128 au lieu de 47. Il demande aussi n − 1 tours quand n est pair et n tours quand n est impair, car avec un effectif impair quelqu'un se repose à chaque tour. Le compromis pratique de la plupart des grands événements est une phase de groupes suivie d'un tableau : le toutes rondes en petits groupes produit un classement défendable à bas coût, et l'élimination directe ne coûte ensuite qu'un match par qualifié éliminé. Quel que soit ton choix, calcule le nombre de matchs avant de réserver la salle — la différence entre 99 et 4 950 n'est pas un détail de planification.

Questions fréquentes

Combien d'exemptions faut-il pour un tournoi à 23 inscrits ?

Neuf. La taille du tableau est la plus petite puissance de deux non inférieure à 23, soit 32, et le nombre d'exemptions vaut cela moins l'effectif : 32 − 23 = 9. La formule est générale — exemptions = 2^plafond(log2 n) − n — et c'est une soustraction, pas une règle empirique. Le premier tour compte alors n moins la moitié du tableau, soit 23 − 16 = 7 matchs, et l'arithmétique boucle : 7 × 2 = 14 personnes jouent, 9 sont exemptées, 14 + 9 = 23, et 7 + 9 = 16 rescapés entrent au deuxième tour, exactement la moitié du tableau. À partir de là il n'y a plus d'exemptions, car l'effectif est de nouveau une puissance de deux. Le tournoi entier tient en 5 tours et 22 matchs.

Quel est l'ordre standard des têtes de série pour un tableau de 16 ?

1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11 — lu comme huit affiches de premier tour, cela donne 1 c. 16, 8 c. 9, 4 c. 13, 5 c. 12, 2 c. 15, 7 c. 10, 3 c. 14, 6 c. 11. Plutôt que de l'apprendre, engendre-le : pars de la liste [1] et remplace répétitivement chaque tête s par la paire (s, m + 1 − s), où m est la taille que la liste va atteindre. Quatre doublements donnent l'ordre ci-dessus ; cinq donnent l'ordre à 32 têtes, et ainsi de suite. Le résultat se vérifie au lieu d'être cru — chaque affiche du premier tour totalise 17, chaque quart de la liste totalise 34 et chaque moitié 68, les têtes 1 et 2 tombent dans des moitiés opposées, et les têtes 1 à 4 dans quatre quarts différents.

Pourquoi les meilleures têtes affrontent-elles les dernières ?

Pour repousser le plus tard possible les rencontres entre inscrits forts. Apparier 1 à 16 et 2 à 15 ne vise pas à offrir un début facile aux favoris ; c'est le seul moyen de les placer de sorte qu'ils ne puissent pas se croiser tôt. La récurrence qui produit l'ordre met les têtes 1 et 2 dans des moitiés opposées et les têtes 1, 2, 3, 4 dans quatre quarts différents : la tête 1 ne peut affronter 2 ou 3 qu'en finale et ne peut croiser aucune de 4, 5, 12 ou 13 avant la demi-finale. Retrace les adversaires possibles les plus précoces de la tête 1 dans un tableau de 16 et tu obtiens 16 au premier tour, 8 ou 9 au deuxième, l'une de 4, 5, 12, 13 en demie et 2 ou 3 en finale. L'objectif de conception est un tournoi dont les meilleurs matchs arrivent à la fin, et il découle automatiquement d'une seule règle de substitution.

Combien de matchs mon tournoi va-t-il demander ?

Pour l'élimination directe, n − 1, et il n'y a rien à chercher. Chaque match élimine exactement un inscrit, à la fin il en reste exactement un, donc exactement n − 1 éliminations et donc n − 1 matchs ont eu lieu. Les exemptions n'y changent rien, car une exemption n'est pas un match. La double élimination exige que tous sauf le champion perdent deux fois, soit 2(n − 1) défaites et donc 2n − 2 matchs ; si l'inscrit venu du tableau des perdants gagne la grande finale, un match de remise à zéro se joue et le total vaut 2n − 1. Le toutes rondes fait jouer chaque paire une fois, soit C(n,2) = n(n − 1)/2 matchs, sur n − 1 tours si n est pair et n tours si n est impair. Pour 100 inscrits, les trois formats coûtent respectivement 99, 198 ou 199, et 4 950 matchs.

Les exemptions doivent-elles aller aux meilleures têtes de série ?

Elles y vont déjà, si tu construis le tableau correctement — tu n'as jamais à en décider à part. Complète le tableau jusqu'à sa taille en puissance de deux avec des inscrits fantômes numérotés au-dessus des réels, engendre l'ordre par la récurrence de doublement, et lis qui affronte un fantôme. Pour 100 inscrits dans un tableau de 128, ce sont exactement les têtes 1 à 28, contiguës et dans l'ordre, car la substitution qui apparie s avec m + 1 − s place les têtes les plus hautes en face des places les plus élevées, qui sont précisément les vides. Deux conséquences. D'abord, le nombre d'exemptions et l'identité de ceux qui les reçoivent viennent d'une seule construction, pas de deux règles qui pourraient se contredire. Ensuite, un générateur qui disperse les exemptions parmi des inscrits arbitraires a aussi cassé le placement, et mérite d'être remplacé.