Shortlist 2017, N1¶
Domaine : Théorie des nombres · Difficulté : ★☆☆☆☆ · Proposé par : South Africa
Concepts : Congruences, théorèmes de Fermat et d'Euler · Principe extrémal
Solution officielle : Shortlist officielle 2017 (avec solutions), p. 75 (page 77 du PDF)
Problème 1 de l'OIM 2017
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2017, où il était le problème 1 (jour 1).
Énoncé¶
The sequence \(a_0, a_1, a_2, \ldots\) of positive integers satisfies
for every \(n \geq 0\). Determine all values of \(a_0 > 1\) for which there is at least one number \(a\) such that \(a_n = a\) for infinitely many values of \(n\).
Indices : les idées clés
- Reformuler : comme \(a_{n+1}\) ne dépend que de \(a_n\), une valeur atteinte deux fois rend la suite périodique à partir d'un certain rang ; on cherche donc les \(a_0\) pour lesquels la suite est ultimement périodique.
- Carrés modulo 3 : un carré n'est jamais \(\equiv -1 \pmod 3\) ; dès qu'un terme est \(\equiv -1\), la suite croît strictement pour toujours.
- Descente : si \(a_n > 9\) et \(a_n \not\equiv -1 \pmod 3\), on atteint un carré parmi \((t+1)^2, (t+2)^2, (t+3)^2\), puis un terme \(\leq t + 3 < a_n\).
- Principe extrémal : on considère le plus petit terme de la suite après un certain rang, qui doit être \(\leq 9\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2017 (une solution).
Réponse : les valeurs cherchées sont tous les multiples positifs de \(3\) (avec \(a_0 > 1\)).
Solution 1¶
Comme \(a_{n+1}\) ne dépend que de \(a_n\), si \(a_n = a_m\) pour deux indices \(n \neq m\), la suite est périodique à partir d'un certain rang. Il s'agit donc de trouver les \(a_0\) pour lesquels la suite est ultimement périodique.
Affirmation 1. Si \(a_n \equiv -1 \pmod 3\), alors pour tout \(m > n\), \(a_m\) n'est pas un carré parfait. Par conséquent la suite est strictement croissante à partir d'un certain rang, donc pas ultimement périodique.
Preuve. Un carré n'est jamais congru à \(-1\) modulo \(3\), donc \(a_n \equiv -1 \pmod 3\) entraîne que \(a_n\) n'est pas un carré, d'où \(a_{n+1} = a_n + 3 > a_n\). Alors \(a_{n+1} \equiv a_n \equiv -1 \pmod 3\), et \(a_{n+1}\) n'est pas non plus un carré. En répétant l'argument, à partir de \(a_n\) aucun terme n'est un carré et chaque terme est plus grand que le précédent. \(\square\)
Affirmation 2. Si \(a_n \not\equiv -1 \pmod 3\) et \(a_n > 9\), il existe un indice \(m > n\) tel que \(a_m < a_n\).
Preuve. Soit \(t^2\) le plus grand carré strictement inférieur à \(a_n\). Comme \(a_n > 9\), \(t \geq 3\). Le premier carré de la suite \(a_n, a_n + 3, a_n + 6, \ldots\) sera \((t+1)^2\), \((t+2)^2\) ou \((t+3)^2\) (parmi ces trois carrés, l'un a le même reste que \(a_n\) modulo \(3\)). Il existe donc \(m > n\) tel que \(a_m \leq t + 3 < t^2 < a_n\). \(\square\)
Affirmation 3. Si \(a_n \equiv 0 \pmod 3\), il existe un indice \(m > n\) tel que \(a_m = 3\).
Preuve. Par définition de la suite, un multiple de \(3\) est toujours suivi d'un multiple de \(3\). Si \(a_n \in \{3, 6, 9\}\), la suite suit ensuite le cycle \(3, 6, 9, 3, 6, 9, \ldots\). Si \(a_n > 9\), soit \(j > n\) un indice tel que \(a_j\) soit le minimum de l'ensemble \(\{a_{n+1}, a_{n+2}, \ldots\}\) (principe extrémal). On a \(a_j \leq 9\), sinon l'affirmation 2 appliquée à \(a_j\) contredirait sa minimalité. Donc \(a_j \in \{3, 6, 9\}\), ce qui conclut. \(\square\)
Affirmation 4. Si \(a_n \equiv 1 \pmod 3\), il existe un indice \(m > n\) tel que \(a_m \equiv -1 \pmod 3\).
Preuve. Dans la suite, \(4\) est toujours suivi de \(2 \equiv -1 \pmod 3\) : l'affirmation est vraie pour \(a_n = 4\). Si \(a_n = 7\), les termes suivants sont \(10, 13, 16, 4, 2, \ldots\) : c'est vrai aussi. Pour \(a_n \geq 10\), prenons de nouveau \(j > n\) tel que \(a_j\) soit le minimum de \(\{a_{n+1}, a_{n+2}, \ldots\}\) ; cet ensemble ne contient aucun multiple de \(3\) (la racine carrée d'un non-multiple de \(3\) n'est pas un multiple de \(3\)). Supposons \(a_j \equiv 1 \pmod 3\). Par l'affirmation 2 et la minimalité, \(a_j \leq 9\), donc \(a_j \in \{4, 7\}\) ; mais alors \(a_m = 2 < a_j\) pour un certain \(m > j\), ce qui contredit la minimalité de \(a_j\). Donc \(a_j \equiv -1 \pmod 3\). \(\square\)
Conclusion. D'après ces affirmations : si \(a_0\) est un multiple de \(3\), la suite finit par suivre le cycle \(3, 6, 9, 3, 6, 9, \ldots\) ; si \(a_0 \equiv -1 \pmod 3\), elle est strictement croissante ; si \(a_0 \equiv 1 \pmod 3\), elle finit par être strictement croissante. La suite est donc ultimement périodique (et une valeur est atteinte une infinité de fois) si et seulement si \(a_0\) est un multiple de \(3\). \(\blacksquare\)