Shortlist 2014, N1

Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : Serbia

Concepts : Récurrence et constructions récursives · Principe extrémal · Congruences, théorèmes de Fermat et d'Euler

Solution officielle : Shortlist officielle 2014 (avec solutions), p. 68 (page 69 du PDF)

Énoncé

Let \(n \geq 2\) be an integer, and let \(A_n\) be the set

\[A_n = \{2^n - 2^k \mid k \in \mathbb{Z}, \; 0 \leq k < n\}.\]

Determine the largest positive integer that cannot be written as the sum of one or more (not necessarily distinct) elements of \(A_n\).

Indices : les idées clés

• Récurrence sur \(n\) : si \(m\) est pair, on représente \(\frac{m}{2}\) avec \(A_{n-1}\) et l'on double ; si \(m\) est impair, on fait de même avec \(\frac{m - (2^n - 1)}{2}\).
• Principe extrémal : le plus petit \(N \equiv 1 \pmod{2^n}\) représentable n'a pas deux termes égaux (sinon on fabrique \(N - 2^n\)).
• Congruences modulo \(2^n\) : les \(2^{k_i}\) distincts doivent sommer à \(2^n - 1\), ce qui force \(N = (n - 1)2^n + 1\) ; plus généralement, \(s 2^n - t\) est représentable si et seulement si \(s \geq \sigma_2(t)\) (solution 3).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2014 (trois solutions).

Réponse : \((n - 2)2^n + 1\).

Solution 1

Partie I. Montrons d'abord que tout entier strictement supérieur à \((n - 2)2^n + 1\) peut s'écrire comme une telle somme, par récurrence sur \(n\).

Pour \(n = 2\), l'ensemble \(A_2\) est formé des deux éléments \(2\) et \(3\). Tout entier \(m \geq 2\) est alors une somme d'éléments de \(A_2\) : \(m = 2 + 2 + \cdots + 2\) si \(m\) est pair, et \(m = 3 + 2 + 2 + \cdots + 2\) si \(m\) est impair.

Soit maintenant \(n > 2\) et \(m > (n - 2)2^n + 1\) un entier. Si \(m\) est pair, considérons

\[\frac{m}{2} \geq \frac{(n - 2)2^n + 2}{2} = (n - 2)2^{n-1} + 1 > (n - 3)2^{n-1} + 1.\]

Par hypothèse de récurrence, il existe une écriture

\[\frac{m}{2} = (2^{n-1} - 2^{k_1}) + (2^{n-1} - 2^{k_2}) + \cdots + (2^{n-1} - 2^{k_r})\]

avec \(0 \leq k_i < n - 1\). On en déduit

\[m = (2^n - 2^{k_1 + 1}) + (2^n - 2^{k_2 + 1}) + \cdots + (2^n - 2^{k_r + 1}),\]

qui est l'écriture voulue comme somme d'éléments de \(A_n\). Si \(m\) est impair, considérons

\[\frac{m - (2^n - 1)}{2} > \frac{(n - 2)2^n + 1 - (2^n - 1)}{2} = (n - 3)2^{n-1} + 1.\]

Par hypothèse de récurrence, il existe une écriture

\[\frac{m - (2^n - 1)}{2} = (2^{n-1} - 2^{k_1}) + (2^{n-1} - 2^{k_2}) + \cdots + (2^{n-1} - 2^{k_r})\]

avec \(0 \leq k_i < n - 1\). On en déduit

\[m = (2^n - 2^{k_1 + 1}) + (2^n - 2^{k_2 + 1}) + \cdots + (2^n - 2^{k_r + 1}) + (2^n - 1),\]

ce qui donne à nouveau une écriture de \(m\).

Partie II. Il reste à montrer que \((n - 2)2^n + 1\) n'a pas d'écriture. Soit \(N\) le plus petit entier strictement positif qui vérifie \(N \equiv 1 \pmod{2^n}\) et qui est une somme d'éléments de \(A_n\). Considérons une écriture de \(N\) :

\[N = (2^n - 2^{k_1}) + (2^n - 2^{k_2}) + \cdots + (2^n - 2^{k_r}), \tag{1}\]

