Shortlist 2017, C2¶

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

Concepts : Invariants et monovariants · Double comptage

Solution officielle : Shortlist officielle 2017 (avec solutions), p. 35 (page 37 du PDF)

Pas encore relu

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

Énoncé¶

Let \(n\) be a positive integer. Define a chameleon to be any sequence of \(3n\) letters, with exactly \(n\) occurrences of each of the letters \(a\), \(b\), and \(c\). Define a swap to be the transposition of two adjacent letters in a chameleon. Prove that for any chameleon \(X\), there exists a chameleon \(Y\) such that \(X\) cannot be changed to \(Y\) using fewer than \(3n^2/2\) swaps.

Indices : les idées clés

Distance et inégalité triangulaire : en notant \(d(X, Y)\) le nombre minimal d'échanges, il suffit de trouver deux caméléons \(P, Q\) avec \(d(P, Q) \geq 3n^2\), car alors \(\max\{d(X, P), d(X, Q)\} \geq \frac{3n^2}{2}\) (solution 1).
Monovariant : une quantité qui varie d'exactement \(1\) à chaque échange minore la distance ; ici le nombre \(f\) de paires de positions « dans l'ordre alphabétique » (solution 1), ou des sommes de positions (solution 2).
Compter des paires : \(f(P) = 3n^2\) et \(f(Q) = 0\) pour \(P = a^n b^n c^n\) et \(Q = c^n b^n a^n\).
Construire \(Y\) selon \(X\) (solution 2) : on place les \(c\), puis les \(b\), du côté « opposé » à celui où ils sont dans \(X\).

Solutions

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

Solution 1¶

Remarquons d'abord qu'échanger deux lettres identiques ne change pas le caméléon ; on peut donc supposer qu'il n'y a pas de tels échanges.

Pour deux caméléons \(X\) et \(Y\), définissons leur distance \(d(X, Y)\) comme le nombre minimal d'échanges nécessaires pour transformer \(X\) en \(Y\) (ou inversement). Clairement, \(d(X, Y) + d(Y, Z) \geq d(X, Z)\) pour tous caméléons \(X, Y, Z\).

Lemme. Pour les deux caméléons

\[P = \underbrace{aa\ldots a}_{n}\underbrace{bb\ldots b}_{n}\underbrace{cc\ldots c}_{n} \quad\text{et}\quad Q = \underbrace{cc\ldots c}_{n}\underbrace{bb\ldots b}_{n}\underbrace{aa\ldots a}_{n},\]

on a \(d(P, Q) \geq 3n^2\).

Preuve. Pour un caméléon \(X\) et deux lettres distinctes \(u, v \in \{a, b, c\}\), notons \(f_{u,v}(X)\) le nombre de paires de positions de \(X\) telles que celle de gauche est occupée par \(u\) et celle de droite par \(v\). Posons \(f(X) = f_{a,b}(X) + f_{a,c}(X) + f_{b,c}(X)\). On a \(f_{a,b}(P) = f_{a,c}(P) = f_{b,c}(P) = n^2\) et \(f_{a,b}(Q) = f_{a,c}(Q) = f_{b,c}(Q) = 0\), donc \(f(P) = 3n^2\) et \(f(Q) = 0\).

Considérons un échange qui transforme \(X\) en \(X'\) ; disons que les lettres \(a\) et \(b\) sont échangées. Alors \(f_{a,b}(X)\) et \(f_{a,b}(X')\) diffèrent d'exactement \(1\), tandis que \(f_{a,c}(X) = f_{a,c}(X')\) et \(f_{b,c}(X) = f_{b,c}(X')\). Donc \(|f(X) - f(X')| = 1\) : chaque échange modifie \(f\) d'exactement \(1\) (c'est un monovariant à pas unité). Par conséquent \(d(X, Y) \geq |f(X) - f(Y)|\) pour tous \(X, Y\), et en particulier \(d(P, Q) \geq |f(P) - f(Q)| = 3n^2\). \(\square\)

Revenons au problème. Soit \(X\) un caméléon quelconque. Par le lemme et l'inégalité triangulaire, \(d(X, P) + d(X, Q) \geq d(P, Q) \geq 3n^2\). Donc \(\max\{d(X, P), d(X, Q)\} \geq \frac{3n^2}{2}\) : l'un des deux caméléons \(Y = P\) ou \(Y = Q\) convient. \(\blacksquare\)

