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)

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

\(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

\[\sum_{i=1}^{n}(w_i - \ell_i)^3 \geq 0. \tag{1}\]

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 :

\[S(T) = \sum_{i=1}^{n}(w_i - \ell_i)^3.\]

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

\[S(T) = \sum_{i_1, i_2, i_3, i_4} S(T_{i_1i_2i_3i_4}), \tag{2}\]

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

\[(w_i - \ell_i)^3 = \Big(\sum_{j \neq i}\varepsilon_{ij}\Big)^3 = \sum_{j_1, j_2, j_3 \neq i}\varepsilon_{ij_1}\varepsilon_{ij_2}\varepsilon_{ij_3}.\]

Donc

\[S(T) = \sum_{i \notin \{j_1, j_2, j_3\}}\varepsilon_{ij_1}\varepsilon_{ij_2}\varepsilon_{ij_3}.\]

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

\[S(T) = \sum_{\lvert \{i, j_1, j_2, j_3\} \rvert = 4}\varepsilon_{ij_1}\varepsilon_{ij_2}\varepsilon_{ij_3} + P(T)\sum_{i \neq j}\varepsilon_{ij} = S_1(T) + P(T)S_2(T).\]

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

\[S_1(T) = \sum_{i_1, i_2, i_3, i_4} S_1(T_{i_1i_2i_3i_4}). \tag{3}\]

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

\[\sum_{i=1}^{n}(w_i - \ell_i) = 0. \tag{4}\]

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

\[\sum_{i=1}^{n}\left(\binom{w_i}{2} - \binom{\ell_i}{2}\right) = 0. \tag{5}\]

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

\[\sum_{i=1}^{n}\left(\binom{w_i}{3} - \binom{\ell_i}{3}\right) \geq 0. \tag{6}\]

Écrivons maintenant l'énoncé (1) comme combinaison linéaire de (4), (5) et (6). On vérifie facilement que

\[(x - y)^3 = 24\left(\binom{x}{3} - \binom{y}{3}\right) + 24\left(\binom{x}{2} - \binom{y}{2}\right) - \big(3(x + y)^2 - 4\big)(x - y).\]

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

\[(w_i - \ell_i)^3 = 24\left(\binom{w_i}{3} - \binom{\ell_i}{3}\right) + 24\left(\binom{w_i}{2} - \binom{\ell_i}{2}\right) - \big(3(n - 1)^2 - 4\big)(w_i - \ell_i).\]

Alors

\[\sum_{i=1}^{n}(w_i - \ell_i)^3 = 24\underbrace{\sum_{i=1}^{n}\left(\binom{w_i}{3} - \binom{\ell_i}{3}\right)}_{\geq 0} + 24\underbrace{\sum_{i=1}^{n}\left(\binom{w_i}{2} - \binom{\ell_i}{2}\right)}_{0} - \big(3(n - 1)^2 - 4\big)\underbrace{\sum_{i=1}^{n}(w_i - \ell_i)}_{0} \geq 0. \qquad \blacksquare\]