Shortlist 2017, A5

Domaine : Algèbre · Difficulté : ★★★☆☆ · Proposé par : Serbia

Concepts : Graphes : degrés, chemins, arbres · Double comptage

Solution officielle : Shortlist officielle 2017 (avec solutions), p. 21 (page 23 du PDF)

Figures reprises du livret officiel de la Shortlist.

Énoncé

An integer \(n \geq 3\) is given. We call an \(n\)-tuple of real numbers \((x_1, x_2, \ldots, x_n)\) Shiny if for each permutation \(y_1, y_2, \ldots, y_n\) of these numbers we have

\[\sum_{i=1}^{n-1} y_i y_{i+1} = y_1y_2 + y_2y_3 + y_3y_4 + \cdots + y_{n-1}y_n \geq -1.\]

Find the largest constant \(K = K(n)\) such that

\[\sum_{1 \leq i < j \leq n} x_i x_j \geq K\]

holds for every Shiny \(n\)-tuple \((x_1, x_2, \ldots, x_n)\).

Indices : les idées clés

• Un exemple limite : \(x_1 = -\frac{1}{2t}\) et \(x_2 = \cdots = x_n = t\) avec \(t \to 0^+\) montre que \(K\) ne peut pas dépasser \(-\frac{n-1}{2}\).
• Graphes (solution 1) : on décompose les arêtes du graphe complet sur \(z_1, \ldots, z_n\) en \(\lfloor \frac{n-1}{2} \rfloor\) chemins hamiltoniens (chacun \(\geq -1\)) et un reste \(L\) que l'on contrôle.
• Séparer les nombres négatifs et positifs : après tri, les produits de deux nombres de même signe sont \(\geq 0\).
• Double comptage (solution 2) : on moyenne \(y_1y_2 + \cdots + y_{n-1}y_n\) sur une famille de permutations, en comptant combien de fois chaque produit apparaît.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2017 (deux solutions).

Réponse. \(K = -\dfrac{n-1}{2}\).

Solution 1

On ne peut pas prendre \(K\) plus grand. Soit \(t > 0\) ; prenons \(x_2 = x_3 = \cdots = x_n = t\) et \(x_1 = -\frac{1}{2t}\). Chaque produit \(x_ix_j\) (\(i \neq j\)) vaut \(t^2\) ou \(-\frac12\). Donc, pour toute permutation \((y_i)\) des \(x_i\) (au plus deux produits consécutifs contiennent \(x_1\)),

\[y_1y_2 + \cdots + y_{n-1}y_n \geq (n-3)t^2 - 1 \geq -1,\]

et le \(n\)-uplet est Shiny. Or

\[\sum_{i<j} x_ix_j = -\frac{n-1}{2} + \frac{(n-1)(n-2)}{2}t^2.\]

Quand \(t\) tend vers \(0\) par valeurs positives, cette somme s'approche autant qu'on veut de \(-\frac{n-1}{2}\). Donc \(K \leq -\frac{n-1}{2}\). Il reste à montrer que \(\sum_{i<j} x_ix_j \geq -\frac{n-1}{2}\) pour tout \(n\)-uplet Shiny.

Découpage en chemins hamiltoniens. Désormais \((x_1, \ldots, x_n)\) est Shiny. Soit \((z_i)_{1 \leq i \leq n}\) une permutation des \(x_i\) que l'on choisira plus tard ; les indices des \(z_i\) sont toujours pris modulo \(n\). On découpe la somme \(\sum_{i<j} x_ix_j = \sum_{i<j} z_iz_j\) en \(\lfloor \frac{n-1}{2} \rfloor\) expressions, chacune de la forme \(y_1y_2 + \cdots + y_{n-1}y_n\) pour une permutation \((y_i)\) des \(z_i\), plus des termes restants. Plus précisément, en regroupant les paires \(\{i, j\}\) selon la classe de \(i + j\) modulo \(n\) :

\[\sum_{i<j} z_iz_j = \sum_{q=0}^{n-1} \sum_{\substack{i + j \equiv q \ (\mathrm{mod}\ n) \\ i \not\equiv j \ (\mathrm{mod}\ n)}} z_iz_j = \sum_{p=1}^{\lfloor \frac{n-1}{2} \rfloor} \sum_{\substack{i + j \equiv 2p-1,\, 2p \ (\mathrm{mod}\ n) \\ i \not\equiv j \ (\mathrm{mod}\ n)}} z_iz_j + L, \tag{1}\]

