Shortlist 2012, N7¶
Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : non indiqué
Concepts : Récurrence et constructions récursives · Congruences, théorèmes de Fermat et d'Euler
Solution officielle : Shortlist officielle 2012 (avec solutions), p. 49 (page 49 du PDF)
Problème 6 de l'OIM 2012
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2012, où il était le problème 6 (jour 2).
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Find all \(n \in \mathbb{N}\) for which there exist nonnegative integers \(a_1, a_2, \ldots, a_n\) such that
Indices : les idées clés
- Parité : en multipliant par une puissance de \(3\), \(1 \cdot x_1 + \cdots + n \cdot x_n = 3^a\) avec des \(x_i\) impairs, donc \(1 + 2 + \cdots + n\) est impair : \(n \equiv 1, 2 \pmod 4\).
- Opération inverse : remplacer un terme \(b_k\) par deux termes \(u\), \(v\) de somme \(3b_k\) (avec l'exposant \(a_k + 1\)) conserve la « faisabilité » ; on réduit donc \(1, 2, \ldots, n\) par des opérations \(\{u, v\} \mapsto \frac{u + v}{3}\).
- Récurrence de pas \(12\) : pour \(n \geq 16\), on ramène \(\alpha_n\) à \(\alpha_{n-12}\) en \(12\) opérations, puis on traite à la main \(n \leq 15\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2012 (une solution).
Solution¶
Réponse : les \(n\) tels que \(n \equiv 1 \pmod 4\) ou \(n \equiv 2 \pmod 4\).
Supposons \(\sum_{k=1}^{n} \frac{k}{3^{a_k}} = 1\) avec \(a_1, a_2, \ldots, a_n\) entiers positifs ou nuls. Alors \(1 \cdot x_1 + 2 \cdot x_2 + \cdots + n \cdot x_n = 3^a\), où \(x_1, \ldots, x_n\) sont des puissances de \(3\) et \(a \geq 0\). Le membre de droite est impair, et le membre de gauche a la même parité que \(1 + 2 + \cdots + n\). Cette somme est donc impaire, ce qui implique \(n \equiv 1, 2 \pmod 4\). Prouvons maintenant la réciproque.
Disons qu'une suite \(b_1, b_2, \ldots, b_n\) est faisable s'il existe des entiers positifs ou nuls \(a_1, a_2, \ldots, a_n\) tels que
Soit \(b_k\) un terme d'une suite faisable \(b_1, \ldots, b_n\), d'exposants \(a_1, \ldots, a_n\) comme ci-dessus, et soient \(u\), \(v\) des entiers positifs ou nuls de somme \(3b_k\). On remarque que
Il s'ensuit que la suite \(b_1, \ldots, b_{k-1}, u, v, b_{k+1}, \ldots, b_n\) est faisable : les exposants \(a_i\) sont les mêmes pour les termes inchangés, et les nouveaux termes \(u\), \(v\) ont l'exposant \(a_k + 1\).
Énonçons la conclusion à l'envers : si l'on remplace deux termes \(u\), \(v\) d'une suite par un seul terme \(\frac{u + v}{3}\) et que la suite obtenue est faisable, alors la suite de départ est faisable aussi.
Notons \(\alpha_n\) la suite \(1, 2, \ldots, n\). Pour montrer que \(\alpha_n\) est faisable pour \(n \equiv 1, 2 \pmod 4\), on la transforme par \(n - 1\) remplacements \(\{u, v\} \mapsto \frac{u + v}{3}\) en la suite à un terme \(\alpha_1\). Celle-ci est faisable, avec \(a_1 = 0\). Remarquons que si \(m\) et \(2m\) sont des termes d'une suite, alors \(\{m, 2m\} \mapsto m\) ; on peut donc ignorer \(2m\) si besoin.
Soit \(n \geq 16\). Montrons que \(\alpha_n\) se ramène à \(\alpha_{n-12}\) en \(12\) opérations. Écrivons \(n = 12k + r\) avec \(k \geq 1\) et \(0 \leq r \leq 11\). Si \(0 \leq r \leq 5\), les \(12\) derniers termes de \(\alpha_n\) se répartissent en deux singletons \(\{12k - 6\}\), \(\{12k\}\) et les \(5\) paires suivantes :
(Il n'y a qu'un type de paires si \(r \in \{0, 5\}\).) On peut ignorer \(12k - 6\) et \(12k\), puisque \(\alpha_n\) contient \(6k - 3\) et \(6k\). De plus, les \(5\) opérations \(\{12k - 6 - i, 12k - 6 + i\} \mapsto 8k - 4\) et \(\{12k - j, 12k + j\} \mapsto 8k\) suppriment les \(10\) termes des paires et introduisent \(5\) nouveaux termes égaux à \(8k - 4\) ou \(8k\). On peut aussi tous les ignorer, puisque \(4k - 2\) et \(4k\) sont encore dans la suite. En effet, \(4k \leq n - 12\) équivaut à \(8k \geq 12 - r\), ce qui est vrai pour \(r \in \{4, 5\}\) ; et si \(r \in \{0, 1, 2, 3\}\), alors \(n \geq 16\) implique \(k \geq 2\), donc \(8k \geq 12 - r\) aussi. Ainsi \(\alpha_n\) se ramène à \(\alpha_{n-12}\).
Le cas \(6 \leq r \leq 11\) est analogue. On considère les singletons \(\{12k\}\), \(\{12k + 6\}\) et les \(5\) paires
On ignore les singletons comme avant, puis on supprime les paires par les opérations \(\{12k - i, 12k + i\} \mapsto 8k\) et \(\{12k + 6 - j, 12k + 6 + j\} \mapsto 8k + 4\). Les \(5\) nouveaux termes \(8k\) et \(8k + 4\) peuvent aussi être ignorés, puisque \(4k + 2 \leq n - 12\) (ce qui découle de \(k \geq 1\) et \(r \geq 6\)). On obtient à nouveau \(\alpha_{n-12}\).
Le problème se ramène à \(2 \leq n \leq 15\), et même à \(n \in \{2, 5, 6, 9, 10, 13, 14\}\) puisque \(n \equiv 1, 2 \pmod 4\). Les cas \(n = 2, 6, 10, 14\) se ramènent à \(n = 1, 5, 9, 13\) respectivement, car on peut ignorer le dernier terme pair de \(\alpha_n\). Pour \(n = 5\), on applique \(\{4, 5\} \mapsto 3\), puis \(\{3, 3\} \mapsto 2\), puis on ignore les deux occurrences de \(2\). Pour \(n = 9\), on ignore d'abord \(6\), puis on applique \(\{5, 7\} \mapsto 4\), \(\{4, 8\} \mapsto 4\), \(\{3, 9\} \mapsto 4\) ; on ignore alors les trois occurrences de \(4\), puis \(2\). Enfin, \(n = 13\) se ramène à \(n = 10\) par \(\{11, 13\} \mapsto 8\), en ignorant \(8\) et \(12\). La preuve est complète. \(\blacksquare\)