Shortlist 2023, C2¶
Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : Czech Republic
Concepts : Récurrence et constructions récursives · Principe des tiroirs
Solution officielle : Shortlist officielle 2023 (avec solutions), p. 36 (page 38 du PDF)
Énoncé¶
Determine the maximal length \(L\) of a sequence \(a_1, \ldots, a_L\) of positive integers satisfying both the following properties:
- every term in the sequence is less than or equal to \(2^{2023}\), and
-
there does not exist a consecutive subsequence \(a_i, a_{i+1}, \ldots, a_j\) (where \(1 \leq i \leq j \leq L\)) with a choice of signs \(s_i, s_{i+1}, \ldots, s_j \in \{1, -1\}\) for which
\[s_i a_i + s_{i+1} a_{i+1} + \cdots + s_j a_j = 0.\]
Indices : les idées clés
- Généraliser : on remplace \(2^{2023}\) par \(n = 2^k\) et on montre que la réponse est \(2n - 1 = 2^{k+1} - 1\).
- Construction avec les valuations \(2\)-adiques : \(a_i = 2^{k - v_2(i)}\) ; dans tout intervalle d'entiers, un seul a la valuation maximale, donc une somme signée ne peut pas s'annuler.
- Récurrence et constructions récursives : on choisit les signes un par un (glouton) pour garder les sommes partielles dans \([-n+1, n]\).
- Principe des tiroirs : \(2n + 1\) sommes partielles dans un intervalle de \(2n\) entiers : deux sont égales.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2023 (une solution et une remarque).
Réponse : \(L = 2^{2024} - 1\).
Solution 1¶
On montre plus généralement que la réponse est \(2^{k+1} - 1\) lorsque \(2^{2023}\) est remplacé par \(2^k\), pour un entier \(k \geq 1\) quelconque. Posons \(n = 2^k\).
Construction d'une suite de longueur \(2n - 1\). Pour un entier \(x \geq 1\), notons \(v_2(x)\) le plus grand entier \(v \geq 0\) tel que \(2^v \mid x\). Considérons la suite \(a_1, \ldots, a_{2n-1}\) définie par
Par exemple, pour \(k = 2\) et \(n = 4\), c'est la suite \(4, 2, 4, 1, 4, 2, 4\). Ce sont bien des entiers positifs inférieurs ou égaux à \(n = 2^k\), car \(0 \leq v_2(i) \leq k\) pour \(1 \leq i \leq 2^{k+1} - 1\).
Affirmation 1. La suite \(a_1, \ldots, a_{2n-1}\) n'a aucune sous-suite de termes consécutifs admettant un choix de signes de somme nulle.
Preuve. Soient \(1 \leq i \leq j \leq 2n - 1\). L'observation principale est que, parmi les entiers \(i, i+1, \ldots, j\), il en existe un unique \(x\) pour lequel \(v_2(x)\) est maximal. En effet, posons \(v = \max(v_2(i), \ldots, v_2(j))\). S'il y avait au moins deux multiples de \(2^v\) parmi \(i, \ldots, j\), deux multiples consécutifs de \(2^v\) y figureraient, et l'un d'eux serait multiple de \(2^{v+1}\) : contradiction.
Il y a donc exactement un \(x\) avec \(i \leq x \leq j\) et \(v_2(x) = v\). Ainsi, dans la suite \(a_i, a_{i+1}, \ldots, a_j\), tous les termes sauf \(a_x = 2^{k-v}\) sont multiples de \(2^{k-v+1}\). Il en est de même pour \(s_i a_i, \ldots, s_j a_j\) : la somme est congrue à \(\pm 2^{k-v}\) modulo \(2^{k-v+1}\), donc ne peut pas être nulle. \(\square\)
Il n'existe pas de suite de longueur \(L \geq 2n\). Soit \(a_1, \ldots, a_L\) une suite quelconque d'entiers positifs inférieurs ou égaux à \(n\), avec \(L \geq 2n\). On définit récursivement une suite de signes \(s_1, \ldots, s_L\) :
- si \(s_1 a_1 + \cdots + s_{i-1} a_{i-1} \leq 0\), on pose \(s_i = +1\) ;
- si \(s_1 a_1 + \cdots + s_{i-1} a_{i-1} \geq 1\), on pose \(s_i = -1\).
Posons \(b_i = \sum_{j=1}^{i} s_j a_j = s_1 a_1 + \cdots + s_i a_i\), et considérons la suite \(0 = b_0, b_1, b_2, \ldots, b_L\).
Affirmation 2. Tous les termes vérifient \(-n + 1 \leq b_i \leq n\).
Preuve. Par récurrence sur \(i\). C'est clair pour \(b_0 = 0\). Supposons \(-n + 1 \leq b_{i-1} \leq n\).
-
Cas 1 : \(-n + 1 \leq b_{i-1} \leq 0\). Alors \(b_i = b_{i-1} + a_i\) par définition de \(s_i\), donc
\[-n + 1 \leq b_{i-1} < b_{i-1} + a_i \leq b_{i-1} + n \leq n.\] -
Cas 2 : \(1 \leq b_{i-1} \leq n\). Alors \(b_i = b_{i-1} - a_i\), donc
\[-n + 1 \leq b_{i-1} - n \leq b_{i-1} - a_i < b_{i-1} \leq n.\]
Cela termine la preuve. \(\square\)
L'intervalle fermé \([-n+1, n]\) contient \(2n\) entiers, et la suite \(b_0, b_1, \ldots, b_L\) a au moins \(2n + 1\) termes (car \(L + 1 \geq 2n + 1\)). Par le principe des tiroirs, deux termes distincts \(b_{i-1}\) et \(b_j\) (avec \(1 \leq i \leq j \leq L\)) sont égaux. En les soustrayant :
ce qui est interdit. Donc \(L \leq 2n - 1\), et pour \(k = 2023\) la longueur maximale est \(L = 2^{2024} - 1\). \(\blacksquare\)
Remarques¶
Remarque 1. Le même argument donne la borne \(L \leq 2n - 1\) pour tout \(n\) (pas seulement les puissances de \(2\)), mais elle n'est pas forcément optimale lorsque \(n\) n'est pas une puissance de \(2\). Par exemple, pour \(n = 3\), la plus longue suite a pour longueur \(L = 3\).