Exercice 26

1. Par récurrence sur le nombre $n \geqslant 2$ d'équipes. Pour $n = 2$, on nomme $E_{1}$ le vainqueur de l'unique match et $E_{2}$ le perdant. Supposons le résultat vrai pour $n$ équipes, et considérons un tournoi à $n + 1$ équipes. Mettons de côté une équipe $T$ ; les $n$ autres forment un tournoi, que l'on numérote $E_{1}$, …, $E_{n}$ comme voulu. Il reste à insérer $T$.

• Si $T$ a battu $E_{1}$, la liste $T$, $E_{1}$, …, $E_{n}$ convient.

• Sinon, $E_{1}$ a battu $T$, et l'ensemble des indices $i \in [\![1\,;n]\!]$ tels que $E_{i}$ ait battu $T$ est non vide. Soit $i$ son plus grand élément. Si $i = n$, la liste $E_{1}$, …, $E_{n}$, $T$ convient. Si $i < n$, l'équipe $E_{i+1}$ n'a pas battu $T$, donc $T$ a battu $E_{i+1}$, et la liste $E_{1}$, …, $E_{i}$, $T$, $E_{i+1}$, …, $E_{n}$ convient.

$$\boxed{\text{Tout tournoi admet un classement où chaque équipe a battu la suivante.}}$$ C'est le théorème de Rédei (1934). Une telle numérotation n'est pas un classement au sens sportif : l'équipe $E_{1}$ peut avoir perdu tous ses autres matchs.

2. Elle n'est pas unique en général : si trois équipes $a$, $b$, $c$ sont telles que $a$ bat $b$, $b$ bat $c$ et $c$ bat $a$, les numérotations $(a,b,c)$, $(b,c,a)$ et $(c,a,b)$ conviennent. On ne peut pas non plus toujours exiger que $E_{n}$ ait battu $E_{1}$ : si une équipe a gagné tous ses matchs, elle n'a été battue par personne et ne peut suivre aucune équipe dans un cycle. $$\boxed{\text{Non et non.}}$$

3. Chaque équipe dispute $n - 1$ matchs. Si le tournoi est équilibré, chacune en gagne autant qu'elle en perd, donc $n - 1$ est pair et $n$ est impair. Réciproquement, supposons $n = 2p + 1$, et numérotons les équipes par les restes $0$, $1$, …, $2p$ modulo $n$. Décidons que l'équipe $i$ bat les équipes $i + 1$, $i + 2$, …, $i + p$ (modulo $n$), et perd contre les $p$ autres. Ces résultats sont cohérents : pour deux équipes distinctes $i$ et $j$, la différence $j - i$ est congrue modulo $n$ à un unique $r \in [\![1\,;2p]\!]$ ; si $r \leqslant p$, l'équipe $i$ bat $j$, et alors $i - j \equiv n - r$ avec $n - r \geqslant p + 1$, de sorte que $j$ ne bat pas $i$ ; et inversement. Chaque équipe gagne ainsi $p$ matchs et en perd $p$. $$\boxed{\text{Un tournoi équilibré à } n \text{ équipes existe si et seulement si } n \text{ est impair.}}$$ Pour $n = 5$ : l'équipe $0$ bat $1$ et $2$, l'équipe $1$ bat $2$ et $3$, et ainsi de suite jusqu'à l'équipe $4$, qui bat $0$ et $1$.