Aller au contenu

Shortlist 2008, A4

Domaine : Algèbre · Difficulté : ★★★☆☆ · Proposé par : non indiqué

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

Solution officielle : Shortlist officielle 2008 (avec solutions), p. 12 (page 13 du PDF)

Énoncé

Pour un entier \(m\), on note \(t(m)\) l'unique nombre de \(\{1, 2, 3\}\) tel que \(m + t(m)\) soit un multiple de \(3\). Une fonction \(f : \mathbb{Z} \to \mathbb{Z}\) vérifie \(f(-1) = 0\), \(f(0) = 1\), \(f(1) = -1\) et

\[f(2^n + m) = f(2^n - t(m)) - f(m) \qquad \text{pour tous entiers } m, n \geq 0 \text{ tels que } 2^n > m.\]

Montrer que \(f(3p) \geq 0\) pour tout entier \(p \geq 0\).

Énoncé original (anglais)

For an integer \(m\), denote by \(t(m)\) the unique number in \(\{1, 2, 3\}\) such that \(m + t(m)\) is a multiple of \(3\). A function \(f : \mathbb{Z} \to \mathbb{Z}\) satisfies \(f(-1) = 0\), \(f(0) = 1\), \(f(1) = -1\) and

\[f(2^n + m) = f(2^n - t(m)) - f(m) \qquad \text{for all integers } m, n \geq 0 \text{ with } 2^n > m.\]

Prove that \(f(3p) \geq 0\) holds for all integers \(p \geq 0\).

Indices : les idées clés
  • Valeurs clés : on calcule explicitement \(f(2^n - 1)\), \(f(2^n - 2)\), \(f(2^n - 3)\) selon la parité de \(n\), par récurrence ; elles valent \(0\), \(\pm 3^k\) ou \(2 \cdot 3^k\).
  • Divisibilité par \(3\) : \(f(2^n - t(m)) \geq 3^{(n-1)/2}\) si \(3 \mid 2^n + m\), et \(f(2^n - t(m)) \leq 0\) sinon.
  • Majoration : \(\lvert f(m) \rvert \leq 3^{n/2}\) pour \(m < 2^n\) ; en écrivant \(3p = 2^a + 2^b + c\), deux applications de la récurrence donnent \(f(3p) \geq 3^{(a-1)/2} - 3^{b/2} \geq 0\).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2008 (une solution).

Solution

Les conditions données déterminent \(f\) de façon unique sur les entiers strictement positifs. Les signes de \(f(1), f(2), \ldots\) semblent changer de façon assez erratique. Cependant, les valeurs de la forme \(f(2^n - t(m))\) suffisent pour calculer directement toute valeur de la fonction. En effet, soit \(n > 0\) d'écriture binaire \(n = 2^{a_0} + 2^{a_1} + \cdots + 2^{a_k}\), \(a_0 > a_1 > \cdots > a_k \geq 0\), et posons \(n_j = 2^{a_j} + 2^{a_{j-1}} + \cdots + 2^{a_k}\), \(j = 0, \ldots, k\). Des applications répétées de la récurrence montrent que \(f(n)\) est une somme alternée des quantités \(f(2^{a_j} - t(n_{j+1}))\) plus \((-1)^{k+1}\). (La formule exacte n'est pas nécessaire pour notre preuve.)

On s'intéresse donc aux valeurs \(f(2^n - 1)\), \(f(2^n - 2)\) et \(f(2^n - 3)\). Six cas se présentent ; plus précisément,

\[t(2^{2k} - 3) = 2, \quad t(2^{2k} - 2) = 1, \quad t(2^{2k} - 1) = 3, \quad t(2^{2k+1} - 3) = 1, \quad t(2^{2k+1} - 2) = 3, \quad t(2^{2k+1} - 1) = 2.\]

Affirmation. Pour tout entier \(k \geq 0\), on a les égalités suivantes :

\[\begin{aligned} f(2^{2k+1} - 3) &= 0, & f(2^{2k+1} - 2) &= 3^k, & f(2^{2k+1} - 1) &= -3^k, \\ f(2^{2k+2} - 3) &= -3^k, & f(2^{2k+2} - 2) &= -3^k, & f(2^{2k+2} - 1) &= 2 \cdot 3^k. \end{aligned}\]

Preuve. Récurrence sur \(k\). Le cas de base \(k = 0\) revient à vérifier que \(f(2) = -1\) et \(f(3) = 2\) ; les valeurs données \(f(-1) = 0\), \(f(0) = 1\), \(f(1) = -1\) servent aussi. Supposons l'affirmation vraie pour \(k - 1\). Pour \(f(2^{2k+1} - t(m))\), la récurrence et l'hypothèse de récurrence donnent

\[\begin{aligned} f(2^{2k+1} - 3) &= f(2^{2k} + (2^{2k} - 3)) = f(2^{2k} - 2) - f(2^{2k} - 3) = -3^{k-1} + 3^{k-1} = 0, \\ f(2^{2k+1} - 2) &= f(2^{2k} + (2^{2k} - 2)) = f(2^{2k} - 1) - f(2^{2k} - 2) = 2 \cdot 3^{k-1} + 3^{k-1} = 3^k, \\ f(2^{2k+1} - 1) &= f(2^{2k} + (2^{2k} - 1)) = f(2^{2k} - 3) - f(2^{2k} - 1) = -3^{k-1} - 2 \cdot 3^{k-1} = -3^k. \end{aligned}\]

