Shortlist 2025, A6¶
Domaine : Algèbre · Difficulté : ★★★★☆ · Proposé par : Singapore
Concepts : Principe des tiroirs · Divisibilité, PGCD et algorithme d'Euclide · Suites et récurrences
Solution officielle : Shortlist officielle 2025 (avec solutions), section A6 (livret PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Let \(S\) be a set of positive integers, possibly infinite, such that no positive integer greater than \(1\) divides all elements of \(S\). Determine all non-periodic infinite sequences \(a_1, a_2, a_3, \ldots\) of positive integers such that, for all positive integers \(n\),
- \(a_n \leq |a_{n+\ell} - \ell|\) for all \(\ell\) in \(S\), and
- \(a_n = |a_{n+\ell} - \ell|\) for at least one \(\ell\) in \(S\).
We say that an infinite sequence \(a_1, a_2, a_3, \ldots\) is periodic if there exists a positive integer \(t\) such that \(a_n = a_{n+t}\) for all positive integers \(n\).
Indices : les idées clés
- Principe des tiroirs (version infinie) : une suite bornée vérifiant les conditions serait périodique, car un bloc de \(2C\) termes consécutifs détermine tous les termes précédents.
- Divisibilité, PGCD et algorithme d'Euclide : par Bézout, tout entier assez grand est somme d'éléments d'une partie finie \(T \subset S\) de PGCD \(1\) ; les inégalités \(a_n \leq a_{n+t} - t\) se propagent alors à tous les grands décalages.
- Suites et récurrences : on étudie la suite \(b_n = a_n - n\), qui devient « presque croissante » puis stationnaire (solution 1), ou l'on montre directement \(a_{n+1} = a_n + 1\) à partir d'un rang (solution 2), avant de redescendre jusqu'à \(n = 1\).
- Sous-suites arithmétiques non bornées (solution 2) : un choix minimal du pas \(m\) et Bézout montrent que toutes les sous-suites \(a_n, a_{n+m}, a_{n+2m}, \ldots\) sont non bornées.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2025 (deux solutions).
Réponse : les suites \(a_n = n + c\), avec \(c \geq 0\) entier.
Solution 1¶
Ces suites conviennent, car \(a_n = n + c = |n + \ell + c - \ell| = |a_{n+\ell} - \ell|\) pour tout \(\ell \in S\) (et elles ne sont pas périodiques). Montrons que ce sont les seules. Soit \((a_n)\) une suite non périodique vérifiant les conditions.
Affirmation 1.1. La suite \((a_n)\) n'est pas bornée.
Preuve. Supposons par l'absurde \(a_n \leq C\) pour tout \(n\). Pour tout \(\ell \in S\) avec \(\ell > 2C\),
Donc, pour tout \(n\), les \(\ell \in S\) tels que \(a_n = |a_{n+\ell} - \ell|\) (il en existe au moins un) vérifient \(\ell \leq 2C\). Posons \(L_n = (a_{n+1}, a_{n+2}, \ldots, a_{n+2C})\). En utilisant la condition d'égalité, \(L_n\) détermine \(a_n\) (c'est le minimum des \(|a_{n+\ell} - \ell|\) pour \(\ell \in S\), \(\ell \leq 2C\)), donc détermine \(L_{n-1}\) ; par récurrence, \(L_n\) détermine \(L_m\) pour tout \(m \leq n\). Par le principe des tiroirs infini (il y a au plus \(C^{2C}\) tuples possibles), un même tuple \(L\) vérifie \(L = L_{n}\) pour une infinité d'indices \(n_1 < n_2 < \cdots\). D'après ce qui précède, \(n_{i+1} - n_i\) est constant, et la suite est périodique de période \(n_2 - n_1\) : contradiction. \(\square\)
Soit \(T\) une partie finie de \(S\) dont les éléments ont pour PGCD \(1\) (elle existe car aucun entier \(> 1\) ne divise tous les éléments de \(S\)), et \(M\) le plus grand élément de \(T\). Le lemme de Bézout donne :
Fait. Il existe un entier \(K > 0\) tel que tout entier \(> K\) est somme d'éléments (non nécessairement distincts) de \(T\).
Preuve du fait. Notons \(T = \{t_1, \ldots, t_k\}\) et \(K = (t_1 + \cdots + t_k)^2\). Soit \(m > K\). Par Bézout généralisé, \(m = w_1 t_1 + \cdots + w_k t_k\) avec des \(w_i \in \mathbb{Z}\). Si un \(w_i < 0\), l'inégalité \(m > K\) impose l'existence d'un \(j\) avec \(w_j \geq t_i\) (sinon \(m < t_i(t_1 + \cdots + t_k) \leq K\)). On remplace \((w_i, w_j)\) par \((w_i + t_j, w_j - t_i)\) : on obtient une autre écriture, et la somme des \(w\) négatifs a augmenté. Ce processus s'arrête sur une écriture avec tous les \(w_i \geq 0\). \(\square\)
Le livret écrit « Suppose \(w_j < 0\) … there exist \(j\) with \(w_j > t_i\) » ; il faut lire \(w_i < 0\) et \(w_j \geq t_i\).
Affirmation 1.2. Il existe \(N\) tel que \(a_n > M\) pour tout \(n > N\).
Preuve. Si \(a_n \leq M\), alors pour tout \(t \in T\) on a \(a_{n-t} \leq |a_n - t| \leq M\) (car \(a_n, t \in [1, M]\)). Donc \(a_{n - t_1 - \cdots - t_j} \leq M\) pour tous \(t_1, \ldots, t_j \in T\), c'est-à-dire, par le Fait, \(a_{n-k} \leq M\) pour tout \(k > K\) : \(a_m \leq M\) pour tout \(m < n - K\). Ainsi, si \(a_n \leq M\) pour une infinité de \(n\), alors \(a_n \leq M\) pour tout \(n\), ce qui contredit l'affirmation 1.1. \(\square\)
On pose \(b_n = a_n - n\).
Affirmation 1.3. \(b_n \leq b_{n+k}\) pour tous \(n > N\) et \(k > K\).
Preuve. Soit \(n > N\) et \(t \in T\). On ne peut pas avoir \(a_{n+t} \leq t - a_n\), car alors \(a_{n+t} < t - M \leq 0\). La condition \(a_n \leq |a_{n+t} - t|\) devient donc \(a_n \leq a_{n+t} - t\), soit \(b_n \leq b_{n+t}\), pour tous \(n > N\) et \(t \in T\). Par définition de \(K\), on en déduit \(b_n \leq b_{n+k}\) pour tout \(k > K\). \(\square\)
Affirmation 1.4. La suite \((b_n)\) est stationnaire.
Preuve. Observation : s'il existe un entier \(B\) tel que \(b_m \leq B\) pour une infinité d'indices \(m\), alors \(b_n \leq B\) pour tout \(n > N\). En effet, pour \(n > N\), il existe \(m > n + K\) avec \(b_m \leq B\), et l'affirmation 1.3 donne \(b_n \leq b_{n + (m-n)} = b_m \leq B\).
Montrons que \((b_n)\) est bornée. Sinon, elle n'est majorée à partir d'aucun rang par aucun entier. Prenons \(B > 0\) plus grand que certains termes de la suite : d'après l'observation (contraposée), \(b_m \leq B\) n'a lieu que pour un nombre fini d'indices, et il existe donc un indice \(m\) avec \(b_m \leq B\) et \(b_n > B\) pour tout \(n > m\). Il existe \(\ell \in S\) tel que
donc \(b_{m+\ell} = b_m \leq B\) : contradiction.
La suite \((b_n)\) étant bornée, si elle n'était pas stationnaire, elle prendrait au moins deux valeurs différentes une infinité de fois ; avec \(B\) la plus petite de ces deux valeurs, l'observation donnerait \(b_n \leq B\) pour tout \(n > N\), ce qui contredit le fait que la plus grande valeur est prise une infinité de fois. \(\square\)
Conclusion. Il existe \(L \geq 1\) et un entier \(c\) tels que \(a_n = n + c\) pour tout \(n \geq L\) ; prenons \(L\) minimal. Si \(L \geq 2\), alors pour tout \(\ell \in S\), \(|a_{L-1+\ell} - \ell| = |c + L - 1|\), donc \(a_{L-1} = |c + L - 1|\). Comme \(c = b_L = a_L - L\), on a \(c + L \geq 1\), donc \(a_{L-1} = L - 1 + c\), ce qui contredit la minimalité de \(L\). Ainsi \(L = 1\) et \(a_n = n + c\) pour tout \(n \geq 1\) ; comme \(a_1 \geq 1\), \(c \geq 0\). \(\blacksquare\)
Solution 2¶
Comme dans la solution 1, on montre d'abord que \((a_n)\) n'est pas bornée, puis l'énoncé plus fort suivant.
Affirmation 2.1. Pour tous entiers \(n, m \geq 1\), la sous-suite \(a_n, a_{n+m}, a_{n+2m}, \ldots\) n'est pas bornée.
Preuve. Sinon, soit \(m\) le plus petit entier pour lequel il existe \(n\) tel que \(a_n, a_{n+m}, a_{n+2m}, \ldots\) soit bornée. On a \(m > 1\), sinon toute la suite serait bornée. Il existe \(\ell \in S\) tel que \(d = \operatorname{pgcd}(\ell, m) < m\), puisque le PGCD des éléments de \(S\) vaut \(1\). Par minimalité de \(m\), la sous-suite \(a_n, a_{n+d}, a_{n+2d}, \ldots\) n'est pas bornée : on choisit \(N' \equiv n \pmod d\) avec \(a_{N'} > \ell\). On a \(a_{N'} \leq |a_{N'+\ell} - \ell|\) ; comme \(a_{N'} > \ell\), cela impose \(a_{N'+\ell} > \ell\), donc \(a_{N'+\ell} \geq a_{N'} + \ell\). Une récurrence simple donne \(a_{N'+k\ell} \geq a_{N'} + k\ell\) pour tout \(k \geq 1\). Par Bézout, puisque \(d = \operatorname{pgcd}(\ell, m)\) divise \(N' - n\), il existe une infinité de couples d'entiers positifs \((i, j)\) avec \(jm - i\ell = N' - n\), et alors \(a_{n+jm} = a_{N'+i\ell} \geq a_{N'} + i\ell\). La sous-suite \((a_{n+jm})\) n'est donc pas bornée : contradiction. \(\square\)
Affirmation 2.2. Pour tout \(\ell \in S\), il existe \(c_\ell \geq 1\) tel que \(a_{n+\ell} \geq a_n + \ell\) pour tout \(n \geq c_\ell\).
Preuve. Soit \(r\) un résidu, \(1 \leq r \leq \ell\). D'après l'affirmation 2.1, la sous-suite \(a_r, a_{r+\ell}, a_{r+2\ell}, \ldots\) n'est pas bornée : il existe \(k\) avec \(a_{r+k\ell} > \ell\). Comme \(a_{r+k\ell} \leq |a_{r+(k+1)\ell} - \ell|\), on a aussi \(a_{r+(k+1)\ell} > \ell\), donc \(a_{r+(k+1)\ell} \geq a_{r+k\ell} + \ell\). Par récurrence, \(a_{r+(m+1)\ell} \geq a_{r+m\ell} + \ell\) pour tout \(m \geq k\). Ainsi \(a_{n+\ell} \geq a_n + \ell\) pour \(n\) assez grand dans chaque classe modulo \(\ell\), donc pour tout \(n\) assez grand. \(\square\)
Par hypothèse sur \(S\), il existe \(\ell_1, \ldots, \ell_k \in S\) de PGCD \(1\). Comme dans le Fait de la solution 1, tout entier \(m\) assez grand s'écrit \(m = w_1\ell_1 + \cdots + w_k\ell_k\) avec des \(w_i \geq 0\) entiers.
Affirmation 2.3. Il existe \(N\) tel que \(a_{n+m} \geq a_n + m\) pour tous \(m, n \geq N\). En particulier, \(a_n \geq n - N\) pour tout \(n \geq 2N\).
Preuve. On prend \(N\) supérieur à \(c_{\ell_1}, \ldots, c_{\ell_k}\) et tel que tout \(m \geq N\) s'écrive \(m = w_1\ell_1 + \cdots + w_k\ell_k\) avec des \(w_i \geq 0\). Pour \(n, m \geq N\), en appliquant plusieurs fois l'affirmation 2.2,
Affirmation 2.4. Pour tous \(n \geq 2N\) et \(m \geq N\), \(a_{n+m} = a_n + m\).
Preuve. Fixons \(n \geq 2N\). Montrons d'abord qu'il existe une infinité de \(m\) avec \(a_{n+m} = a_n + m\). Il existe \(s_1 \in S\) tel que \(a_n = |a_{n+s_1} - s_1|\) ; comme \(n + s_1 \geq 2N\), l'affirmation 2.3 donne \(a_{n+s_1} \geq n + s_1 - N > s_1\), donc \(a_n = a_{n+s_1} - s_1\). De même, il existe \(s_2 \in S\) avec \(a_{n+s_1+s_2} = a_{n+s_1} + s_2 = a_n + s_1 + s_2\), et ainsi de suite.
Soit maintenant \(m \geq N\). Il existe \(M' \geq N + m\) tel que \(a_{n+M'} = a_n + M'\). Par l'affirmation 2.3 (appliquée deux fois, \(M' - m \geq N\) et \(m \geq N\)),
Comme \(a_{n+M'} = a_n + M'\), ce sont des égalités, d'où \(a_{n+m} = a_n + m\). \(\square\)
Affirmation 2.5. Pour tout \(n \geq 2N\), \(a_{n+1} = a_n + 1\).
Preuve. Pour \(m \geq N\), l'affirmation 2.4 donne \(a_n + m + 1 = a_{n+m+1} = a_{n+1} + m\). \(\square\)
Conclusion. On a \(a_{n+1} = a_n + 1\) pour tout \(n \geq 2N\). En particulier \(a_{2N-1+\ell} = a_{2N} - 1 + \ell \geq \ell\) pour tout \(\ell \in S\), donc
En répétant cet argument, \(a_{n+1} = a_n + 1\) pour tout \(n \geq 1\), donc \(a_n = n + c\) pour une constante entière \(c\), et \(c \geq 0\) car \(a_1 \geq 1\). \(\blacksquare\)