Dans un tournoi, quelqu'un gagne beaucoup

Exercice d'entraînement · niveau 3 (difficile) · mathématiques appliquées (ECG 1re année), chapitre 3 — Théorie des graphes · Degrés et formule d'Euler

Énoncé

Dans un graphe orienté, le degré sortant $d^{+} (s)$ est le nombre d'arcs qui partent de $s$ , le degré entrant $d^{-} (s)$ le nombre d'arcs qui y arrivent. Montrer que $\sum_{s} d^{+} (s) = \sum_{s} d^{-} (s) = m$ . Dans un tournoi à $n$ joueurs (chaque paire joue une fois, l'arc allant du vainqueur au perdant), en déduire qu'un joueur gagne au moins $\frac{n - 1}{2}$ matchs.

Corrigé

Les deux sommes. Comptons de deux façons les couples formés d'un arc et de son origine. Chaque arc a exactement une origine : le total vaut $m$ . En regroupant par sommet, chaque sommet $s$ fournit $d^{+} (s)$ tels couples : le total vaut $\sum_{s} d^{+} (s)$ . Les deux comptages portant sur le même ensemble, $\sum_{s} d^{+} (s) = m$ . Le même raisonnement avec l'extrémité de l'arc donne $\sum_{s} d^{-} (s) = m$ .

Le tournoi. Chaque paire de joueurs donne exactement un arc, donc $m = \frac{n ( n - 1 )}{2},$ qui est le nombre de paires. Le degré sortant $d^{+} (s)$ est le nombre de victoires de $s$ .

La conclusion. Supposons par l'absurde que tout joueur gagne strictement moins de $\frac{n - 1}{2}$ matchs. Alors $m = s \sum d^{+} (s) < n \times \frac{n - 1}{2} = \frac{n ( n - 1 )}{2} = m,$ c'est-à-dire $m < m$ : contradiction. Il existe donc un joueur $s$ avec $d^{+} (s) \geq \frac{n - 1}{2}$ .

Le point délicat est la stricte inégalité : c'est parce que la majoration est stricte pour chaque terme, et qu'il y a au moins un terme, que la somme est strictement majorée. Le résultat s'énonce familièrement : dans un tournoi, il y a toujours un joueur au moins aussi bon que la moyenne — et la moyenne des victoires vaut exactement $\frac{n - 1}{2}$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.