Shortlist 2018, N3¶
Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : Serbia
Concepts : Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2018 (avec solutions), p. 58 (page 60 du PDF)
Énoncé¶
Define the sequence \(a_0, a_1, a_2, \ldots\) by \(a_n = 2^n + 2^{\lfloor n/2 \rfloor}\). Prove that there are infinitely many terms of the sequence which can be expressed as a sum of (two or more) distinct terms of the sequence, as well as infinitely many of those which cannot be expressed in such a way.
Indices : les idées clés
- Passer au complémentaire : si \(b < a_n\) est somme de termes, ces termes sont parmi \(a_0, \ldots, a_{n-1}\), et \(S_{n-1} - b\) est la somme des termes restants.
- La somme partielle explicite \(S_{n-1} = a_0 + \cdots + a_{n-1} = 2^n + 2^{\lceil n/2 \rceil} + 2^{\lfloor n/2 \rfloor} - 3\) ramène la question à la représentabilité des nombres \(2^t - 3\) (solution 1) ou des puissances de \(4\) (solution 2).
- Construction récursive d'une suite infinie : une transformation \(t \mapsto 4t - 6\) (solution 1) ou \(s \mapsto 4s - 3\) (solution 2) qui préserve la représentabilité, appliquée à partir d'un exemple représentable et d'un exemple non représentable.
- Termes obligatoires : quand la somme de tous les termes disponibles dépasse à peine la cible, certains termes doivent figurer dans toute représentation.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2018 (deux solutions).
Solution 1¶
On dit qu'un entier \(b \geq 0\) est représentable s'il est somme de plusieurs termes distincts de la suite (éventuellement \(0\) ou \(1\) terme). Deux entiers \(b, c \geq 0\) sont équivalents (noté \(b \sim c\)) s'ils sont tous deux représentables ou tous deux non représentables.
On calcule facilement
En effet, \(S_n - S_{n-1} = 2^n + 2^{\lfloor n/2 \rfloor} = a_n\), et on conclut par récurrence. En particulier, \(S_{2k-1} = 2^{2k} + 2^{k+1} - 3\).
Si \(n \geq 3\), alors \(2^{\lceil n/2 \rceil} \geq 2^2 > 3\), donc
On remarque aussi que \(S_{n-1} - a_n = 2^{\lceil n/2 \rceil} - 3 < a_n\).
Affirmation 1. Soit \(b\) un entier positif tel que \(S_{n-1} - a_n < b < a_n\) pour un certain \(n \geq 3\). Alors \(b \sim S_{n-1} - b\).
Preuve. On a vu que \(S_{n-1} > a_n\). Posons \(c = S_{n-1} - b\) ; alors \(S_{n-1} - a_n < c < a_n\), donc les rôles de \(b\) et \(c\) sont symétriques. Supposons \(b\) représentable. Sa représentation ne peut pas contenir de \(a_i\) avec \(i \geq n\), puisque \(b < a_n\). Donc \(b\) est la somme d'une partie de \(\{a_0, a_1, \ldots, a_{n-1}\}\), et \(c\) est la somme du complémentaire. La réciproque s'obtient en échangeant \(b\) et \(c\). \(\square\)
Affirmation 2. Pour tout \(n \geq 3\), \(a_n\) s'écrit comme somme d'au moins deux termes distincts de la suite si et seulement si \(S_{n-1} - a_n = 2^{\lceil n/2 \rceil} - 3\) est représentable.
Preuve. Posons \(c = S_{n-1} - a_n < a_n\). Si \(a_n\) vérifie la condition, c'est la somme d'une partie de \(\{a_0, \ldots, a_{n-1}\}\), et \(c\) est la somme du complémentaire. Réciproquement, si \(c\) est représentable, sa représentation n'utilise que des termes de \(\{a_0, \ldots, a_{n-1}\}\), et \(a_n\) est la somme du complémentaire (ce complémentaire contient au moins deux termes, puisque chaque \(a_i\) avec \(i < n\) est strictement inférieur à \(a_n\)). \(\square\)
Précision ajoutée : la parenthèse finale n'est pas dans le livret, pas plus que la dernière phrase de la conclusion ci-dessous.
D'après l'affirmation 2, il suffit de trouver une infinité de nombres représentables de la forme \(2^t - 3\), et une infinité de nombres non représentables de cette forme.
Affirmation 3. Pour tout \(t \geq 3\), on a \(2^t - 3 \sim 2^{4t-6} - 3\), et \(2^{4t-6} - 3 > 2^t - 3\).
Preuve. L'inégalité découle de \(t \geq 3\). Pour l'équivalence, on applique deux fois l'affirmation 1. D'abord, comme
l'affirmation 1 donne \(2^t - 3 \sim S_{2t-3} - (2^t - 3) = 2^{2t-2}\). Ensuite, comme
l'affirmation 1 donne \(2^{2t-2} \sim S_{4t-7} - 2^{2t-2} = 2^{4t-6} - 3\). Donc \(2^t - 3 \sim 2^{2t-2} \sim 2^{4t-6} - 3\). \(\square\)
Conclusion. Le nombre \(2^3 - 3 = 5 = a_0 + a_1\) est représentable, donc l'affirmation 3 fournit une suite infinie de nombres représentables
Par ailleurs, \(2^7 - 3 = 125\) n'est pas représentable : par l'affirmation 1,
et \(4\) n'est clairement pas représentable (les premiers termes sont \(2, 3, 6, 10, \ldots\)). L'affirmation 3 fournit donc une suite infinie de nombres non représentables
Avec l'affirmation 2 (et \(2^{\lceil n/2 \rceil}\) prenant toutes les valeurs \(2^t\)), on obtient une infinité de termes \(a_n\) de chaque sorte. \(\blacksquare\)
Solution 2¶
On garde la notion de représentabilité et la notation \(S_n\). Un indice \(n\) est bon si \(a_n\) s'écrit comme somme de termes plus petits de la suite, mauvais sinon. Il faut montrer qu'il y a une infinité d'indices bons et une infinité d'indices mauvais.
Lemme 1. Pour tout entier \(m \geq 0\), \(4^m\) est représentable si et seulement si \(2m + 1\) est bon, si et seulement si \(2m + 2\) est bon.
Preuve. Le cas \(m = 0\) est évident ; supposons \(m \geq 1\). Soit \(n = 2m + 1\) ou \(2m + 2\) ; alors \(n \geq 3\). On a
Cette inégalité s'écrit \(2^n + 2^{\lceil n/2 \rceil} + 2^{\lfloor n/2 \rfloor} - 3 < 2^n + 2^{\lfloor n/2 \rfloor} + 2^{n-2} + 2^{\lfloor n/2 \rfloor - 1}\), c'est-à-dire \(2^{\lceil n/2 \rceil} < 2^{n-2} + 2^{\lfloor n/2 \rfloor - 1} + 3\). Si \(n \geq 4\), alors \(n/2 \leq n - 2\), donc \(\lceil n/2 \rceil \leq n - 2\) et \(2^{\lceil n/2 \rceil} \leq 2^{n-2}\). Pour \(n = 3\), on vérifie directement.
Si \(n\) est bon, \(a_n = a_{i_1} + \cdots + a_{i_r}\) avec \(r \geq 2\) et \(i_1 < \cdots < i_r < n\). Alors \(i_r = n - 1\) et \(i_{r-1} = n - 2\) : sinon, si \(n - 1\) ou \(n - 2\) manque parmi \(i_1, \ldots, i_r\), on aurait
Ainsi, si \(n\) est bon, \(a_n - a_{n-1}\) et \(a_n - a_{n-1} - a_{n-2}\) sont tous deux représentables.
Cas \(n = 2m + 1\). On a \(a_n - a_{n-1} = (2^{2m+1} + 2^m) - (2^{2m} + 2^m) = 2^{2m}\). Donc si \(2m + 1\) est bon, \(2^{2m}\) est représentable. Réciproquement, si \(2^{2m}\) est représentable, comme \(2^{2m} < a_{2m}\), c'est une somme de termes distincts \(a_i\) avec \(i < 2m\). Alors \(a_{2m+1} = a_{2m} + 2^{2m}\) s'écrit comme \(a_{2m}\) plus une somme de termes distincts \(a_i\) avec \(i < 2m\), donc \(2m + 1\) est bon.
Cas \(n = 2m + 2\). On a \(a_n - a_{n-1} - a_{n-2} = (2^{2m+2} + 2^{m+1}) - (2^{2m+1} + 2^m) - (2^{2m} + 2^m) = 2^{2m}\). Donc si \(2m + 2\) est bon, \(2^{2m}\) est représentable. Réciproquement, si \(2^{2m}\) est représentable, c'est une somme de termes distincts \(a_i\) avec \(i < 2m\), et \(a_{2m+2} = a_{2m+1} + a_{2m} + 2^{2m}\) montre que \(2m + 2\) est bon. \(\square\)
Le livret écrit « either of \(2m+1\) and \(2m+2\) is good » ; la preuve montre l'équivalence pour chacun des deux indices.
Lemme 2. Si \(k \geq 2\), alors \(2^{4k-2}\) est représentable si et seulement si \(2^{k+1}\) est représentable. En particulier, si \(s \geq 2\), \(4^s\) est représentable si et seulement si \(4^{4s-3}\) l'est ; de plus, \(4^{4s-3} > 4^s\).
Preuve. On a \(2^{4k-2} < a_{4k-2}\), donc une représentation de \(2^{4k-2}\) n'utilise que des \(a_i\) avec \(i \leq 4k - 3\). Or
Donc toute représentation de \(2^{4k-2}\) contient tous les termes de \(a_{2k}\) à \(a_{4k-3}\) (si l'un d'eux manque, la somme des autres est \(\leq (a_0 + \cdots + a_{4k-3}) - a_{2k} < 2^{4k-2}\)). Ainsi, si \(2^{4k-2}\) est représentable, \(2^{4k-2} - \sum_{i=2k}^{4k-3} a_i\) l'est aussi. Mais
Donc si \(2^{4k-2}\) est représentable, \(2^{k+1}\) l'est. Réciproquement, si \(2^{k+1}\) est représentable, comme \(2^{k+1} < 2^{2k} + 2^k = a_{2k}\), il s'écrit comme somme de termes distincts \(a_i\) avec \(i < 2k\). Alors \(2^{4k-2} = \sum_{i=2k}^{4k-3} a_i + 2^{k+1}\) s'écrit comme \(a_{4k-3} + a_{4k-4} + \cdots + a_{2k}\) plus une somme de termes distincts \(a_i\) avec \(i < 2k\), donc \(2^{4k-2}\) est représentable.
Pour le second énoncé, si \(s \geq 2\), on prend \(k = 2s - 1\) : alors \(2^{k+1} = 4^s\) et \(2^{4k-2} = 4^{4s-3}\). Enfin, \(s \geq 2\) entraîne \(4s - 3 > s\). \(\square\)
Conclusion. \(4^2 = a_2 + a_3\) est représentable, alors que \(4^6 = 4096\) ne l'est pas. En effet, \(4^6 = 2^{12} < a_{12}\), donc les seuls termes disponibles sont \(a_0, \ldots, a_{11}\), c'est-à-dire \(2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080\). Leur somme est \(S_{11} = 4221\), qui dépasse \(4096\) de \(125\). Toute représentation de \(4096\) doit donc contenir tous les termes supérieurs à \(125\), soit \(136, 272, 528, 1056, 2080\), de somme \(4072\). Comme \(4096 - 4072 = 24\) et que \(24\) n'est clairement pas représentable (avec \(2, 3, 6, 10, 20\)), \(4096\) ne l'est pas non plus.
En partant de ces deux valeurs et en itérant le lemme 2 (construction récursive \(s \mapsto 4s - 3\)), on obtient une infinité de puissances de \(4\) représentables et une infinité de non représentables. Le lemme 1 conclut. \(\blacksquare\)