où \(L\) est la somme des \(z_iz_j\) (\(i \not\equiv j\)) pour les classes restantes : \(i + j \equiv 0\) si \(n\) est impair, \(i + j \equiv 0\) ou \(-1\) si \(n\) est pair. Ainsi, si \(n\) est impair,

\[L = z_1z_{-1} + z_2z_{-2} + \cdots + z_{(n-1)/2}\,z_{-(n-1)/2},\]

et si \(n\) est pair, \(L\) est la somme des \(n - 1\) produits consécutifs le long du chemin \(z_0, z_{-1}, z_1, z_{-2}, z_2, \ldots, z_{-(n-2)/2}, z_{(n-2)/2}, z_{n/2}\) :

\[L = z_0z_{-1} + z_{-1}z_1 + z_1z_{-2} + z_{-2}z_2 + \cdots + z_{(n-2)/2}\,z_{n/2}.\]

Le livret écrit \(L = z_1z_{-1} + z_1z_{-2} + z_2z_{-2} + \cdots + z_{(n-2)/2}z_{-n/2}\) pour \(n\) pair, ce qui omet le terme \(z_0z_{-1}\) (il faut \(n-1\) termes) ; nous rétablissons ce terme ici et dans le cas 2 ci-dessous.

Pour chaque \(p = 1, 2, \ldots, \lfloor \frac{n-1}{2} \rfloor\), il existe une permutation \((y_i)\) des \(z_i\) telle que

\[\sum_{\substack{i + j \equiv 2p-1,\, 2p \ (\mathrm{mod}\ n) \\ i \not\equiv j \ (\mathrm{mod}\ n)}} z_iz_j = \sum_{k=1}^{n-1} y_ky_{k+1} :\]

