Shortlist 2010, N6¶
Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : Iran
Concepts : Valuations p-adiques et lemme LTE · Suites et récurrences · Graphes : degrés, chemins, arbres
Solution officielle : Shortlist officielle 2010 (avec solutions), p. 72 (page 73 du PDF)
Énoncé¶
The rows and columns of a \(2^n \times 2^n\) table are numbered from \(0\) to \(2^n - 1\). The cells of the table have been colored with the following property being satisfied: for each \(0 \leq i, j \leq 2^n - 1\), the \(j\)th cell in the \(i\)th row and the \((i + j)\)th cell in the \(j\)th row have the same color. (The indices of the cells in a row are considered modulo \(2^n\).)
Prove that the maximal possible number of colors is \(2^n\).
Indices : les idées clés
- Graphe des flèches \((i, j) \to (j, i + j)\) : c'est une union disjointe de cycles, et le nombre maximal de couleurs est le nombre de cycles.
- Suites de type Fibonacci modulo \(2^n\) : un cycle correspond à une suite récurrente \(a_{k+1} = a_k + a_{k-1}\) ; on étudie \(\nu_2(F_{3 \cdot 2^{m-2}}) = m\) et la période modulo \(2^m\).
- Valuation 2-adique : si \(\mu(A) = k < n\), la période est \(3 \cdot 2^{n-1-k}\) ; on compte \(2^{n-1-k}\) cycles pour chaque \(k\), plus le cycle de \((0, 0)\), soit \(2^n\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2010 (une solution et une remarque).
Solution¶
Dans toute la solution, on note les cases du tableau par des couples de coordonnées ; \((i, j)\) désigne la \(j\)-ième case de la \(i\)-ième ligne.
Considérons le graphe orienté dont les sommets sont les cases du tableau et dont les arêtes sont les flèches \((i, j) \to (j, i + j)\) pour tous \(0 \leq i, j \leq 2^n - 1\). De chaque sommet \((i, j)\) part exactement une arête (vers \((j, i + j \bmod 2^n)\)) ; réciproquement, dans chaque case \((j, k)\) arrive exactement une arête (depuis la case \((k - j \bmod 2^n, j)\)). Le graphe se décompose donc en cycles.
Dans toute coloration considérée, les sommets d'un même cycle doivent avoir la même couleur, d'après la condition du problème. D'autre part, si chaque cycle a sa propre couleur, la coloration obtenue vérifie évidemment les conditions du problème. Le nombre maximal de couleurs est donc égal au nombre de cycles, et il faut prouver que ce nombre vaut \(2^n\).
Considérons un cycle quelconque \((i_1, j_1), (i_2, j_2), \ldots\) ; nous allons le décrire autrement. Définissons une suite \((a_0, a_1, \ldots)\) par \(a_0 = i_1\), \(a_1 = j_1\), \(a_{n+1} = a_n + a_{n-1}\) pour tout \(n \geq 1\) (on dit qu'une telle suite est de type Fibonacci). Une récurrence évidente montre alors que \(i_k \equiv a_{k-1} \pmod{2^n}\), \(j_k \equiv a_k \pmod{2^n}\). Il faut donc étudier le comportement des suites de type Fibonacci modulo \(2^n\).
Notons \(F_0, F_1, \ldots\) les nombres de Fibonacci définis par \(F_0 = 0\), \(F_1 = 1\) et \(F_{n+2} = F_{n+1} + F_n\) pour \(n \geq 0\). On pose aussi \(F_{-1} = 1\), conformément à la relation de récurrence.
Pour tout entier \(m > 0\), notons \(\nu(m)\) l'exposant de \(2\) dans la décomposition en facteurs premiers de \(m\), c'est-à-dire l'entier tel que \(2^{\nu(m)} \mid m\) mais \(2^{\nu(m)+1} \nmid m\).
Lemme 1. Pour toute suite de type Fibonacci \(a_0, a_1, a_2, \ldots\) et tout \(k \geq 0\), on a \(a_k = F_{k-1}a_0 + F_ka_1\).
Preuve. Récurrence sur \(k\). Les cas de base \(k = 0, 1\) sont triviaux. Pour l'hérédité, l'hypothèse de récurrence donne
Lemme 2. Pour tout \(m \geq 3\),
(a) on a \(\nu(F_{3 \cdot 2^{m-2}}) = m\) ;
(b) \(d = 3 \cdot 2^{m-2}\) est le plus petit indice strictement positif tel que \(2^m \mid F_d\) ;
(c) \(F_{3 \cdot 2^{m-2} + 1} \equiv 1 + 2^{m-1} \pmod{2^m}\).
Preuve. Récurrence sur \(m\). Dans le cas de base \(m = 3\), on a \(F_{3 \cdot 2^{m-2}} = F_6 = 8\), donc \(\nu(F_6) = \nu(8) = 3\) ; les nombres de Fibonacci précédents ne sont pas divisibles par \(8\), et en effet \(F_{3 \cdot 2^{m-2} + 1} = F_7 = 13 \equiv 1 + 4 \pmod 8\).
Supposons maintenant \(m > 3\) et posons \(k = 3 \cdot 2^{m-3}\). En appliquant le lemme 1 à la suite de type Fibonacci \(F_k, F_{k+1}, \ldots\), on obtient
D'après l'hypothèse de récurrence, \(\nu(F_k) = m - 1\), et \(F_{k+1}\) est impair. On obtient donc \(\nu(F_k^2) = 2(m - 1) > (m - 1) + 1 = \nu(2F_kF_{k+1})\), ce qui implique \(\nu(F_{2k}) = m\) et établit l'affirmation (a).
De plus, comme \(F_{k+1} = 1 + 2^{m-2} + a2^{m-1}\) pour un certain entier \(a\), on obtient
comme voulu pour l'affirmation (c).
Il reste à prouver que \(2^m \nmid F_\ell\) pour \(\ell < 2k\). Supposons le contraire. Comme \(2^{m-1} \mid F_\ell\), l'hypothèse de récurrence donne \(\ell > k\). Mais alors \(F_\ell = F_{k-1}F_{\ell-k} + F_kF_{\ell-k+1}\), où le second terme est divisible par \(2^{m-1}\) mais pas le premier (puisque \(F_{k-1}\) est impair et \(\ell - k < k\)). La somme n'est donc même pas divisible par \(2^{m-1}\). Contradiction. \(\square\)
Pour tout couple d'entiers \((a, b) \neq (0, 0)\), posons \(\mu(a, b) = \min\{\nu(a), \nu(b)\}\). Par une récurrence évidente, pour toute suite de type Fibonacci \(A = (a_0, a_1, \ldots)\), on a \(\mu(a_0, a_1) = \mu(a_1, a_2) = \cdots\) ; on note \(\mu(A)\) cette valeur commune. On note aussi \(p_n(A)\) la période de cette suite modulo \(2^n\), c'est-à-dire le plus petit \(p > 0\) tel que \(a_{k+p} \equiv a_k \pmod{2^n}\) pour tout \(k \geq 0\).
Lemme 3. Soit \(A = (a_0, a_1, \ldots)\) une suite de type Fibonacci telle que \(\mu(A) = k < n\). Alors \(p_n(A) = 3 \cdot 2^{n-1-k}\).
Preuve. Remarquons d'abord que la suite \((a_0, a_1, \ldots)\) est de période \(p\) modulo \(2^n\) si et seulement si la suite \((a_0/2^k, a_1/2^k, \ldots)\) est de période \(p\) modulo \(2^{n-k}\). En passant à cette suite, on peut donc supposer \(k = 0\).
Prouvons l'énoncé par récurrence sur \(n\). On voit facilement que l'affirmation est vraie pour \(n = 1, 2\) ; en effet, toute suite de type Fibonacci \(A\) avec \(\mu(A) = 0\) se comporte comme \(0, 1, 1, 0, 1, 1, \ldots\) modulo \(2\), et comme \(0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, \ldots\) modulo \(4\) (tous les couples de résidus dont l'un au moins est impair apparaissent comme couples de termes consécutifs de cette suite).
Supposons maintenant \(n \geq 3\) et considérons une suite de type Fibonacci quelconque \(A = (a_0, a_1, \ldots)\) avec \(\mu(A) = 0\). On doit évidemment avoir \(p_{n-1}(A) \mid p_n(A)\), soit, d'après l'hypothèse de récurrence, \(s = 3 \cdot 2^{n-2} \mid p_n(A)\). On peut ensuite supposer \(a_0\) pair ; alors \(a_1\) est impair, et \(a_0 = 2b_0\), \(a_1 = 2b_1 + 1\) pour des entiers \(b_0\), \(b_1\).
Considérons la suite de type Fibonacci \(B = (b_0, b_1, \ldots)\) commençant par \((b_0, b_1)\). Comme \(a_0 = 2b_0 + F_0\), \(a_1 = 2b_1 + F_1\), une récurrence facile donne \(a_k = 2b_k + F_k\) pour tout \(k \geq 0\). D'après l'hypothèse de récurrence, \(p_{n-1}(B) \mid s\), donc la suite \((2b_0, 2b_1, \ldots)\) est \(s\)-périodique modulo \(2^n\). D'autre part, d'après le lemme 2, \(F_{s+1} \equiv 1 + 2^{n-1} \pmod{2^n}\), \(F_{2s} \equiv 0 \pmod{2^n}\), \(F_{2s+1} \equiv 1 \pmod{2^n}\), donc
La première ligne signifie que \(A\) n'est pas \(s\)-périodique, tandis que les deux autres donnent \(a_{2s} \equiv a_0\), \(a_{2s+1} \equiv a_1\), et donc \(a_{2s+t} \equiv a_t\) pour tout \(t \geq 0\). Ainsi \(s \mid p_n(A) \mid 2s\) et \(p_n(A) \neq s\), ce qui signifie que \(p_n(A) = 2s\), comme voulu. \(\square\)
Enfin, le lemme 3 fournit une méthode directe pour compter les cycles. Prenons un nombre \(0 \leq k \leq n - 1\) et considérons toutes les cases \((i, j)\) telles que \(\mu(i, j) = k\). Le nombre total de ces cases est \(2^{2(n-k)} - 2^{2(n-k-1)} = 3 \cdot 2^{2n-2k-2}\). D'autre part, elles se répartissent en cycles, et, d'après le lemme 3, chaque cycle a pour longueur \(3 \cdot 2^{n-1-k}\). Le nombre de cycles formés par ces cases est donc exactement \(\frac{3 \cdot 2^{2n-2k-2}}{3 \cdot 2^{n-1-k}} = 2^{n-k-1}\). Enfin, il n'y a qu'une case, \((0, 0)\), qui n'est pas prise en compte dans ce calcul, et elle forme un cycle à part. Le nombre total de cycles est donc
Remarque¶
Voici l'esquisse d'une autre preuve de la partie essentielle du lemme 3. On suppose \(k = 0\) et l'on montre que, dans ce cas, la période de \((a_i)\) modulo \(2^n\) coïncide avec la période des nombres de Fibonacci modulo \(2^n\) ; on termine ensuite avec les arguments du lemme 2.
Remarquons que \(p\) est une période (pas nécessairement minimale) de la suite \((a_i)\) modulo \(2^n\) si et seulement si \(a_0 \equiv a_p \pmod{2^n}\) et \(a_1 \equiv a_{p+1} \pmod{2^n}\), c'est-à-dire
Si \(p\) est une période de \((F_i)\), alors \(F_p \equiv F_0 = 0 \pmod{2^n}\) et \(F_{p+1} \equiv F_1 = 1 \pmod{2^n}\), donc, d'après (1), \(p\) est aussi une période de \((a_i)\).
Réciproquement, supposons que \(p\) soit une période de \((a_i)\). En combinant les relations (1), on obtient
Comme l'un au moins des nombres \(a_0\), \(a_1\) est impair, le nombre \(a_1^2 - a_1a_0 - a_0^2\) est impair aussi. Les relations précédentes équivalent donc à \(F_p \equiv 0 \pmod{2^n}\) et \(F_{p+1} \equiv 1 \pmod{2^n}\), ce qui signifie exactement que \(p\) est une période de \((F_0, F_1, \ldots)\) modulo \(2^n\).
Les ensembles des périodes de \((a_i)\) et de \((F_i)\) coïncident donc, et en particulier leurs périodes minimales aussi.