Exercice 54

Modèle. Un tournoi est déterminé par le vainqueur de chacun des $\binom{n}{2}$ matchs ; on munit l'ensemble des $2^{\binom{n}{2}}$ tournois de la probabilité uniforme, ce qui revient, par la proposition 17, à considérer des matchs mutuellement indépendants, chacun gagné par l'une ou l'autre équipe avec la probabilité $\frac{1}{2}$. Un événement qui fixe l'issue de $m$ matchs donnés a donc la probabilité $2^{-m}$.

1.(a) Pour $i \in \llbracket 1\,,n \rrbracket$, l'événement $E_{i}$ « l'équipe $i$ a battu toutes les autres » fixe l'issue de $n - 1$ matchs : $\mathrm{P}(E_{i}) = 2^{-(n-1)}$. Les $E_{i}$ sont deux à deux incompatibles, puisque deux équipes ne peuvent pas s'être battues mutuellement. Par additivité, $$\boxed{\mathrm{P}\big(\text{une équipe a battu toutes les autres}\big) = \frac{n}{2^{n-1}}}$$

(b) Un classement est une permutation $\sigma \in \mathfrak{S}_{n}$, l'équipe $\sigma(1)$ étant classée première. L'événement $F_{\sigma}$ « pour $a < b$, l'équipe $\sigma(a)$ a battu l'équipe $\sigma(b)$ » fixe l'issue des $\binom{n}{2}$ matchs, et $\mathrm{P}(F_{\sigma}) = 2^{-\binom{n}{2}}$. Si $\sigma \neq \sigma'$, deux équipes sont classées dans des ordres différents par $\sigma$ et $\sigma'$, et leur match ne peut pas avoir les deux issues : les $F_{\sigma}$ sont deux à deux incompatibles. Par le théorème 1 et l'additivité, $$\boxed{\mathrm{P}\big(\text{les équipes peuvent être classées}\big) = \frac{n!}{2^{\binom{n}{2}}}}$$ Pour $n = 3$, on trouve $\frac{6}{8} = \frac{3}{4}$ : les deux tournois exclus sont ceux où $1$ bat $2$, $2$ bat $3$ et $3$ bat $1$, ou l'inverse. Pour $n = 10$, la probabilité vaut environ $1{,}0 \cdot 10^{-7}$.

(c) Pour $j \notin K$, l'événement $H_{j}$ « l'équipe $j$ a battu toutes les équipes de $K$ » fixe l'issue de $k$ matchs, et $\mathrm{P}(H_{j}) = 2^{-k}$. Les événements $H_{j}$, pour $j \notin K$, portent sur des ensembles de matchs deux à deux disjoints, les matchs entre $j$ et les équipes de $K$ : ils sont mutuellement indépendants par le lemme des coalitions (théorème 7) et la proposition 15, ainsi que leurs contraires (proposition 10 (iii)). La probabilité qu'aucune des $n - k$ équipes hors de $K$ ne convienne vaut donc $(1 - 2^{-k})^{n-k}$, et $$\boxed{\mathrm{P}\big(\text{une équipe hors de } K \text{ a battu toutes celles de } K\big) = 1 - \big(1 - 2^{-k}\big)^{n-k}}$$

2. On suppose $n > k$. Le tournoi n'est pas $k$-indécis si et seulement s'il existe un ensemble $K$ de $k$ équipes qu'aucune autre équipe n'a toutes battues. Par la sous-additivité (proposition 7 (iv)) et la question 1(c), en sommant sur les $\binom{n}{k}$ ensembles $K$, $$1 - \mathrm{P}(\text{le tournoi est } k\text{-indécis}) \leqslant \binom{n}{k}\big(1 - 2^{-k}\big)^{n-k} \leqslant \frac{n^{k}q^{n}}{q^{k}}, \qquad q = 1 - 2^{-k} \in \left]0\,,1\right[,$$ puisque $\binom{n}{k} = \frac{n(n - 1)\cdots(n - k + 1)}{k!} \leqslant n^{k}$. En écrivant $q^{n} = \mathrm{e}^{-\gamma n}$ avec $\gamma = -\ln q > 0$, les croissances comparées (chapitre 10, proposition 2) donnent $n^{k}q^{n} \to 0$, d'où $$\boxed{\mathrm{P}(\text{un tournoi aléatoire de taille } n \text{ est } k\text{-indécis}) \xrightarrow[n \to +\infty]{} 1}$$

3. Pour $n$ assez grand, cette probabilité est strictement positive, donc l'événement correspondant n'est pas vide : il existe un tournoi $k$-indécis à $n$ équipes. C'est la méthode probabiliste : on prouve l'existence d'un objet sans le construire, en montrant qu'un objet tiré au hasard a la propriété voulue avec une probabilité non nulle. Pour $k = 2$, il suffit que la majoration de la question 2 soit strictement inférieure à $1$ ; le programme suivant cherche le plus petit tel $n$.

from math import comb

def taille(k):
    n = k + 1
    while comb(n, k) * (1 - 2**-k)**(n - k) >= 1:
        n += 1
    return n

print(taille(2), taille(3))      # affiche 21 91

$$\boxed{\text{pour } n = 21, \ \binom{21}{2}\Big(\frac{3}{4}\Big)^{19} \approx 0{,}888 < 1 : \text{il existe un tournoi } 2\text{-indécis à } 21 \text{ équipes}}$$ tandis que $\binom{20}{2}\big(\frac{3}{4}\big)^{18} \approx 1{,}071$ ne permet pas de conclure pour $n = 20$. Le calcul en fractions exactes donne les mêmes seuils, $21$ pour $k = 2$ et $91$ pour $k = 3$.

À retenir. La majoration ne donne qu'une taille suffisante. Par une recherche exhaustive, aucun des $2^{15} = 32\,768$ tournois à $6$ équipes n'est $2$-indécis, et le tournoi à $7$ équipes où $i$ bat $j$ lorsque $j - i$ est congru à $1$, $2$ ou $4$ modulo $7$ l'est : la plus petite taille est $7$. La méthode probabiliste est grossière, mais elle s'applique à tout $k$, alors qu'une construction explicite est délicate.