Shortlist 2012, C1¶
Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : non indiqué
Concepts : Invariants et monovariants
Solution officielle : Shortlist officielle 2012 (avec solutions), p. 19 (page 19 du PDF)
Énoncé¶
Several positive integers are written in a row. Iteratively, Alice chooses two adjacent numbers \(x\) and \(y\) such that \(x > y\) and \(x\) is to the left of \(y\), and replaces the pair \((x, y)\) by either \((y + 1, x)\) or \((x - 1, x)\). Prove that she can perform only finitely many such iterations.
Indices : les idées clés
- Invariant : l'opération ne change pas le maximum \(M\) de la suite, donc tous les termes restent entre \(1\) et \(M\).
- Monovariant (solution 1) : la somme pondérée \(S = a_1 + 2a_2 + \cdots + na_n\) augmente d'au moins \(1\) à chaque étape et reste au plus \((1 + 2 + \cdots + n)M\).
- Ordre lexicographique (solutions 2 et 3) : la suite (ou la suite des « scores ») progresse strictement pour un ordre total sur un ensemble fini.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2012 (trois solutions et deux remarques).
Solution 1¶
Remarquons d'abord que l'opération ne change pas le maximum \(M\) de la suite initiale. Soient \(a_1, a_2, \ldots, a_n\) les nombres obtenus à un moment du processus, et considérons la somme
Montrons que \(S\) augmente d'un entier strictement positif à chaque opération. Supposons que l'opération remplace le couple \((a_i, a_{i+1})\) par \((c, a_i)\), avec \(a_i > a_{i+1}\) et \(c = a_{i+1} + 1\) ou \(c = a_i - 1\). La nouvelle et l'ancienne valeur de \(S\) diffèrent de
L'entier \(d\) est strictement positif, car \(a_i - a_{i+1} \geq 1\) et \(c - a_{i+1} \geq 0\).
D'autre part, \(S \leq (1 + 2 + \cdots + n)M\) puisque \(a_i \leq M\) pour tout \(i\). Comme \(S\) augmente d'au moins \(1\) à chaque étape sans jamais dépasser une constante, le processus s'arrête après un nombre fini d'étapes. \(\blacksquare\)
Solution 2¶
Comme dans la première solution, les opérations ne changent pas le maximum \(M\) de la suite initiale. Considérons l'ordre lexicographique « inversé » sur les \(n\)-uplets d'entiers : \((x_1, \ldots, x_n) < (y_1, \ldots, y_n)\) si \(x_n < y_n\), ou si \(x_n = y_n\) et \(x_{n-1} < y_{n-1}\), ou si \(x_n = y_n\), \(x_{n-1} = y_{n-1}\) et \(x_{n-2} < y_{n-2}\), etc. Chaque opération crée une suite plus grande que la précédente pour cet ordre, et aucune suite n'apparaît deux fois. Or il n'y a qu'un nombre fini de suites possibles, puisque leurs termes sont des entiers strictement positifs au plus égaux à \(M\). Le processus ne peut donc pas continuer indéfiniment. \(\blacksquare\)
Solution 3¶
Soient \(a_1, a_2, \ldots, a_n\) les nombres actuels. Définissons le score \(s_i\) de \(a_i\) comme le nombre de \(a_j\) strictement inférieurs à \(a_i\), et appelons \(s_1, s_2, \ldots, s_n\) la suite des scores de \(a_1, a_2, \ldots, a_n\).
Disons qu'une suite \(x_1, \ldots, x_n\) domine une suite \(y_1, \ldots, y_n\) si le premier indice \(i\) tel que \(x_i \neq y_i\) vérifie \(x_i < y_i\). Montrons qu'après chaque opération, la nouvelle suite des scores domine l'ancienne. Les suites de scores ne se répètent donc pas, et il y en a un nombre fini (au plus \((n - 1)^n\)) ; le processus s'arrête donc.
Considérons une opération qui remplace \((x, y)\) par \((a, x)\), avec \(a = y + 1\) ou \(a = x - 1\). Supposons que \(x\) était à la position \(i\). Pour tout \(j < i\), le score \(s_j\) n'augmente pas, puisque \(y \leq a\) et \(x \leq x\). Si \(s_j\) diminue pour un \(j < i\), la nouvelle suite domine l'ancienne. Supposons donc que \(s_j\) reste le même pour tout \(j < i\), et considérons \(s_i\). Comme \(x > y\) et \(y \leq a \leq x\), le score \(s_i\) diminue d'au moins \(1\). Cela conclut la preuve. \(\blacksquare\)
Remarques¶
Remarque 1. Les trois preuves fonctionnent si \(x\) et \(y\) ne sont pas forcément adjacents, et si le couple \((x, y)\) est remplacé par n'importe quel couple \((a, x)\), où \(a\) est un entier tel que \(y \leq a \leq x\). Les « poids » \(1, 2, \ldots, n\) dans la définition de \(S = \sum_{i=1}^{n} ia_i\) n'ont rien de particulier : pour toute suite \(w_1 < w_2 < \cdots < w_n\) d'entiers strictement positifs, la somme \(\sum_{i=1}^{n} w_i a_i\) augmente d'au moins \(1\) à chaque opération.
Considérons le même problème, mais en laissant Alice remplacer le couple \((x, y)\) par \((a, x)\), où \(a\) est un entier strictement positif quelconque inférieur à \(x\). La conclusion reste vraie : le processus finit par s'arrêter. La solution avec l'ordre lexicographique inversé fonctionne sans changement. La première solution demanderait des poids particuliers, comme \(w_i = M^i\) pour \(i = 1, \ldots, n\).
Remarque 2. Les deux premières solutions donnent des majorations du nombre d'opérations possibles, respectivement de l'ordre de \(Mn^2\) et de \(M^n\), où \(M\) est le maximum de la suite initiale. La majoration \((n - 1)^n\) de la troisième solution ne dépend pas de \(M\).