Pour \(f(2^{2k+2} - t(m))\), on utilise les trois égalités qu'on vient d'établir :

\[\begin{aligned} f(2^{2k+2} - 3) &= f(2^{2k+1} + (2^{2k+1} - 3)) = f(2^{2k+1} - 1) - f(2^{2k+1} - 3) = -3^k - 0 = -3^k, \\ f(2^{2k+2} - 2) &= f(2^{2k+1} + (2^{2k+1} - 2)) = f(2^{2k+1} - 3) - f(2^{2k+1} - 2) = 0 - 3^k = -3^k, \\ f(2^{2k+2} - 1) &= f(2^{2k+1} + (2^{2k+1} - 1)) = f(2^{2k+1} - 2) - f(2^{2k+1} - 1) = 3^k + 3^k = 2 \cdot 3^k. \end{aligned}\]

L'affirmation en découle. \(\square\)

En examinant de plus près les six cas, on voit que \(f(2^n - t(m)) \geq 3^{(n-1)/2}\) si \(2^n - t(m)\) est divisible par \(3\), et \(f(2^n - t(m)) \leq 0\) sinon. D'autre part, remarquons que \(2^n - t(m)\) est divisible par \(3\) si et seulement si \(2^n + m\) l'est. Donc, pour tous entiers positifs ou nuls \(m\) et \(n\),

(i) \(f(2^n - t(m)) \geq 3^{(n-1)/2}\) si \(2^n + m\) est divisible par \(3\) ;

(ii) \(f(2^n - t(m)) \leq 0\) si \(2^n + m\) n'est pas divisible par \(3\).

Une autre conséquence directe de l'affirmation est que \(\lvert f(2^n - t(m)) \rvert \leq \frac{2}{3} \cdot 3^{n/2}\) pour tous \(m, n \geq 0\).

Cette dernière inégalité permet de majorer \(\lvert f(m) \rvert\) pour \(m\) inférieur à une puissance de \(2\) donnée. Montrons par récurrence sur \(n\) que \(\lvert f(m) \rvert \leq 3^{n/2}\) pour tous entiers \(m, n \geq 0\) avec \(2^n > m\).

Le cas de base \(n = 0\) est clair, puisque \(f(0) = 1\). Pour passer de \(n\) à \(n + 1\), soient \(m\) et \(n\) tels que \(2^{n+1} > m\). Si \(m < 2^n\), l'hypothèse de récurrence conclut. Si \(m \geq 2^n\), alors \(m = 2^n + k\) avec \(2^n > k \geq 0\). Par \(\lvert f(2^n - t(k)) \rvert \leq \frac{2}{3} \cdot 3^{n/2}\) et l'hypothèse de récurrence,

\[\lvert f(m) \rvert = \lvert f(2^n - t(k)) - f(k) \rvert \leq \lvert f(2^n - t(k)) \rvert + \lvert f(k) \rvert \leq \frac{2}{3} \cdot 3^{n/2} + 3^{n/2} < 3^{(n+1)/2}.\]

La récurrence est terminée.

Montrons enfin que \(f(3p) \geq 0\) pour tout entier \(p \geq 0\). Pour \(p = 0\), c'est clair (\(f(0) = 1\)). Pour \(p \geq 1\), comme \(3p\) n'est pas une puissance de \(2\), son écriture binaire contient au moins deux termes. On peut donc écrire \(3p = 2^a + 2^b + c\) avec \(a > b\) et \(2^b > c \geq 0\). En appliquant deux fois la récurrence, on obtient

\[f(3p) = f(2^a + 2^b + c) = f(2^a - t(2^b + c)) - f(2^b - t(c)) + f(c).\]

Comme \(2^a + 2^b + c\) est divisible par \(3\), on a \(f(2^a - t(2^b + c)) \geq 3^{(a-1)/2}\) d'après (i). Comme \(2^b + c\) n'est pas divisible par \(3\), on a \(f(2^b - t(c)) \leq 0\) d'après (ii). Enfin, \(\lvert f(c) \rvert \leq 3^{b/2}\) puisque \(2^b > c \geq 0\), de sorte que \(f(c) \geq -3^{b/2}\). Donc \(f(3p) \geq 3^{(a-1)/2} - 3^{b/2}\), qui est positif ou nul puisque \(a > b\). \(\blacksquare\)

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2023 N5 ★★★☆☆ : Une suite croissante dont chaque terme divise le double de la somme des précédents : si elle fait intervenir une infinité de premiers, tout entier divise l'un de ses termes.
  • 2018 A4 ★★★☆☆ : Chaque terme est la moyenne de quelques termes précédents, choisis librement : quelle est la plus grande valeur de \(a_{2018} - a_{2017}\) ?
  • 2009 A6 ★★★☆☆ · OIM P3 : Si deux sous-suites extraites d'une suite croissante sont arithmétiques, la suite elle-même l'est.
  • 2006 A3 ★★★☆☆ : Les couples \((\sum c_j, \sum c_{j-1})\) formés avec une suite de type Fibonacci sont exactement les points entiers d'une bande.