Shortlist 2010, C5¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : South Korea
Concepts : Double comptage · Graphes : degrés, chemins, arbres
Solution officielle : Shortlist officielle 2010 (avec solutions), p. 31 (page 32 du PDF)
Énoncé¶
\(n \geq 4\) joueurs ont participé à un tournoi de tennis. Deux joueurs quelconques se sont affrontés exactement une fois, sans match nul. On dit qu'un groupe de quatre joueurs est mauvais si l'un des joueurs a été battu par les trois autres, et si chacun de ces trois joueurs a gagné un match et en a perdu un contre les deux autres. On suppose qu'il n'y a pas de groupe mauvais dans ce tournoi. Soient \(w_i\) et \(\ell_i\) respectivement le nombre de victoires et le nombre de défaites du \(i\)-ième joueur. Montrer que
Énoncé original (anglais)
\(n \geq 4\) players participated in a tennis tournament. Any two players have played exactly one game, and there was no tie game. We call a company of four players bad if one player was defeated by the other three players, and each of these three players won a game and lost another game among themselves. Suppose that there is no bad company in this tournament. Let \(w_i\) and \(\ell_i\) be respectively the number of wins and losses of the \(i\)th player. Prove that
Indices : les idées clés
- Cas de \(4\) joueurs : on vérifie à la main que \(S(T) \geq 0\) pour un tournoi de \(4\) joueurs sans groupe mauvais.
- Développement : \((w_i - \ell_i)^3 = \sum \varepsilon_{ij_1}\varepsilon_{ij_2}\varepsilon_{ij_3}\) ; les termes à indices répétés s'annulent par paires, et chaque terme restant apparaît dans exactement un sous-tournoi de \(4\) joueurs, donc \(S(T) = \sum S(T_{i_1i_2i_3i_4})\).
- Solution 2 : on compte champions et perdants locaux des groupes de \(2\), \(3\) et \(4\) joueurs, puis on écrit \((x - y)^3\) comme combinaison de \(\binom{x}{3} - \binom{y}{3}\), \(\binom{x}{2} - \binom{y}{2}\) et \(x - y\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2010 (deux solutions).
Solution 1¶
Pour tout tournoi \(T\) vérifiant la condition du problème, notons \(S(T)\) la somme considérée :
Montrons d'abord que l'énoncé est vrai pour un tournoi \(T\) de seulement \(4\) joueurs. Soit \(A = (a_1, a_2, a_3, a_4)\) la suite des nombres de victoires des joueurs ; on peut supposer \(a_1 \geq a_2 \geq a_3 \geq a_4\). On a \(a_1 + a_2 + a_3 + a_4 = \binom{4}{2} = 6\), donc \(a_4 \leq 1\). Si \(a_4 = 0\), on ne peut pas avoir \(a_1 = a_2 = a_3 = 2\), sinon le groupe de tous les joueurs serait mauvais. On doit donc avoir \(A = (3, 2, 1, 0)\), et \(S(T) = 3^3 + 1^3 + (-1)^3 + (-3)^3 = 0\). D'autre part, si \(a_4 = 1\), seules deux possibilités, \(A = (3, 1, 1, 1)\) et \(A = (2, 2, 1, 1)\), peuvent se produire. Dans le premier cas, \(S(T) = 3^3 + 3 \cdot (-2)^3 > 0\), et dans le second \(S(T) = 1^3 + 1^3 + (-1)^3 + (-1)^3 = 0\), comme voulu.
Passons au problème général. Considérons un tournoi \(T\) sans groupe mauvais et numérotons les joueurs de \(1\) à \(n\). Pour quatre joueurs \(i_1, i_2, i_3, i_4\), considérons le « sous-tournoi » \(T_{i_1i_2i_3i_4}\) formé de ces seuls joueurs et des parties qu'ils ont jouées entre eux. D'après ce qui précède, \(S(T_{i_1i_2i_3i_4}) \geq 0\). Notre but est de prouver que
où la somme porte sur tous les quadruplets de nombres distincts de l'ensemble \(\{1, \ldots, n\}\). L'énoncé du problème en découlera.
Interprétons le nombre \((w_i - \ell_i)^3\) de la façon suivante. Pour \(i \neq j\), posons \(\varepsilon_{ij} = 1\) si le \(i\)-ième joueur a battu le \(j\)-ième, et \(\varepsilon_{ij} = -1\) sinon. Alors
Donc
Pour simplifier cette expression, considérons tous les termes de cette somme où deux indices sont égaux. Si, par exemple, \(j_1 = j_2\), le terme contient \(\varepsilon_{ij_1}^2 = 1\), et l'on peut remplacer ce terme par \(\varepsilon_{ij_3}\). Faisons ces remplacements pour tous ces termes ; évidemment, après ce changement, chaque terme de la forme \(\varepsilon_{ij_3}\) apparaît \(P(T)\) fois, donc
Montrons que \(S_2(T) = 0\), de sorte que \(S(T) = S_1(T)\) pour tout tournoi. En effet, \(\varepsilon_{ij} = -\varepsilon_{ji}\), et la somme se découpe en paires de ce type. Comme la somme de chaque paire est nulle, \(S_2(T)\) l'est aussi.
L'égalité (2) s'écrit donc
Or, si les nombres \(j_1, j_2, j_3\) sont tous distincts, l'ensemble \(\{i, j_1, j_2, j_3\}\) est contenu dans exactement un quadruplet, donc le terme \(\varepsilon_{ij_1}\varepsilon_{ij_2}\varepsilon_{ij_3}\) apparaît exactement une fois dans le membre de droite de (3), ainsi que dans le membre de gauche. Il n'y a évidemment pas d'autres termes dans les deux membres, donc l'égalité est établie. \(\blacksquare\)
Solution 2¶
Comme dans la première solution, on appelle groupes les ensembles de joueurs, et \(k\)-groupes les groupes de \(k\) éléments.
Dans tout groupe de joueurs, on appelle champion local du groupe un joueur qui a battu tous les autres membres du groupe. De même, si un joueur a perdu toutes ses parties contre les autres membres du groupe, on l'appelle perdant local du groupe. Évidemment, tout groupe a au plus un champion local et au plus un perdant local. D'après la condition du problème, dès qu'un \(4\)-groupe a un perdant local, il a aussi un champion local.
Soit \(k\) un entier strictement positif ; comptons tous les cas où un joueur est champion local d'un \(k\)-groupe. Le \(i\)-ième joueur a battu \(w_i\) autres joueurs. Pour être champion local d'un \(k\)-groupe, il doit en être membre, et les \(k - 1\) autres membres doivent être choisis parmi ceux qu'il a battus. Le \(i\)-ième joueur est donc champion local de \(\binom{w_i}{k-1}\) \(k\)-groupes. Le nombre total de champions locaux de tous les \(k\)-groupes est donc \(\sum_{i=1}^{n}\binom{w_i}{k-1}\). De même, le nombre total de perdants locaux des \(k\)-groupes est \(\sum_{i=1}^{n}\binom{\ell_i}{k-1}\).
Appliquons cela pour \(k = 2\), \(3\) et \(4\).
Comme chaque partie a un vainqueur et un perdant, \(\sum_{i=1}^{n} w_i = \sum_{i=1}^{n}\ell_i = \binom{n}{2}\), donc
Dans tout \(3\)-groupe, ou bien les joueurs se sont battus en cycle, ou bien le groupe a à la fois un champion local et un perdant local. Le nombre total de champions locaux et celui de perdants locaux dans les \(3\)-groupes sont donc égaux : \(\sum_{i=1}^{n}\binom{w_i}{2} = \sum_{i=1}^{n}\binom{\ell_i}{2}\). On a donc
Dans tout \(4\)-groupe, d'après la condition du problème, le nombre de perdants locaux est inférieur ou égal au nombre de champions locaux. Il en est donc de même des nombres totaux de champions et de perdants locaux dans tous les \(4\)-groupes : \(\sum_{i=1}^{n}\binom{w_i}{3} \geq \sum_{i=1}^{n}\binom{\ell_i}{3}\). Donc
Écrivons maintenant l'énoncé (1) comme combinaison linéaire de (4), (5) et (6). On vérifie facilement que
Appliquons cette identité à \(x = w_i\) et \(y = \ell_i\) (le livret écrit \(x = w_1\)). Comme chaque joueur a joué \(n - 1\) parties, \(w_i + \ell_i = n - 1\), et donc
Alors
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2011 C4 ★★☆☆☆ : En combien de parties au plus peut-on couper \(\mathbb{N}^*\) pour que chacune écrive tout \(n \geq 15\) comme somme de deux de ses éléments ?
- 2023 A5 ★★★☆☆ : Une permutation de \(1, \ldots, 2023\) dont les écarts successifs sont tous distincts commence ou finit par au moins \(507\).
- 2013 A4 ★★★☆☆ : Une suite périodique presque croissante vérifiant \(a_{a_i} \leq n + i - 1\) a une somme au plus \(n^2\).
- 2022 C8 ★★★★☆ · OIM P6 : Remplir un tableau \(n \times n\) de \(1\) à \(n^2\) avec le moins possible de chemins croissants partant d'un minimum local.