Shortlist 2018, C6¶

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

Concepts : Divisibilité, PGCD et algorithme d'Euclide · Invariants et monovariants

Solution officielle : Shortlist officielle 2018 (avec solutions), p. 32 (page 34 du PDF)

Pas encore relu

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

Énoncé¶

Let \(a\) and \(b\) be distinct positive integers. The following infinite process takes place on an initially empty board.

(i) If there is at least a pair of equal numbers on the board, we choose such a pair and increase one of its components by \(a\) and the other by \(b\).

(ii) If no such pair exists, we write down two times the number \(0\).

Prove that, no matter how we make the choices in (i), operation (ii) will be performed only finitely many times.

Indices : les idées clés

Compter les apparitions (solution 1) : si \(f(k)\) est le nombre de fois où \(k\) est apparu, alors \(f(k) = \lfloor f(k-a)/2 \rfloor + \lfloor f(k-b)/2 \rfloor\) au moment où il faut rajouter des zéros.
Divisibilité et PGCD : réduction à \(\gcd(a,b) = 1\), puis tout entier \(> ab - a - b\) s'écrit \(sa + tb\) avec \(s, t \geq 0\) ; cela fournit \(b\) entiers consécutifs souvent atteints.
Invariants (solution 2) : le résultat final ne dépend pas de l'ordre des coups ; on peut donc mettre tous les zéros au début et choisir les coups à sa guise.
Une configuration qui se reproduit (solution 2) : avec \(n+1, \ldots, n+a\) et \(n+1, \ldots, n+b\) au tableau, un coup redonne la même configuration décalée de \(1\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2018 (deux solutions et une remarque).

Solution 1¶

On peut supposer \(\gcd(a, b) = 1\) ; sinon, on raisonne de la même façon avec les multiples de \(d = \gcd(a, b)\).

Supposons qu'après \(N\) opérations de type (ii) et un certain nombre d'opérations de type (i), on doive ajouter deux nouveaux zéros (donc tous les nombres au tableau sont distincts). Pour tout entier \(k\), notons \(f(k)\) le nombre de fois où le nombre \(k\) est apparu au tableau jusqu'à ce moment. Alors \(f(0) = 2N\) et \(f(k) = 0\) pour \(k < 0\). Comme le tableau contient à ce moment au plus un exemplaire de \(k - a\), les apparitions de \(k - a\) ont été « consommées » par paires, et chaque paire a produit une apparition de \(k\) ; de même pour \(k - b\). Par conséquent, pour \(k > 0\),

\[f(k) = \left\lfloor \frac{f(k-a)}{2} \right\rfloor + \left\lfloor \frac{f(k-b)}{2} \right\rfloor, \tag{1}\]

d'où

\[f(k) \geq \frac{f(k-a) + f(k-b)}{2} - 1. \tag{2}\]

Comme \(\gcd(a, b) = 1\), tout entier \(x > ab - a - b\) s'écrit \(x = sa + tb\) avec des entiers \(s, t \geq 0\).

Montrons par récurrence sur \(s + t\) que si \(x = sa + tb\) avec \(s, t\) entiers positifs ou nuls, alors

\[f(x) > \frac{f(0)}{2^{s+t}} - 2. \tag{3}\]

Le cas \(s + t = 0\) est évident. Supposons (3) vraie pour \(s + t = v\). Si \(s + t = v + 1\) et \(x = sa + tb\), l'un des deux nombres \(s, t\), disons \(s\), est strictement positif ; d'après (2) (et \(f(x - b) \geq 0\)),

\[f(x) = f(sa + tb) \geq \frac{f\left((s-1)a + tb\right)}{2} - 1 > \frac{1}{2}\left(\frac{f(0)}{2^{s+t-1}} - 2\right) - 1 = \frac{f(0)}{2^{s+t}} - 2.\]

Supposons maintenant que l'on doive effectuer des opérations de type (ii) indéfiniment. Posons \(n = ab - a - b\) et supposons \(b > a\). Chacun des nombres \(n+1, n+2, \ldots, n+b\) s'écrit \(sa + tb\) avec \(0 \leq s \leq b\) et \(0 \leq t \leq a\). Au moment où l'opération (ii) a été effectuée \(2^{a+b+1}\) fois et où il faut rajouter une nouvelle paire de zéros, on a \(f(0) = 2^{a+b+2}\) et \(s + t \leq a + b\), donc d'après (3) chaque \(f(n+k)\), \(k = 1, 2, \ldots, b\), vaut au moins \(2\). La relation (1) donne alors, par récurrence, \(f(n+k) \geq 2\) pour tout \(k \geq 1\) (pour \(m > n + b\), les nombres \(m - a\) et \(m - b\) sont tous deux \(> n\) et \(< m\)). C'est absurde : après un nombre fini d'opérations, \(f\) ne peut être non nulle qu'en un nombre fini de points. \(\blacksquare\)

Solution 2¶

Montrons d'abord que le résultat du processus ne dépend pas de la façon dont on effectue les opérations. Pour cela, il est commode de modifier un peu le processus.

Affirmation 1. Supposons que le tableau contienne initialement un nombre fini d'entiers positifs ou nuls, et qu'on n'effectue que des opérations de type (i). Supposons qu'une suite de \(k\) opérations conduise à une configuration finale, où plus aucune opération de type (i) n'est possible. Alors, en partant de la même configuration initiale et en effectuant des opérations de type (i) de façon arbitraire, le processus s'arrête nécessairement sur la même configuration finale.

Preuve. Dans cette preuve, toutes les opérations sont de type (i). Récurrence sur \(k\) ; le cas \(k = 0\) est évident, car aucune opération n'est possible. Supposons \(k \geq 1\). Fixons un processus canonique formé de \(k\) opérations \(M_1, M_2, \ldots, M_k\) et aboutissant à la configuration finale \(A\). Considérons un processus quelconque \(m_1, m_2, \ldots\) partant de la même configuration et poursuivi aussi longtemps que possible ; il contient évidemment au moins une opération. Il faut montrer qu'il s'arrête en \(A\).

Supposons que \(m_1\) remplace deux exemplaires de \(x\) par \(x + a\) et \(x + b\). Si \(M_1\) fait de même, on applique l'hypothèse de récurrence à la configuration obtenue après \(m_1\). Sinon, le processus canonique doit tout de même contenir au moins une opération \((x, x) \mapsto (x + a, x + b)\), car la configuration initiale contient au moins deux exemplaires de \(x\), alors que la configuration finale en contient au plus un.

Soit \(M_i\) la première telle opération. Comme les exemplaires de \(x\) sont indiscernables et qu'aucun autre exemplaire de \(x\) n'a disparu avant \(M_i\) dans le processus canonique, on peut réordonner ce processus en \(M_i, M_1, \ldots, M_{i-1}, M_{i+1}, \ldots, M_k\) sans changer la configuration finale. Il suffit alors d'effectuer l'opération \(m_1 = M_i\) et d'appliquer l'hypothèse de récurrence comme ci-dessus. \(\square\)

Affirmation 2. Considérons un processus partant du tableau vide, comportant exactement \(n\) opérations de type (ii) et aboutissant à une configuration finale où tous les nombres sont distincts. Si l'on part d'un tableau contenant \(2n\) zéros (comme si les \(n\) opérations de type (ii) avaient été faites au début) et qu'on applique des opérations de type (i) de façon arbitraire, on aboutit à la même configuration finale.

Preuve. En partant du tableau avec \(2n\) zéros, on peut reproduire le premier processus en omettant les opérations de type (ii) ; on obtient ainsi la même configuration finale. L'affirmation 1 montre alors que cette configuration finale est obtenue quelle que soit la façon d'appliquer les opérations de type (i). \(\square\)

L'affirmation 2 permet de reformuler l'énoncé ainsi : il existe un entier \(n\) tel que, en partant de \(2n\) zéros, on puisse appliquer des opérations de type (i) indéfiniment. Précision ajoutée : en effet, si l'opération (ii) était effectuée une \((n+1)\)-ième fois, la configuration juste avant serait finale (tous les nombres distincts) après exactement \(n\) opérations (ii) ; d'après les affirmations 1 et 2, tout processus de type (i) partant de \(2n\) zéros s'arrêterait alors, ce qui contredit le choix de \(n\). Ainsi l'opération (ii) est effectuée au plus \(n\) fois.

Montrons-le. D'abord, par une récurrence immédiate sur \(s + t = k \geq 1\) : en partant de \(2^{s+t}\) zéros, on peut obtenir simultanément au tableau, à un certain moment, chacun des nombres \(sa + tb\) avec \(s + t = k\).

Supposons \(a < b\). En utilisant des groupes de zéros séparés, on peut obtenir deux exemplaires de chacun des nombres \(sa + tb\) avec \(0 \leq s, t \leq b\), \((s,t) \neq (0,0)\). Le livret écrit \(1 \leq s, t \leq b\) ; il faut autoriser \(s = 0\) ou \(t = 0\), sans quoi certains \(N + k\) ne sont pas représentables (par exemple \(a = 2\), \(b = 3\), \(N + 1 = 2\)).

Posons \(N = ab - a - b\) (précision ajoutée : on suppose ici \(\gcd(a,b) = 1\), la réduction étant la même que dans la solution 1). En écrivant chacun des nombres \(N + k\), \(1 \leq k \leq b\), sous la forme \(sa + tb\) avec \(0 \leq s, t \leq b\), on obtient, avec suffisamment de zéros, les nombres \(N+1, N+2, \ldots, N+a\) et les nombres \(N+1, N+2, \ldots, N+b\).

À partir de là, on peut effectuer indéfiniment des opérations de type (i). En effet, si \(n \geq N\), la présence des nombres \(n+1, n+2, \ldots, n+a\) et \(n+1, n+2, \ldots, n+b\), et le remplacement \((n+1, n+1) \mapsto (n+b+1, n+a+1)\), conduisent à la présence des nombres \(n+2, n+3, \ldots, n+a+1\) et \(n+2, n+3, \ldots, n+b+1\) : c'est la même situation avec \(n\) remplacé par \(n + 1\). \(\blacksquare\)

Remarques¶

Remarque 1. Les preuves des affirmations 1 et 2 peuvent être prolongées pour montrer qu'en fait le nombre d'opérations du processus canonique est le même que dans un processus quelconque.