Shortlist 2023, N6¶

Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : China

Concepts : Congruences, théorèmes de Fermat et d'Euler · Suites et récurrences

Solution officielle : Shortlist officielle 2023 (avec solutions), p. 89 (page 91 du PDF)

Pas encore relu

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

Énoncé¶

A sequence of integers \(a_0, a_1, a_2, \ldots\) is called kawaii, if \(a_0 = 0\), \(a_1 = 1\), and, for any positive integer \(n\), we have

\[(a_{n+1} - 3a_n + 2a_{n-1})(a_{n+1} - 4a_n + 3a_{n-1}) = 0.\]

An integer is called kawaii if it belongs to a kawaii sequence.

Suppose that two consecutive positive integers \(m\) and \(m + 1\) are both kawaii (not necessarily belonging to the same kawaii sequence). Prove that \(3\) divides \(m\), and that \(m/3\) is kawaii.

Indices : les idées clés

Congruences : modulo \(3\), chaque terme est congru à l'un des deux précédents, donc tout entier kawaii est \(\equiv 0\) ou \(1 \pmod 3\) ; de même modulo \(2\).
Suites et récurrences : la récurrence se réécrit sur les différences, \(a_{n+1} - a_n = 2(a_n - a_{n-1})\) ou \(3(a_n - a_{n-1})\).
Dichotomie selon \(a_2\) : si \(a_2 = 3\), tous les termes (\(n \geq 1\)) sont impairs ; si \(a_2 = 4\), ils sont tous \(\equiv 1 \pmod 3\).
Changement de suite \(a'_n = \frac{a_{n+1} - 1}{3}\) : il transforme une suite kawaii de la deuxième sorte en une suite kawaii, et fait apparaître \(m/3\).

Solutions

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

Solution 1¶

La condition s'écrit

\[a_{n+1} = 3a_n - 2a_{n-1} \quad \text{ou} \quad a_{n+1} = 4a_n - 3a_{n-1}.\]

On a donc \(a_{n+1} \equiv a_n\) ou \(a_{n-1} \pmod 2\), et \(a_{n+1} \equiv a_{n-1}\) ou \(a_n \pmod 3\), pour tout \(n \geq 1\). Comme \(a_0 = 0\) et \(a_1 = 1\), on obtient \(a_n \equiv 0\) ou \(1 \pmod 3\) pour tout \(n \geq 0\). Puisque \(m\) et \(m+1\) sont kawaii, aucun des deux n'est \(\equiv 2 \pmod 3\), donc nécessairement \(m \equiv 0 \pmod 3\).

On remarque aussi que \(a_2 = 3\) ou \(a_2 = 4\), et :

si \(a_2 = 3\), alors \(a_n \equiv 1 \pmod 2\) pour tout \(n \geq 1\), puisque \(a_1 \equiv a_2 \equiv 1 \pmod 2\) ;
si \(a_2 = 4\), alors \(a_n \equiv 1 \pmod 3\) pour tout \(n \geq 1\), puisque \(a_1 \equiv a_2 \equiv 1 \pmod 3\).

Comme \(m \equiv 0 \pmod 3\), une suite kawaii contenant \(m\) ne vérifie pas (2), donc vérifie (1) : \(m\) est impair, et \(m+1\) est pair.

Prenons une suite kawaii \((a_n)\) contenant \(m+1\), et soit \(t \geq 2\) tel que \(a_t = m+1\). Elle ne vérifie pas (1) (\(m+1\) est pair), donc elle vérifie (2) : \(a_n \equiv 1 \pmod 3\) pour tout \(n \geq 1\). Définissons

\[a'_n = \frac{a_{n+1} - 1}{3}.\]

C'est une suite kawaii : \(a'_0 = 0\), \(a'_1 = 1\) et, pour tout \(n \geq 1\),

\[(a'_{n+1} - 3a'_n + 2a'_{n-1})(a'_{n+1} - 4a'_n + 3a'_{n-1}) = \frac{(a_{n+2} - 3a_{n+1} + 2a_n)(a_{n+2} - 4a_{n+1} + 3a_n)}{9} = 0.\]

Enfin \(a'_{t-1} = \frac{m}{3}\), donc \(m/3\) est kawaii. \(\blacksquare\)

Solution 2¶

Affirmation 1. \(a_n \equiv 0\) ou \(1 \pmod 3\) pour tout \(n \geq 0\).

Preuve. On a \(a_{n+1} = 3a_n - 2a_{n-1} = 3(a_n - a_{n-1}) + a_{n-1}\) ou \(a_{n+1} = 4a_n - 3a_{n-1} = 3(a_n - a_{n-1}) + a_n\), donc \(a_{n+1} \equiv a_n\) ou \(a_{n-1} \pmod 3\) ; comme \(a_0 = 0\) et \(a_1 = 1\), le résultat suit. \(\square\)

Donc si \(m\) et \(m+1\) sont kawaii, nécessairement \(m \equiv 0 \pmod 3\).

Affirmation 2. Un entier \(\geq 2\) est kawaii si et seulement s'il s'écrit \(1 + b_2 + \cdots + b_n\) pour un certain \(n \geq 2\), avec \(b_i = 2^{r_i} 3^{s_i}\), \(r_i + s_i = i - 1\) pour \(i = 2, \ldots, n\), et \(b_i \mid b_{i+1}\) pour \(i = 2, \ldots, n-1\).

Preuve. Pour une suite kawaii, \(a_{n+1} = a_n + 2(a_n - a_{n-1})\) ou \(a_{n+1} = a_n + 3(a_n - a_{n-1})\), donc \(a_{n+1} - a_n = 2(a_n - a_{n-1})\) ou \(3(a_n - a_{n-1})\). Par conséquent \(a_n = 1 + b_2 + \cdots + b_n\) avec \(b_2 = 2\) ou \(3\) et \(b_{i+1} = 2b_i\) ou \(3b_i\).

Réciproquement, pour un nombre écrit de cette façon, on pose \(a_0 = 0\), \(a_1 = 1\), \(a_i = 1 + b_2 + \cdots + b_i\) pour \(2 \leq i \leq n\), puis on prolonge par la condition kawaii pour \(i \geq n+1\). On obtient une suite kawaii contenant ce nombre comme \(a_n\). \(\square\)

Supposons \(m\) et \(m+1\) kawaii. D'après l'affirmation 2, en regroupant les premiers termes (ceux où l'on multiplie par \(2\)), on peut écrire

\[m = 1 + 2 + \cdots + 2^{\ell} + 2^{\ell} \cdot 3 \cdot A \quad \text{et} \quad m + 1 = 1 + 2 + \cdots + 2^{\ell'} + 2^{\ell'} \cdot 3 \cdot A'\]

avec \(A, A'\) entiers positifs ou nuls. Modulo \(3\) (puisque \(1 + 2 + \cdots + 2^{\ell} = 2^{\ell+1} - 1\), \(m \equiv 0\) et \(m + 1 \equiv 1\)), \(\ell\) est impair et \(\ell'\) est pair. Or, modulo \(2^{\min(\ell, \ell')}\), les deux écritures donnent \(m \equiv -1\) et \(m + 1 \equiv -1\), d'où \(m + 1 \equiv m \pmod{2^{\min(\ell, \ell')}}\), ce qui impose \(\min(\ell, \ell') = 0\), donc \(\ell' = 0\).

Ainsi \(m + 1 = 1 + b_2 + \cdots + b_j\) avec des \(b_i\) comme dans l'affirmation 2, \(b_2 = 3\) et \(b_i \mid b_{i+1}\) : donc \(3 \mid b_i\) pour tout \(i = 2, \ldots, j\). Alors

\[\frac{m}{3} = \frac{b_2 + \cdots + b_j}{3} = 1 + b'_2 + \cdots + b'_{j-1}, \qquad b'_i = \frac{b_{i+1}}{3},\]

où les \(b'_i\) vérifient les conditions de l'affirmation 2 ; donc \(m/3\) est kawaii. \(\blacksquare\)

Précision ajoutée : le passage modulo \(2^{\min(\ell,\ell')}\) est condensé dans le livret ; on a explicité que \(1 + 2 + \cdots + 2^{\ell - 1} = 2^{\ell} - 1 \equiv -1\) et que les autres termes sont divisibles par \(2^{\ell}\).

Solution 3¶

(Cette solution combine différemment les idées des solutions 1 et 2.)

Tout terme est \(\equiv 0\) ou \(1 \pmod 3\). Pour \(n \geq 1\), posons \(b_n = a_n - a_{n-1}\). Alors

\[a_t = a_0 + \sum_{k=1}^{t} (a_k - a_{k-1}) = \sum_{k=1}^{t} b_k. \tag{*}\]

On a \(a_{n+1} - 3a_n + 2a_{n-1} = b_{n+1} - 2b_n\) et \(a_{n+1} - 4a_n + 3a_{n-1} = b_{n+1} - 3b_n\). Les conditions définissant une suite kawaii sont donc

\[b_1 = a_1 - a_0 = 1 \quad \text{et} \quad \frac{b_{n+1}}{b_n} \in \{2, 3\} \text{ pour } n \geq 1.\]

Si \(\frac{b_{n+1}}{b_n} = 2\) pour tout \(1 \leq n \leq t-1\), alors \((*)\) donne \(a_t = \sum_{k=1}^{t} 2^{k-1} = 2^t - 1 \equiv 0\) ou \(1 \pmod 3\).
S'il existe \(s\) avec \(2 \leq s \leq t-1\) tel que \(\frac{b_2}{b_1} = \cdots = \frac{b_s}{b_{s-1}} = 2\) et \(\frac{b_{s+1}}{b_s} = 3\), alors \(3 \mid b_n\) pour tout \(n \geq s+1\), et comme en (1), \(a_t \equiv \sum_{k=1}^{s} b_k = 2^s - 1 \equiv 0\) ou \(1 \pmod 3\).
Si \(\frac{b_2}{b_1} = b_2 = 3\), alors \(3 \mid b_n\) pour tout \(n \geq 2\), donc \(a_t \equiv 1 \pmod 3\).

Dans tous les cas, \(a_t \equiv 0\) ou \(1 \pmod 3\).

Aucun entier kawaii strictement positif n'est divisible à la fois par \(2\) et par \(3\). Si \(b_2 = 2\), alors \(2 \mid b_n\) et \(a_n \equiv 1 \pmod 2\) pour tout \(n \geq 2\). Si \(b_2 = 3\), alors \(3 \mid b_n\) et \(a_n \equiv 1 \pmod 3\) pour tout \(n \geq 2\).

Conclusion. Comme \(m\) et \(m+1\) sont kawaii, \(m \equiv 0\) ou \(1\) et \(m + 1 \equiv 0\) ou \(1 \pmod 3\), d'où \(3 \mid m\). Un entier kawaii divisible par \(3\) est impair, donc \(m\) est impair et \(m+1\) est pair. Prenons une suite kawaii contenant \(m+1\) comme terme \(a_t\). Comme \(m+1\) est pair, \(b_2 = 3\), donc \(3 \mid b_n\) pour tout \(n \geq 2\). Posons

\[b'_n = \frac{b_{n+1}}{3} \quad (n \geq 1).\]

Alors \(b'_1 = \frac{b_2}{3} = 1\) et \(\frac{b'_{n+1}}{b'_n} = \frac{b_{n+2}}{b_{n+1}} \in \{2, 3\}\). Avec \(a'_0 = 0\) et \(a'_n = \sum_{k=1}^{n} b'_k\), la suite \((a'_n)\) est kawaii, et

\[a'_{t-1} = \sum_{k=1}^{t-1} b'_k = \frac{1}{3} \sum_{k=2}^{t} b_k = \frac{1}{3}\left(-b_1 + \sum_{k=1}^{t} b_k\right) = \frac{1}{3}(-1 + a_t) = \frac{m}{3}.\]

Donc \(m/3\) est kawaii. \(\blacksquare\)

Remarques¶

Remarque. Il existe une infinité d'entiers \(m\) tels que \(m\), \(m+1\) et \(m/3\) soient kawaii. En effet, si \(k \geq 1\) est kawaii, alors \(2k + 1\) et \(3k + 1\) sont kawaii (affirmation 2 de la solution 2), donc \(3(2k+1) + 1 = 6k + 4\) et \(2(3k+1) + 1 = 6k + 3\) aussi : on prend \(m = 6k + 3\), et \(m/3 = 2k + 1\).