Solution 2¶

On reprend la notion de distance de la solution 1, mais avec une autre minoration.

Dans un caméléon \(X\), numérotons les positions de gauche à droite par \(1, 2, \ldots, 3n\). Soit \(s_c(X)\) la somme des positions occupées par des \(c\). La valeur de \(s_c\) change d'au plus \(1\) à chaque échange, mais cela seul ne suffit pas ; il faut une amélioration.

Pour tout caméléon \(X\), notons \(X_c\) la suite obtenue en supprimant les \(n\) lettres \(c\) de \(X\). Numérotons les positions de \(X_c\) par \(1, 2, \ldots, 2n\), et soit \(s_{c,b}(X)\) la somme des positions de \(X_c\) occupées par des \(b\) (on regarde donc la position des \(b\) relativement aux \(a\) seulement). Posons enfin

\[d'(X, Y) := |s_c(X) - s_c(Y)| + |s_{c,b}(X) - s_{c,b}(Y)|.\]

Considérons un échange transformant \(X\) en \(X'\). Si aucune lettre \(c\) n'est concernée, alors \(s_c(X) = s_c(X')\), et exactement une lettre \(b\) change de position dans \(X_c\), donc \(|s_{c,b}(X) - s_{c,b}(X')| = 1\). Si une lettre \(c\) est concernée, alors \(X_c = X'_c\), donc \(s_{c,b}(X) = s_{c,b}(X')\) et \(|s_c(X) - s_c(X')| = 1\). Dans tous les cas \(d'(X, X') = 1\).

Comme dans la solution 1, cela entraîne \(d(X, Y) \geq d'(X, Y)\) pour tous caméléons \(X, Y\). Il suffit donc, pour tout \(X\), d'exhiber \(Y\) avec \(d'(X, Y) \geq \frac{3n^2}{2}\).

La fonction \(s_c\) prend ses valeurs entre \(1 + \cdots + n = \frac{n(n+1)}{2}\) et \((2n+1) + \cdots + 3n = 2n^2 + \frac{n(n+1)}{2}\). Si \(s_c(X) \leq n^2 + \frac{n(n+1)}{2}\), on place les \(c\) de \(Y\) dans les \(n\) dernières positions ; sinon, dans les \(n\) premières. Dans les deux cas, \(|s_c(X) - s_c(Y)| \geq n^2\).

De même, \(s_{c,b}\) prend ses valeurs entre \(\frac{n(n+1)}{2}\) et \(n^2 + \frac{n(n+1)}{2}\). Si \(s_{c,b}(X) \leq \frac{n^2}{2} + \frac{n(n+1)}{2}\), on place les \(b\) de \(Y\) dans les \(n\) dernières positions encore libres ; sinon, dans les \(n\) premières positions libres. Les positions restantes reçoivent les \(a\). Dans tous les cas \(|s_{c,b}(X) - s_{c,b}(Y)| \geq \frac{n^2}{2}\), donc

\[d'(X, Y) \geq n^2 + \frac{n^2}{2} = \frac{3n^2}{2}. \qquad \blacksquare\]

Remarques¶

Remarque 1 (langage des graphes). Soit \(G\) le graphe dont les sommets sont les caméléons, deux sommets étant reliés si les caméléons diffèrent d'un seul échange. Alors \(d(X, Y)\) est la distance usuelle dans ce graphe. Le rayon d'un graphe connexe est \(r(G) = \min_{v} \max_{u} d(u, v)\) ; il s'agit de prouver que \(r(G) \geq \frac{3n^2}{2}\). Il est bien connu que le rayon d'un graphe connexe est au moins la moitié de son diamètre \(\max_{u,v} d(u, v)\) : c'est exactement ce fait qui conclut la solution 1.

Remarque 2 (bornes liées, et une borne plus fine). Les deux minorants \(|f(X) - f(Y)|\) et \(d'(X, Y)\) sont étroitement liés, car

\[f_{a,c}(X) + f_{b,c}(X) = s_c(X) - \frac{n(n+1)}{2} \quad\text{et}\quad f_{a,b}(X) = s_{c,b}(X) - \frac{n(n+1)}{2}.\]

Par exemple, \(d'\) aurait aussi pu servir dans la preuve du lemme de la solution 1. Voici une borne encore plus fine. Dans chaque caméléon, numérotons les occurrences de \(a\) de gauche à droite : \(a_1, \ldots, a_n\) ; comme on n'échange jamais deux lettres identiques, leur ordre relatif ne change pas. Faisons de même pour \(b\) et \(c\), et notons \(\mathcal{A}\) l'ensemble des \(3n\) lettres obtenues. Pour \(s \in \mathcal{A}\), soit \(N_s(X)\) la position de \(s\) dans \(X\). Une paire \((s, t)\) est une \((X, Y)\)-inversion si \(N_s(X) < N_t(X)\) mais \(N_s(Y) > N_t(Y)\) ; soit \(d^*(X, Y)\) le nombre de \((X, Y)\)-inversions. Si \(Y\) et \(Y'\) diffèrent d'un échange, \(|d^*(X, Y) - d^*(X, Y')| = 1\) ; comme \(d^*(X, X) = 0\), on obtient \(d(X, Y) \geq d^*(X, Y)\). Cette borne peut aussi servir dans les deux solutions.

Remarque 3 (optimalité). En fait \(d^* = d\) : si \(X \neq Y\), il existe une \((X, Y)\)-inversion \((s, t)\), que l'on peut choisir en positions consécutives dans \(Y\) ; \(s\) et \(t\) sont alors des lettres différentes de \(\{a, b, c\}\), et les échanger dans \(Y\) donne \(Y'\) avec \(d^*(X, Y') = d^*(X, Y) - 1\). On passe ainsi de \(Y\) à \(X\) en \(d^*(X, Y)\) échanges. On en déduit que l'estimation de l'énoncé est optimale pour \(n \geq 2\) (pour \(n = 1\) elle ne l'est pas : il faut trois échanges pour renverser une permutation de trois lettres). Pour \(k \geq 0\), on pose

\[X_{2k} = \underbrace{abc\,abc\ldots abc}_{3k \text{ lettres}}\,\underbrace{cba\,cba\ldots cba}_{3k \text{ lettres}} \quad\text{et}\quad X_{2k+3} = \underbrace{abc\ldots abc}_{3k \text{ lettres}}\;abc\;bca\;cab\;\underbrace{cba\ldots cba}_{3k \text{ lettres}},\]

et l'on affirme que \(d^*(X_n, Y) \leq \left\lceil \frac{3n^2}{2} \right\rceil\) pour tout \(n \geq 2\) et tout caméléon \(Y\). On note \(d^*_{u,v}(X, Y)\) le nombre d'inversions entre une instance de \(u\) et une instance de \(v\), de sorte que \(d^* = d^*_{a,b} + d^*_{b,c} + d^*_{c,a}\).

Cas \(n = 2k\) pair, \(X = X_{2k}\) : on montre \(d^*_{a,b}(X, Y) \leq 2k^2\) par récurrence sur \(k\) (cas \(k = 0\) trivial). \(d^*_{a,b}(X, Y)\) est le nombre minimal d'échanges pour passer de \(Y_c\) à \(X_c\). Amener \(a_1\) et \(a_{2k}\) en première et dernière positions coûte au plus \(2k\) échanges, puis \(b_1\) et \(b_{2k}\) en deuxième et avant-dernière positions au plus \(2k - 2\) ; on supprime ces lettres et on applique l'hypothèse de récurrence : au total au plus \(2(k-1)^2 + 2k + (2k - 2) = 2k^2\) échanges. Les estimations analogues pour \(d^*_{b,c}\) et \(d^*_{c,a}\) donnent \(d^* \leq 6k^2 = \frac{3n^2}{2}\).
Cas \(n = 2k + 3\) impair (plus technique) : on montre \(d^*_{a,b}(X_{2k+3}, Y) \leq 2k^2 + 6k + 5\), avec égalité seulement si \(Y_c = bb\ldots b\,aa\ldots a\), par une récurrence analogue (en soignant le cas de base et le cas d'égalité). En sommant, \(d^*(X_{2k+3}, Y) \leq 3(2k^2 + 6k + 5) = \left\lceil \frac{3n^2}{2} \right\rceil + 1\), soit \(1\) de trop ; mais l'égalité exigerait simultanément \(Y_c = b\ldots b\,a\ldots a\), \(Y_b = a\ldots a\,c\ldots c\) et \(Y_a = c\ldots c\,b\ldots b\), ce qui est impossible.