Shortlist 2009, C8¶
Domaine : Combinatoire · Difficulté : ★★★★★ · Proposé par : Austria
Concepts : Invariants et monovariants · Récurrence et constructions récursives · Principe extrémal
Solution officielle : Shortlist officielle 2009 (avec solutions), p. 41 (page 43 du PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
For any integer \(n \geq 2\), we compute the integer \(h(n)\) by applying the following procedure to its decimal representation. Let \(r\) be the rightmost digit of \(n\).
(1) If \(r = 0\), then the decimal representation of \(h(n)\) results from the decimal representation of \(n\) by removing this rightmost digit \(0\).
(2) If \(1 \leq r \leq 9\) we split the decimal representation of \(n\) into a maximal right part \(R\) that solely consists of digits not less than \(r\) and into a left part \(L\) that either is empty or ends with a digit strictly smaller than \(r\). Then the decimal representation of \(h(n)\) consists of the decimal representation of \(L\), followed by two copies of the decimal representation of \(R - 1\). For instance, for the number \(n = 17{,}151{,}345{,}543\), we will have \(L = 17{,}151\), \(R = 345{,}543\) and \(h(n) = 17{,}151{,}345{,}542{,}345{,}542\).
Prove that, starting with an arbitrary integer \(n \geq 2\), iterated application of \(h\) produces the integer \(1\) after finitely many steps.
Indices : les idées clés
- Monovariant emboîté : on définit \(f_9(x) = m + 1\) pour une chaîne de \(m\) neufs, puis \(f_k(x) = \sum 4^{f_{k+1}(x_s)}\) en découpant \(x\) selon le chiffre \(k\) ; alors \(f_0(n) > f_0(h(n))\).
- Inégalité clé : \(f_{r-1}(zr) = 4^{f_r(z) + 4^{f_{r+1}(\varepsilon)}} \geq 4 \cdot 4^{f_r(z)}\), qui dépasse la valeur pour \(z(r - 1)z(r - 1)\).
- Solution 2 : par minimalité, on montre qu'une chaîne \(yzr\) termine dès que \(y\) et \(zr\) terminent, grâce aux fonctions \(g_k\) qui commutent avec \(h\) (récurrence sur \(k\)).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2009 (trois solutions).
Solution 1¶
On identifie les entiers \(n \geq 2\) aux chaînes de chiffres (en bref, chaînes) de leur écriture décimale, et l'on étend la définition de \(h\) à toutes les chaînes non vides de chiffres de \(0\) à \(9\). Définissons récursivement dix fonctions \(f_0, \ldots, f_9\) qui envoient certaines chaînes sur des entiers, pour \(k = 9, 8, \ldots, 1, 0\). La fonction \(f_9\) n'est définie que sur les chaînes \(x\) (y compris la chaîne vide \(\varepsilon\)) formées uniquement de neufs. Si \(x\) est formée de \(m\) neufs, alors \(f_9(x) = m + 1\), \(m = 0, 1, \ldots\). Pour \(k \leq 8\), le domaine de \(f_k(x)\) est l'ensemble de toutes les chaînes formées uniquement de chiffres \(\geq k\). On écrit \(x\) sous la forme \(x_0kx_1kx_2k \ldots x_{m-1}kx_m\), où les chaînes \(x_s\) ne sont formées que de chiffres \(\geq k + 1\). Remarquons que certaines de ces chaînes peuvent être la chaîne vide \(\varepsilon\), et que \(m = 0\) est possible, c'est-à-dire que le chiffre \(k\) n'apparaît pas dans \(x\). On définit alors
Nous utiliserons le fait évident suivant.
Fait 1. Si \(x\) ne contient pas de chiffre inférieur à \(k\), alors \(f_i(x) = 4^{f_{i+1}(x)}\) pour tout \(i = 0, \ldots, k - 1\). En particulier, \(f_i(\varepsilon) = 4^{9-i}\) pour tout \(i = 0, 1, \ldots, 9\).
De plus, une récurrence facile sur \(k = 9, 8, \ldots, 0\) donne :
Fait 2. Si la chaîne non vide \(x\) ne contient pas de chiffre inférieur à \(k\), alors \(f_i(x) > f_i(\varepsilon)\) pour tout \(i = 0, \ldots, k\).
Nous allons montrer le fait essentiel suivant.
Fait 3. \(f_0(n) > f_0(h(n))\).
Alors la chaîne vide sera nécessairement atteinte après un nombre fini d'applications de \(h\). Mais, en partant d'une chaîne sans zéro en tête, \(\varepsilon\) ne peut être atteinte que par les chaînes \(1 \to 00 \to 0 \to \varepsilon\). Le nombre \(1\) apparaît donc aussi après un nombre fini d'applications de \(h\).
Preuve du fait 3. Si le dernier chiffre \(r\) de \(n\) est \(0\), on écrit \(n = x_00 \ldots 0x_{m-1}0\varepsilon\), où les \(x_i\) ne contiennent pas le chiffre \(0\). Alors \(h(n) = x_00 \ldots 0x_{m-1}\) et \(f_0(n) - f_0(h(n)) = f_0(\varepsilon) > 0\).
Soit donc le dernier chiffre \(r\) de \(n\) au moins égal à \(1\). Soient \(L = yk\) et \(R = zr\) les parties gauche et droite correspondantes, où \(y\) est une chaîne, \(k \leq r - 1\), et la chaîne \(z\) n'est formée que de chiffres au moins égaux à \(r\). Alors \(n = ykzr\) et \(h(n) = ykz(r - 1)z(r - 1)\). Soit \(d(y)\) le plus petit chiffre de \(y\). On considère deux cas, qui ne s'excluent pas.
Cas 1 : \(d(y) \geq k\). Alors
Vu le fait 1, cette différence est strictement positive si et seulement si
D'après le fait 2, on a
On utilise ici la définition supplémentaire \(f_{10}(\varepsilon) = 0\) si \(r = 9\). Par conséquent, \(f_k(n) - f_k(h(n)) > 0\) et, d'après le fait 1, \(f_0(n) - f_0(h(n)) > 0\).
Cas 2 : \(d(y) \leq k\). Montrons par récurrence sur \(d(y) = k, k - 1, \ldots, 0\) que \(f_i(n) - f_i(h(n)) > 0\) pour tout \(i = 0, \ldots, d(y)\). D'après le fait 1, il suffit de le faire pour \(i = d(y)\). L'initialisation \(d(y) = k\) a déjà été traitée dans le cas 1. Soit \(t = d(y) < k\). Écrivons \(y\) sous la forme \(utv\), où \(v\) ne contient pas de chiffre \(\leq t\). Alors, vu l'hypothèse de récurrence,
L'inégalité \(f_{d(y)}(n) - f_{d(y)}(h(n)) > 0\) est ainsi établie et, d'après le fait 1, il s'ensuit que \(f_0(n) - f_0(h(n)) > 0\). \(\blacksquare\)
Solution 2¶
On identifie les entiers \(n \geq 2\) aux chaînes de leur écriture décimale et l'on étend la définition de \(h\) à toutes les chaînes non vides de chiffres de \(0\) à \(9\). On décide de plus que la chaîne vide \(\varepsilon\) est envoyée sur la chaîne vide. Dans la suite, toutes les fonctions envoient l'ensemble des chaînes dans lui-même. Pour deux fonctions \(f\) et \(g\), soit \(g \circ f\) définie par \((g \circ f)(x) = g(f(x))\) pour toute chaîne \(x\), et, pour tout entier \(n \geq 0\), notons \(f^n\) la \(n\)-ième itérée de \(f\). Pour toute chaîne \(x\), soit \(s(x)\) le plus petit chiffre de \(x\), et pour la chaîne vide, posons \(s(\varepsilon) = \infty\). On définit neuf fonctions \(g_1, \ldots, g_9\) ainsi : soit \(k \in \{1, \ldots, 9\}\) et \(x\) une chaîne. Si \(x = \varepsilon\), alors \(g_k(x) = \varepsilon\). Sinon, on écrit \(x\) sous la forme \(x = yzr\), où \(y\) est la chaîne vide ou se termine par un chiffre inférieur à \(k\), \(s(z) \geq k\), et \(r\) est le chiffre le plus à droite de \(x\). Alors \(g_k(x) = zr\).
Lemme 1. On a \(g_k \circ h = g_k \circ h \circ g_k\) pour tout \(k = 1, \ldots, 9\).
Preuve. Soit \(x = yzr\) comme dans la définition de \(g_k\). Si \(y = \varepsilon\), alors \(g_k(x) = x\), d'où
Soit donc \(y \neq \varepsilon\).
Cas 1 : \(z\) contient un chiffre inférieur à \(r\). Soit \(z = uav\) avec \(a < r\) et \(s(v) \geq r\). Alors
Comme \(y\) se termine par un chiffre inférieur à \(k\), (1) est évidemment vraie.
Cas 2 : \(z\) ne contient pas de chiffre inférieur à \(r\). Soit \(y = uv\), où \(u\) est la chaîne vide ou se termine par un chiffre inférieur à \(r\), et \(s(v) \geq r\). On a
Rappelons que \(y\), et donc \(v\), se termine par un chiffre inférieur à \(k\), mais que tous les chiffres de \(v\) sont au moins égaux à \(r\). Si \(r > k\), alors \(v = \varepsilon\), et le dernier chiffre de \(u\) est inférieur à \(k\), ce qui entraîne
Si \(r \leq k\), alors
de sorte que (1) est vraie dans les deux cas. Le lemme 1 est prouvé. \(\square\)
Lemme 2. Soient \(k \in \{1, \ldots, 9\}\), \(x\) une chaîne non vide et \(n\) un entier strictement positif. Si \(h^n(x) = \varepsilon\), alors \((g_k \circ h)^n(x) = \varepsilon\).
Preuve. Récurrence sur \(n\). Si \(n = 1\), on a
Passons de \(n - 1\) à \(n\), avec \(n \geq 2\). Soit \(h^n(x) = \varepsilon\) et posons \(y = h(x)\). Alors \(h^{n-1}(y) = \varepsilon\) et, par hypothèse de récurrence, \((g_k \circ h)^{n-1}(y) = \varepsilon\). Vu le lemme 1,
L'hérédité est donc établie, et le lemme 2 est prouvé. \(\square\)
On dit que la chaîne non vide \(x\) termine si \(h^n(x) = \varepsilon\) pour un entier \(n \geq 0\).
Lemme 3. Soit \(x = yzr\) avec \(s(y) \geq k\), \(s(z) \geq k\), où \(y\) se termine par le chiffre \(k\) et \(z\) est éventuellement vide. Si \(y\) et \(zr\) terminent, alors \(x\) termine aussi.
Preuve. Supposons que \(y\) et \(zr\) terminent. On procède par récurrence sur \(k\). Soit \(k = 0\). Évidemment, \(h(yw) = yh(w)\) pour toute chaîne non vide \(w\). Soit \(h^n(zr) = \varepsilon\). Une récurrence facile sur \(m\) donne \(h^m(yzr) = yh^m(zr)\) pour \(m = 1, \ldots, n\). Par conséquent, \(h^n(yzr) = y\). Comme \(y\) termine, \(x = yzr\) termine aussi.
Supposons maintenant l'affirmation vraie pour tous les entiers positifs ou nuls inférieurs à \(k\), et prouvons-la pour \(k \geq 1\). Il suffit de prouver que \(yg_k(h(zr))\) termine. En effet :
Cas 1 : \(r = 0\). Alors \(h(yzr) = yz = yg_k(h(zr))\).
Cas 2 : \(0 < r \leq k\). On a \(h(zr) = z(r - 1)z(r - 1)\) et \(g_k(h(zr)) = z(r - 1)\). Alors \(h(yzr) = yz(r - 1)yz(r - 1) = yg_k(h(zr))yg_k(h(zr))\), et l'on peut appliquer l'hypothèse de récurrence pour voir que si \(yg_k(h(zr))\) termine, alors \(h(yzr)\) termine.
Cas 3 : \(r > k\). Alors \(h(yzr) = yh(zr) = yg_k(h(zr))\).
Remarquons que \(yg_k(h(zr))\) est de la forme \(yz'r'\) avec \(s(z') \geq k\). Par les mêmes arguments, il suffit de prouver que \(yg_k(h(z'r')) = y(g_k \circ h)^2(zr)\) termine et, par récurrence, que \(y(g_k \circ h)^m(zr)\) termine pour un certain entier \(m > 0\). Vu le lemme 2, il existe un \(m\) tel que \((g_k \circ h)^m(zr) = \varepsilon\), donc \(x = yzr\) termine si \(y\) termine. Le lemme 3 est prouvé. \(\square\)
Supposons maintenant qu'une chaîne \(x\) ne termine pas. Choisissons \(x\) minimal. Si \(x \geq 10\), on peut écrire \(x\) sous la forme \(x = yzr\) du lemme 3, et d'après ce lemme \(x\) termine, puisque \(y\) et \(zr\) sont plus petits que \(x\). Si \(x \leq 9\), alors \(h(x) = (x - 1)(x - 1)\), et \(h(x)\) termine de nouveau d'après le lemme 3 et le choix minimal de \(x\). \(\blacksquare\)
Solution 3¶
Commençons par introduire un peu de terminologie. Au lieu d'entiers, on considère l'ensemble \(S\) de toutes les chaînes formées des chiffres \(0, 1, \ldots, 9\), y compris la chaîne vide \(\epsilon\). Si \((a_1, a_2, \ldots, a_n)\) est une chaîne non vide, on note \(\rho(a) = a_n\) le chiffre terminal de \(a\), et \(\lambda(a)\) la chaîne privée de son dernier chiffre. On pose aussi \(\lambda(\epsilon) = \epsilon\), et l'on note \(\mathbb{N}_0\) l'ensemble des entiers positifs ou nuls.
Soit maintenant \(k \in \{0, 1, 2, \ldots, 9\}\) un chiffre quelconque. On définit une fonction \(f_k : S \to S\) sur l'ensemble des chaînes : d'abord, si le chiffre terminal de \(n\) appartient à \(\{0, 1, \ldots, k\}\), alors \(f_k(n)\) s'obtient à partir de \(n\) en supprimant ce chiffre terminal, c'est-à-dire \(f_k(n) = \lambda(n)\). Ensuite, si le chiffre terminal de \(n\) appartient à \(\{k + 1, \ldots, 9\}\), alors \(f_k(n)\) s'obtient à partir de \(n\) par le procédé décrit dans l'énoncé. On pose aussi \(f_k(\epsilon) = \epsilon\). Remarquons qu'à la définition près pour les entiers \(n \leq 1\), la fonction \(f_0\) coïncide avec la fonction \(h\) du problème, en interprétant les entiers comme des chaînes de chiffres. L'argument sera grosso modo le suivant. On introduit d'abord une généralisation immédiate de notre affirmation sur \(f_0\). On verra facilement que \(f_9\) a toutes ces propriétés plus fortes, et il suffira donc de montrer, pour \(k \in \{0, 1, \ldots, 8\}\), que \(f_k\) possède ces propriétés dès que \(f_{k+1}\) les possède.
On continue à noter \(k\) un chiffre quelconque. L'opération \(f_k\) est dite séparante si la propriété suivante est vraie : dès que \(a\) est un segment initial de \(b\), il existe un \(N \in \mathbb{N}_0\) tel que \(f_k^N(b) = a\). Les deux notions suivantes ne s'appliquent qu'au cas où \(f_k\) est séparante ; sinon, elles restent indéfinies. Pour tout \(a \in S\), on note \(g_k(a)\) le plus petit \(N \in \mathbb{N}_0\) tel que \(f_k^N(a) = \epsilon\) (comme \(\epsilon\) est un segment initial de \(a\), un tel \(N\) existe si \(f_k\) est séparante). Si, pour toutes chaînes \(a\) et \(b\) telles que \(a\) soit un segment terminal de \(b\), on a \(g_k(a) \leq g_k(b)\), on dit que \(f_k\) est cohérente. Si \(f_k\) est séparante et cohérente, on dit que le chiffre \(k\) est séduisant.
Comme \(f_9(a) = \lambda(a)\) pour tout \(a\), il est évident que \(9\) est séduisant. Donc, pour montrer que \(0\) est séduisant, ce qui implique clairement l'énoncé du problème, il suffit de prendre un \(k \in \{0, 1, \ldots, 8\}\) tel que \(k + 1\) soit séduisant et de prouver que \(k\) l'est aussi. Ce faisant, on dispose de la fonction \(g_{k+1}\). Il faut établir deux choses, et l'on commence par :
Étape 1. \(f_k\) est séparante.
Avant de prouver cela, notons une observation utile, qui se prouve facilement par récurrence sur \(M\).
Affirmation 1. Pour toutes chaînes \(A\), \(B\) et tout entier \(M > 0\) tel que \(f_k^{M-1}(B) \neq \epsilon\), on a
On appelle maintenant méchante une paire \((a, b)\) de chaînes telle que \(a\) soit un segment initial de \(b\), mais qu'il n'existe aucun \(N \in \mathbb{N}_0\) tel que \(f_k^N(b) = a\). Il faut montrer qu'il n'y en a pas ; supposons donc qu'il en existe. Choisissons une paire méchante \((a, b)\) pour laquelle \(g_{k+1}(b)\) atteint la plus petite valeur possible. Évidemment, \(b \neq \epsilon\) pour toute paire méchante \((a, b)\). Soit \(z\) le chiffre terminal de \(b\). Remarquons que \(a \neq b\), ce qui signifie que \(a\) est aussi un segment initial de \(\lambda(b)\). Pour faciliter la construction de la contradiction finale, prouvons :
Affirmation 2. Il ne peut pas exister de \(N \in \mathbb{N}_0\) tel que
Preuve. Supposons qu'un tel \(N\) existe. Comme \(g_{k+1}(\lambda(b)) < g_{k+1}(b)\) par cohérence de \(f_{k+1}\), la paire \((a, \lambda(b))\) n'est pas méchante. Mais alors il existe un \(N'\) tel que \(f_k^{N'}(\lambda(b)) = a\), ce qui entraîne \(f_k^{N+N'}(b) = a\) : contradiction. L'affirmation 2 est donc prouvée. \(\square\)
Il s'ensuit que \(z \leq k\) est impossible, sinon \(N = 1\) contredirait l'affirmation 2.
De plus, \(z > k + 1\) est impossible. Posons \(B = f_k(b)\). On a alors aussi \(f_{k+1}(b) = B\), mais \(g_{k+1}(B) < g_{k+1}(b)\), et \(a\) est un segment initial de \(B\). La paire \((a, B)\) n'est donc pas méchante. Il existe donc un \(N \in \mathbb{N}_0\) tel que \(a = f_k^N(B)\), ce qui entraîne cependant \(a = f_k^{N+1}(b)\).
Il reste le cas \(z = k + 1\). Soient \(L\) la partie gauche et \(R = R^*(k + 1)\) la partie droite de \(b\). On a alors, symboliquement,
En utilisant que \(R^*\) est un segment terminal de \(LR^*\) et la cohérence de \(f_{k+1}\), on en déduit
La paire \((\epsilon, R^*)\) n'est donc pas méchante, de sorte qu'il existe un \(M \in \mathbb{N}_0\) minimal tel que \(f_k^M(R^*) = \epsilon\), et d'après l'affirmation 1, il s'ensuit que \(f_k^{2+M}(b) = LR^*k\). Finalement, on en déduit que \(\lambda(b) = LR^* = f_k(LR^*k) = f_k^{3+M}(b)\), ce qui contredit l'affirmation 2.
Cette contradiction finale établit que \(f_k\) est bien séparante.
Étape 2. \(f_k\) est cohérente.
Pour préparer cette preuve, introduisons encore un peu de terminologie. Une chaîne non vide \((a_1, a_2, \ldots, a_n)\) est appelée hypostase si \(a_n < a_i\) pour tout \(i = 1, \ldots, n - 1\). En lisant une chaîne quelconque \(a\) à l'envers, on trouve facilement une suite (éventuellement vide) \((A_1, A_2, \ldots, A_m)\) d'hypostases telle que \(\rho(A_1) \leq \rho(A_2) \leq \cdots \leq \rho(A_m)\) et, symboliquement, \(a = A_1A_2 \ldots A_m\). Cette suite est appelée la décomposition de \(a\). Par exemple, \((20, 0, 9)\) est la décomposition de \(2009\), et la chaîne \(50\) est une hypostase. On explique ensuite ce que signifie, pour deux chaînes \(a\) et \(b\), que \(a\) est injectable dans \(b\). La définition se fait par récurrence sur la longueur de \(b\). Soit \((B_1, B_2, \ldots, B_n)\) la décomposition de \(b\) en hypostases. Alors \(a\) est injectable dans \(b\) si, pour la décomposition \((A_1, A_2, \ldots, A_m)\) de \(a\), il existe une fonction strictement croissante \(H : \{1, 2, \ldots, m\} \to \{1, 2, \ldots, n\}\) telle que
- \(\rho(A_i) = \rho(B_{H(i)})\) pour tout \(i = 1, \ldots, m\) ;
- \(\lambda(A_i)\) est injectable dans \(\lambda(B_{H(i)})\) pour tout \(i = 1, \ldots, m\).
Si l'on peut choisir \(H\) avec \(H(m) = n\), on dit que \(a\) est fortement injectable dans \(b\). Évidemment, si \(a\) est un segment terminal de \(b\), alors \(a\) est fortement injectable dans \(b\).
Affirmation 3. Si \(a\) et \(b\) sont deux chaînes non vides telles que \(a\) soit fortement injectable dans \(b\), alors \(\lambda(a)\) est injectable dans \(\lambda(b)\).
Preuve. Soient \((B_1, B_2, \ldots, B_n)\) la décomposition de \(b\) et \((A_1, A_2, \ldots, A_m)\) celle de \(a\). Prenons une fonction \(H\) qui montre que \(a\) est fortement injectable dans \(b\). Soient \((C_1, C_2, \ldots, C_r)\) la décomposition de \(\lambda(A_m)\) et \((D_1, D_2, \ldots, D_s)\) celle de \(\lambda(B_n)\). Choisissons une fonction strictement croissante \(H' : \{1, 2, \ldots, r\} \to \{1, 2, \ldots, s\}\) montrant que \(\lambda(A_m)\) est injectable dans \(\lambda(B_n)\). Clairement, \((A_1, A_2, \ldots, A_{m-1}, C_1, C_2, \ldots, C_r)\) est la décomposition de \(\lambda(a)\), et \((B_1, B_2, \ldots, B_{n-1}, D_1, D_2, \ldots, D_s)\) celle de \(\lambda(b)\). Alors la fonction \(H'' : \{1, 2, \ldots, m + r - 1\} \to \{1, 2, \ldots, n + s - 1\}\) donnée par \(H''(i) = H(i)\) pour \(i = 1, 2, \ldots, m - 1\) et \(H''(m - 1 + i) = n - 1 + H'(i)\) pour \(i = 1, 2, \ldots, r\) montre que \(\lambda(a)\) est injectable dans \(\lambda(b)\), ce qui termine la preuve de l'affirmation. \(\square\)
Une paire \((a, b)\) de chaînes est dite agressive si \(a\) est injectable dans \(b\) et que pourtant \(g_k(a) > g_k(b)\). Remarquons que si \(f_k\) n'était pas cohérente, ce que nous supposons désormais, de telles paires existeraient. Parmi toutes les paires agressives, choisissons-en une, disons \((a, b)\), pour laquelle \(g_k(b)\) atteint la plus petite valeur possible. Évidemment, \(f_k(a)\) ne peut pas être injectable dans \(f_k(b)\), sinon la paire \((f_k(a), f_k(b))\) serait agressive et contredirait notre choix de \((a, b)\). Soient \((A_1, A_2, \ldots, A_m)\) et \((B_1, B_2, \ldots, B_n)\) les décompositions de \(a\) et de \(b\), et prenons une fonction \(H : \{1, 2, \ldots, m\} \to \{1, 2, \ldots, n\}\) montrant que \(a\) est bien injectable dans \(b\). Si l'on avait \(H(m) < n\), alors \(a\) serait aussi injectable dans le nombre \(b'\) de décomposition \((B_1, B_2, \ldots, B_{n-1})\), et, par la propriété séparante de \(f_k\), on obtiendrait \(g_k(b') < g_k(b)\), de sorte que la paire \((a, b')\) serait aussi agressive, contrairement à la condition de minimalité imposée à \(b\). Donc \(a\) est fortement injectable dans \(b\). En particulier, \(a\) et \(b\) ont un chiffre terminal commun, disons \(z\). Si l'on avait \(z \leq k\), alors \(f_k(a) = \lambda(a)\) et \(f_k(b) = \lambda(b)\), de sorte que, d'après l'affirmation 3, \(f_k(a)\) serait injectable dans \(f_k(b)\), ce qui est une contradiction. Donc \(z \geq k + 1\).
Soit maintenant \(r\) le plus petit élément de \(\{1, 2, \ldots, m\}\) tel que \(\rho(A_r) = z\). Alors la partie droite maximale de \(a\) formée de chiffres \(\geq z\) est égale à \(R_a\), la chaîne de décomposition \((A_r, A_{r+1}, \ldots, A_m)\). Alors \(R_a - 1\) est une hypostase, et \((A_1, \ldots, A_{r-1}, R_a - 1, R_a - 1)\) est la décomposition de \(f_k(a)\). En définissant \(s\) et \(R_b\) de la même façon pour \(b\), on voit que \((B_1, \ldots, B_{s-1}, R_b - 1, R_b - 1)\) est la décomposition de \(f_k(b)\). La définition de l'injectabilité entraîne alors facilement que \(R_a\) est fortement injectable dans \(R_b\). D'après l'affirmation 3, \(\lambda(R_a) = \lambda(R_a - 1)\) est injectable dans \(\lambda(R_b) = \lambda(R_b - 1)\), d'où la fonction \(H' : \{1, 2, \ldots, r + 1\} \to \{1, 2, \ldots, s + 1\}\), donnée par \(H'(i) = H(i)\) pour \(i = 1, 2, \ldots, r - 1\), \(H'(r) = s\) et \(H'(r + 1) = s + 1\), montre que \(f_k(a)\) est injectable dans \(f_k(b)\), ce qui donne une contradiction comme précédemment.
Cela montre que les paires agressives ne peuvent pas exister ; \(f_k\) est donc bien cohérente, ce qui termine la preuve du caractère séduisant de \(k\), et le problème est enfin résolu. \(\blacksquare\)