où \(0 \leq k_1, k_2, \ldots, k_r < n\). Supposons d'abord que deux termes de la somme soient égaux, c'est-à-dire \(k_i = k_j\) pour certains \(i \neq j\). Si \(k_i = k_j = n - 1\), on peut simplement retirer ces deux termes et obtenir une écriture de

\[N - 2(2^n - 2^{n-1}) = N - 2^n\]

comme somme d'éléments de \(A_n\), ce qui contredit le choix de \(N\). Si \(k_i = k_j = k < n - 1\), on remplace les deux termes par \(2^n - 2^{k+1}\), qui est aussi un élément de \(A_n\), et l'on obtient une écriture de

\[N - 2(2^n - 2^k) + 2^n - 2^{k+1} = N - 2^n,\]

encore une contradiction. Donc tous les \(k_i\) sont distincts, ce qui implique

\[2^{k_1} + 2^{k_2} + \cdots + 2^{k_r} \leq 2^0 + 2^1 + 2^2 + \cdots + 2^{n-1} = 2^n - 1.\]

D'autre part, en réduisant (1) modulo \(2^n\), on trouve

\[2^{k_1} + 2^{k_2} + \cdots + 2^{k_r} \equiv -N \equiv -1 \pmod{2^n}.\]

On a donc \(2^{k_1} + 2^{k_2} + \cdots + 2^{k_r} = 2^n - 1\), ce qui n'est possible que si chaque élément de \(\{0, 1, \ldots, n - 1\}\) apparaît parmi les \(k_i\). Cela donne

\[N = n 2^n - (2^0 + 2^1 + \cdots + 2^{n-1}) = (n - 1)2^n + 1.\]

En particulier, \((n - 2)2^n + 1\) n'est pas une somme d'éléments de \(A_n\). \(\blacksquare\)

Solution 2

On peut aussi montrer autrement que \(m = (n - 2)2^n + 1\) n'est pas une somme d'éléments de \(A_n\). On prouve par récurrence sur \(n\) l'énoncé suivant.

Affirmation. Si \(a\), \(b\) sont des entiers avec \(a \geq 0\), \(b \geq 1\) et \(a + b < n\), alors \(a 2^n + b\) n'est pas une somme d'éléments de \(A_n\).

Preuve. L'affirmation est vraie pour \(n = 2\) (la seule possibilité est \(a = 0\), \(b = 1\)). Pour \(n > 2\), supposons qu'il existe des entiers \(a\), \(b\) avec \(a \geq 0\), \(b \geq 1\) et \(a + b < n\), et des éléments \(m_1, m_2, \ldots, m_r\) de \(A_n\) tels que

\[a 2^n + b = m_1 + m_2 + \cdots + m_r.\]

On peut supposer \(m_1 \geq m_2 \geq \cdots \geq m_r\). Soit \(\ell\) le plus grand indice tel que \(m_\ell = 2^n - 1\) (\(\ell = 0\) si \(m_1 \neq 2^n - 1\)). Clairement, \(\ell\) et \(b\) ont la même parité. Alors

\[(a - \ell)2^n + (b + \ell) = m_{\ell + 1} + m_{\ell + 2} + \cdots + m_r,\]

donc

\[(a - \ell)2^{n-1} + \frac{b + \ell}{2} = \frac{m_{\ell+1}}{2} + \frac{m_{\ell+2}}{2} + \cdots + \frac{m_r}{2}.\]

Les nombres \(\frac{m_{\ell+1}}{2}, \frac{m_{\ell+2}}{2}, \ldots, \frac{m_r}{2}\) sont des éléments de \(A_{n-1}\). De plus, \(a - \ell\) et \(\frac{b + \ell}{2}\) sont des entiers, et \(\frac{b + \ell}{2} \geq 1\). Si \(a - \ell\) était négatif, on aurait

\[a 2^n + b \geq \ell(2^n - 1) \geq (a + 1)(2^n - 1) = a 2^n + 2^n - a - 1,\]

donc \(n \geq a + b + 1 \geq 2^n\), ce qui est impossible. Donc \(a - \ell \geq 0\). Par hypothèse de récurrence, on doit avoir \(a - \ell + \frac{b + \ell}{2} \geq n - 1\), ce qui est contradictoire, puisque

\[a - \ell + \frac{b + \ell}{2} \leq a - \ell + b + \ell - 1 = a + b - 1 < n - 1. \qquad \square\]