il suffit de prendre \(y_{2i-1} = z_{i+p-1}\) pour \(1 \leq i \leq \frac{n+1}{2}\) et \(y_{2i} = z_{p-i}\) pour \(1 \leq i \leq \frac n2\) (les sommes d'indices consécutifs valent alternativement \(2p - 1\) et \(2p\)). En termes de graphes : chaque produit \(z_iz_j\) est une arête du graphe complet sur les sommets \(z_1, \ldots, z_n\), et chaque groupe de (1) est un chemin hamiltonien (voir les figures pour \(n = 6, 7\)).

Comme les \(z_i\) forment un \(n\)-uplet Shiny, (1) donne

\[\sum_{i<j} z_iz_j \geq -\left\lfloor \frac{n-1}{2} \right\rfloor + L.\]

Il reste à montrer qu'il existe une permutation \((z_i)\) des \(x_i\) telle que \(L \geq 0\) si \(n\) est impair, et \(L \geq -\frac12\) si \(n\) est pair (dans les deux cas on obtient alors \(\sum_{i<j} x_ix_j \geq -\frac{n-1}{2}\)). Comme on n'a encore rien supposé sur l'ordre des \(x_i\), on peut supposer

\[x_1 \leq x_2 \leq \cdots \leq x_k \leq 0 \leq x_{k+1} \leq \cdots \leq x_n. \tag{2}\]

Cas 1 : \(n\) impair. Quitte à changer tous les \(x_i\) en leurs opposés, on peut supposer \(k\) pair. Alors \(x_1x_2, x_3x_4, \ldots, x_{n-2}x_{n-1} \geq 0\), car les facteurs de chaque produit sont de même signe. Posons \(L = x_1x_2 + x_3x_4 + \cdots + x_{n-2}x_{n-1} \geq 0\), et choisissons les \(z_i\) pour que cette définition coïncide avec celle des termes restants de (1) : on renumérote les \(x_i\) en \(z_i\) de sorte que

\[\{z_1, z_{n-1}\}, \{z_2, z_{n-2}\}, \ldots, \{z_{(n-1)/2}, z_{(n+1)/2}\}\]

soient, dans un certain ordre, les paires \(\{x_1, x_2\}, \{x_3, x_4\}, \ldots, \{x_{n-2}, x_{n-1}\}\), et \(z_n = x_n\). On a alors bien \(L = z_1z_{n-1} + \cdots + z_{(n-1)/2}z_{(n+1)/2}\).

Cas 2 : \(n\) pair. Posons \(L = x_1x_2 + x_2x_3 + \cdots + x_{n-1}x_n\). Quitte à changer les signes, on peut supposer \(k \neq 1\). Alors

\[2L = (x_1x_2 + \cdots + x_{n-1}x_n) + (x_1x_2 + \cdots + x_{n-1}x_n) \geq (x_2x_3 + \cdots + x_{n-1}x_n) + x_kx_{k+1} \geq x_2x_3 + \cdots + x_{n-1}x_n + x_nx_1 \geq -1.\]

La première inégalité vient de ce que le seul terme négatif de \(L\) est \(x_kx_{k+1}\) (et \(x_1x_2 \geq 0\) car \(k \neq 1\)) ; la deuxième de \(x_1 \leq x_k \leq 0 \leq x_{k+1} \leq x_n\) ; la troisième de ce que les \(x_i\) sont Shiny (c'est la somme le long de la permutation \(x_2, x_3, \ldots, x_n, x_1\)). Donc \(L \geq -\frac12\). On choisit les \(z_i\) pour que cette définition de \(L\) coïncide avec les termes restants de (1) : on pose \(x_1 = z_0\), \(x_{2i} = z_{-i}\) et \(x_{2i+1} = z_i\) (indices modulo \(n\)). Alors

\[L = \sum_{\substack{i + j \equiv 0,\, -1 \ (\mathrm{mod}\ n) \\ i \not\equiv j \ (\mathrm{mod}\ n)}} z_iz_j,\]

comme voulu. Le livret écrit \(x_{2i-1} = z_{-i}\), \(x_{2i} = z_i\), ce qui donnerait le même indice \(\pm\frac n2\) à \(x_{n-1}\) et \(x_n\) ; nous corrigeons en décalant d'un cran. \(\blacksquare\)

Solution 2

On donne une autre preuve de \(\sum_{i<j} x_ix_j \geq -\frac{n-1}{2}\) pour tout \(n\)-uplet Shiny. On ordonne les \(x_i\) comme dans (2) et on pose \(\ell = n - k\). Sans perte de généralité (quitte à changer les signes), \(k \geq \ell\). On suppose aussi \(k \neq n\) (sinon tous les \(x_i\) sont \(\leq 0\) et l'inégalité est triviale). Soient \(S = \{1, \ldots, k\}\) et \(T = \{k+1, \ldots, n\}\), et

\[K = \sum_{\substack{i<j \\ i, j \in S}} x_ix_j, \qquad M = \sum_{\substack{i \in S \\ j \in T}} x_ix_j, \qquad L = \sum_{\substack{i<j \\ i, j \in T}} x_ix_j.\]

Par définition, \(K, L \geq 0\) et \(M \leq 0\). On veut montrer \(K + L + M \geq -\frac{n-1}{2}\).

Cas 1 : \(k > \ell\). Considérons toutes les permutations \(\phi\) de \(\{1, \ldots, n\}\) telles que \(\phi^{-1}(T) = \{2, 4, \ldots, 2\ell\}\) (les éléments de \(T\) occupent les positions \(2, 4, \ldots, 2\ell\)) ; il y en a \(k!\,\ell!\). Posons

\[f(\phi) = \sum_{i=1}^{n-1} x_{\phi(i)}x_{\phi(i+1)}.\]

On sait que \(f(\phi) \geq -1\) pour chaque telle \(\phi\). En faisant la moyenne sur toutes ces \(\phi\) :

\[-1 \leq \frac{1}{k!\,\ell!}\sum_\phi f(\phi) = \frac{2\ell}{k\ell}M + \frac{2(k - \ell - 1)}{k(k-1)}K,\]

l'égalité venant d'un double comptage : \(M\) contient \(k\ell\) produits, dont \(2\ell\) apparaissent dans chaque \(f(\phi)\), et \(K\) contient \(\frac{k(k-1)}{2}\) produits, dont \(k - \ell - 1\) apparaissent dans chaque \(f(\phi)\) ; par symétrie, chaque produit apparaît aussi souvent que les autres de sa catégorie. On en déduit

\[K + L + M \geq K + L + \left(-\frac k2 - \frac{k - \ell - 1}{k - 1}K\right) = -\frac k2 + \frac{\ell}{k-1}K + L.\]

Comme \(k \leq n - 1\) et \(K, L \geq 0\), on obtient l'inégalité voulue.

Cas 2 : \(k = \ell = \frac n2\). On procède de même avec toutes les permutations \(\phi\) telles que \(\phi^{-1}(T) = \{2, 4, \ldots, 2\ell\}\), et le même \(f\). Comme dans le cas 1,

\[-1 \leq \frac{1}{k!\,\ell!}\sum_\phi f(\phi) = \frac{2\ell - 1}{k\ell}M,\]

car \(M\) contient \(k\ell\) produits, dont \(2\ell - 1\) apparaissent dans chaque \(f(\phi)\). Donc

\[K + L + M \geq M \geq -\frac{n^2}{4(n-1)} \geq -\frac{n-1}{2},\]

la dernière inégalité étant vraie car \(n \geq 4\). \(\blacksquare\)