Shortlist 2025, C5

Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Germany

Concepts : Bijections et dénombrement

Solution officielle : Shortlist officielle 2025 (avec solutions), section C5 (livret PDF)

Figures reprises du livret officiel de la Shortlist.

Énoncé

Let \(n\) be a positive integer, and let \((a_1, a_2, \ldots, a_n)\) be any \(n\)-tuple of distinct integers. An inversion is a pair \((i, j)\) of integers satisfying \(1 \leq i < j \leq n\) and \(a_i > a_j\). An inversion \((i, j)\) is called odd if \(j - i\) is odd. Let \(A\) be the number of all inversions, and let \(B\) be the number of odd inversions.

(a) Prove that \(A \leq 5B\) for all \(n\) and all \(n\)-tuples \((a_1, a_2, \ldots, a_n)\).

(b) Prove that there exist an \(n\) and an \(n\)-tuple \((a_1, a_2, \ldots, a_n)\) for which \(A > 4.99B\).

Indices : les idées clés

• Bijections et dénombrement : on répartit les inversions en cinq types et l'on construit, pour chacun des quatre types d'inversions paires, une injection vers les inversions impaires, en utilisant le « milieu » \(\frac{i+j}{2}\) ou \(\frac{i+j}{2} - 1\).
• Parité de \(\frac{j - i}{2}\) : selon que \(i \equiv j + 2\) ou \(i \equiv j \pmod 4\), c'est \(\frac{i+j}{2}\) ou \(\frac{i+j}{2} - 1\) qui est à distance impaire de \(i\) et de \(j\).
• Construction par blocs (b) : termes pairs et impairs décroissants par blocs décalés de \(2m\), de sorte que presque toutes les inversions soient entre indices de même parité ; on compte ensuite précisément.

Solutions

La solution ci-dessous suit la solution officielle de la Shortlist 2025 (une solution).

Solution

On dit qu'une inversion \((i, j)\) est paire si elle n'est pas impaire.

(a) On classe les inversions \((i, j)\) en cinq types :

1. les inversions impaires ;
2. les inversions paires avec \(i \equiv j + 2 \pmod 4\) et \(a_i > a_{(i+j)/2}\) ;
3. les inversions paires avec \(i \equiv j + 2 \pmod 4\) et \(a_i < a_{(i+j)/2}\) ;
4. les inversions paires avec \(i \equiv j \pmod 4\) et \(a_i > a_{(i+j)/2 - 1}\) ;
5. les inversions paires avec \(i \equiv j \pmod 4\) et \(a_i < a_{(i+j)/2 - 1}\).

Chaque inversion est d'exactement un type (les \(a_i\) sont distincts). Soit \(\mathcal{B}_k\) l'ensemble des inversions de type \(k\) et \(B_k\) son cardinal. Alors \(B = B_1\) et \(A = B_1 + B_2 + B_3 + B_4 + B_5\). Pour montrer \(A \leq 5B\), il suffit de montrer \(B_k \leq B_1\) pour \(k = 2, \ldots, 5\), en construisant une injection de \(\mathcal{B}_k\) dans \(\mathcal{B}_1\).

• Type 2. On envoie \((i, j)\) sur \(\left(i, \frac{i+j}{2}\right)\). Cette application est clairement injective, et \(\left(i, \frac{i+j}{2}\right)\) est une inversion impaire : \(a_i > a_{(i+j)/2}\) et \(\frac{i+j}{2} - i = \frac{j - i}{2}\) est impair puisque \(i \equiv j + 2 \pmod 4\).
• Type 3. On envoie \((i, j)\) sur \(\left(\frac{i+j}{2}, j\right)\). C'est injectif, et c'est une inversion impaire : \(a_{(i+j)/2} > a_i > a_j\), et \(j - \frac{i+j}{2} = \frac{j-i}{2}\) est impair.
• Type 4. On envoie \((i, j)\) sur \(\left(i, \frac{i+j}{2} - 1\right)\) ; comme pour le type 2, c'est bien défini et injectif (\(\frac{i+j}{2} - 1 - i = \frac{j-i}{2} - 1\) est impair car \(i \equiv j \pmod 4\), et \(\frac{i+j}{2} - 1 > i\) car \(j - i \geq 4\)).
• Type 5. On envoie \((i, j)\) sur \(\left(\frac{i+j}{2} - 1, j\right)\) ; comme pour le type 3, c'est bien défini et injectif.

Donc \(A \leq 5B\). \(\square\)

(b) On prend \(n = 4mk\) avec \(m, k\) entiers positifs, et pour \(1 \leq i \leq n\) :

• si \(i\) est pair et \(s\) est l'unique entier tel que \(4sm < i \leq (4s + 4)m\), on pose \(a_i = (6s + 2)m - \frac{i}{2}\) ;
• si \(i\) est impair et \(s\) est l'unique entier tel que \((4s - 2)m < i < (4s + 2)m\), on pose \(a_i = (6s - 1)m - \frac{i + 1}{2}\).

(Voir la figure pour le cas \(m = 4\), \(k = 3\).) Si \(i\) est pair, \(a_i \in [4sm, 4sm + 2m[\) ; si \(i\) est impair, \(a_i \in [4sm - 2m, 4sm[\). Il en résulte que les \(a_i\) sont distincts.

Soit \(C\) le nombre d'inversions paires ; il suffit de montrer \(C > 3.99B\) pour certains \(m, k\) (car \(A = B + C\)).

Inversions paires.

• Si \(i\) et \(j\) sont pairs, \((i, j)\) est une inversion si et seulement s'il existe \(s\) avec \(4sm < i < j \leq (4s + 4)m\) ; il y en a \(k\binom{2m}{2}\).
• Si \(i\) et \(j\) sont impairs, \((i, j)\) est une inversion si et seulement s'il existe \(s\) avec \((4s - 2)m < i < j < (4s + 2)m\) ; en ne comptant que \(1 \leq s \leq k - 1\), il y en a au moins \((k - 1)\binom{2m}{2}\).

Ainsi \(C \geq (2k - 1)\binom{2m}{2}\).

Inversions impaires.

• Si \(i\) est pair et \(j\) impair, \((i, j)\) est une inversion si et seulement s'il existe \(s\) avec \(4sm < i < j < (4s + 2)m\) ; pour chaque \(s\), il y a au plus \(\binom{m}{2}\) tels couples, donc au plus \(k\binom{m}{2}\) au total.
• Si \(i\) est impair et \(j\) pair, \((i, j)\) est une inversion si et seulement s'il existe \(s\) avec \((4s + 2)m < i < j \leq (4s + 4)m\) ; pour chaque \(s\), il y a au plus \(\binom{m+1}{2}\) tels couples, donc au plus \(k\binom{m+1}{2}\) au total.

Ainsi \(B \leq k\binom{m}{2} + k\binom{m+1}{2}\).

Pour \(k = m\) :

\[C \geq (2m - 1)\binom{2m}{2} = 4m^3 - 4m^2 + m, \qquad B \leq m\binom{m}{2} + m\binom{m+1}{2} = m^3.\]

Donc, pour \(m\) assez grand, \(C \geq 4m^3 - 4m^2 + m > 3.99m^3 \geq 3.99B\), et \(A = B + C > 4.99B\). \(\blacksquare\)