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)

Pas encore relu

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

Énoncé

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\)