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é¶
Soit \(n\) un entier strictement positif, et soit \((a_1, a_2, \ldots, a_n)\) un \(n\)-uplet quelconque d'entiers distincts. Une inversion est un couple \((i, j)\) d'entiers vérifiant \(1 \leq i < j \leq n\) et \(a_i > a_j\). Une inversion \((i, j)\) est dite impaire si \(j - i\) est impair. Soit \(A\) le nombre total d'inversions et \(B\) le nombre d'inversions impaires.
(a) Montrer que \(A \leq 5B\) pour tout \(n\) et tout \(n\)-uplet \((a_1, a_2, \ldots, a_n)\).
(b) Montrer qu'il existe un \(n\) et un \(n\)-uplet \((a_1, a_2, \ldots, a_n)\) pour lesquels \(A > 4.99B\).
Énoncé original (anglais)
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 :
- les inversions impaires ;
- les inversions paires avec \(i \equiv j + 2 \pmod 4\) et \(a_i > a_{(i+j)/2}\) ;
- les inversions paires avec \(i \equiv j + 2 \pmod 4\) et \(a_i < a_{(i+j)/2}\) ;
- les inversions paires avec \(i \equiv j \pmod 4\) et \(a_i > a_{(i+j)/2 - 1}\) ;
- 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\) :
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\)
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2008 C2 ★★☆☆☆ : Combien de permutations vérifient que \(2(a_1 + \cdots + a_k)\) est divisible par \(k\) pour tout \(k\) ?
- 2022 C5 ★★★☆☆ : Au moins \(n^n\) fonctions donnent à une seule des parties \(X_k\) la plus grande somme.
- 2008 C4 ★★★☆☆ · OIM P5 : Allumer les \(n\) premières lampes en \(k\) étapes, avec ou sans toucher aux autres : quel est le rapport des nombres de façons ?
- 2006 C3 ★★★☆☆ : Une somme pondérée par \(x^{a(P)}(1 - x)^{b(P)}\) sur tous les polygones convexes à sommets dans \(S\) vaut toujours \(1\).