Le cas particulier \(a = n - 2\), \(b = 1\) achève la preuve. \(\blacksquare\)

Solution 3

Notons \(B_n\) l'ensemble des entiers strictement positifs qui sont des sommes d'éléments de \(A_n\). Dans cette solution, on décrit explicitement tous les éléments de \(B_n\), par un argument proche de la première solution.

Pour un entier \(n \geq 1\), on note \(\sigma_2(n)\) la somme de ses chiffres en base \(2\). Tout entier \(m \geq 1\) s'écrit de manière unique \(m = s 2^n - t\) avec \(s \geq 1\) entier et \(0 \leq t \leq 2^n - 1\).

Lemme. Pour deux entiers \(s \geq 1\) et \(0 \leq t \leq 2^n - 1\), le nombre \(m = s 2^n - t\) est dans \(B_n\) si et seulement si \(s \geq \sigma_2(t)\).

Preuve. Pour \(t = 0\), l'énoncé est évident, car \(m = 2s \cdot (2^n - 2^{n-1})\).

Supposons maintenant \(t \geq 1\), et soit

\[t = 2^{k_1} + \cdots + 2^{k_\sigma} \qquad (0 \leq k_1 < \cdots < k_\sigma \leq n - 1, \; \sigma = \sigma_2(t))\]

son écriture binaire. Si \(s \geq \sigma\), alors \(m \in B_n\) puisque

\[m = (s - \sigma)2^n + (\sigma 2^n - t) = 2(s - \sigma) \cdot (2^n - 2^{n-1}) + \sum_{i=1}^{\sigma} (2^n - 2^{k_i}).\]

Supposons maintenant qu'il existe des entiers \(s\) et \(t\) avec \(1 \leq s < \sigma_2(t)\) et \(0 \leq t \leq 2^n - 1\) tels que \(m = s 2^n - t\) soit dans \(B_n\). Parmi tous ces cas, choisissons celui pour lequel \(m\) est minimal, et soit

\[m = \sum_{i=1}^{d} (2^n - 2^{\ell_i}) \qquad (0 \leq \ell_i \leq n - 1)\]

l'écriture correspondante. Si tous les \(\ell_i\) sont distincts, alors \(\sum_{i=1}^{d} 2^{\ell_i} \leq \sum_{j=0}^{n-1} 2^j = 2^n - 1\), donc \(s = d\) et \(t = \sum_{i=1}^{d} 2^{\ell_i}\), d'où \(s = d = \sigma_2(t)\), ce qui est impossible. Deux des \(\ell_i\) sont donc égaux, disons \(\ell_{d-1} = \ell_d\). Alors \(m \geq 2(2^n - 2^{\ell_d}) \geq 2^n\), donc \(s \geq 2\).

On affirme que le nombre \(m' = m - 2^n = (s - 1)2^n - t\) est lui aussi dans \(B_n\), ce qui contredit la minimalité. En effet,

\[(2^n - 2^{\ell_{d-1}}) + (2^n - 2^{\ell_d}) = 2(2^n - 2^{\ell_d}) = 2^n + (2^n - 2^{\ell_d + 1}),\]

donc

\[m' = \sum_{i=1}^{d-2} (2^n - 2^{\ell_i}) + (2^n - 2^{\ell_d + 1})\]

est l'écriture voulue de \(m'\) (si \(\ell_d = n - 1\), le dernier terme est simplement omis). Cette contradiction achève la preuve. \(\square\)

D'après le lemme, le plus grand nombre \(M\) qui n'est pas dans \(B_n\) est de la forme

\[m_t = (\sigma_2(t) - 1)2^n - t\]

pour un \(t\) avec \(1 \leq t \leq 2^n - 1\), et \(M\) est le plus grand de ces nombres. Pour \(t_0 = 2^n - 1\), on a \(m_{t_0} = (n - 1)2^n - (2^n - 1) = (n - 2)2^n + 1\) ; pour toute autre valeur de \(t\), on a \(\sigma_2(t) \leq n - 1\), donc \(m_t \leq (\sigma_2(t) - 1)2^n \leq (n - 2)2^n < m_{t_0}\). Donc \(M = m_{t_0} = (n - 2)2^n + 1\). \(\blacksquare\)