Shortlist 2022, C1¶
Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : Czech Republic
Concepts : Récurrence et constructions récursives · Principe extrémal
Solution officielle : Shortlist officielle 2022 (avec solutions), p. 24 (page 26 du PDF)
Énoncé¶
A \(\pm 1\)-sequence is a sequence of \(2022\) numbers \(a_1, \ldots, a_{2022}\), each equal to either \(+1\) or \(-1\). Determine the largest \(C\) so that, for any \(\pm 1\)-sequence, there exists an integer \(k\) and indices \(1 \leq t_1 < \cdots < t_k \leq 2022\) so that \(t_{i+1} - t_i \leq 2\) for all \(i\), and
Indices : les idées clés
- Algorithme glouton : on garde tous les termes du signe majoritaire, et on ne garde un terme de l'autre signe que lorsqu'on ne peut pas le sauter.
- Compter par paires : chaque \(-1\) conservé est précédé d'un \(-1\) sauté, d'où au plus \(\lfloor 1011/2 \rfloor = 505\) termes \(-1\) conservés.
- Construction d'un contre-exemple par blocs \(\{-1\}, \{+1, +1\}, \{-1, -1\}, \ldots, \{+1\}\) : entre deux blocs de \(+1\) utilisés, on doit traverser un bloc de \(-1\) de longueur \(2\).
- Principe extrémal : le cas limite \(k = 506\) (tous les blocs de \(+1\) utilisés) est traité à part grâce au bloc d'extrémité, de taille \(1\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2022 (une solution et une remarque).
Réponse : \(C = 506\).
Solution 1¶
Appelons admissible une sous-suite \(a_{t_1}, \ldots, a_{t_k}\) avec \(t_{i+1} - t_i \leq 2\) pour tout \(i\).
On peut toujours atteindre \(506\). Quitte à changer tous les signes, supposons qu'au moins \(\frac{2022}{2} = 1011\) termes valent \(+1\). Construisons une sous-suite de la façon suivante, en parcourant les indices \(t\) dans l'ordre : si \(a_t = +1\), on inclut toujours \(a_t\) ; si \(a_t = -1\), on le saute si c'est possible (c'est-à-dire si l'on a inclus \(a_{t-1}\), ou si \(t\) est le premier indice), et sinon on l'inclut par nécessité ; puis on passe à l'indice suivant. Cette sous-suite est admissible et contient tous les \(+1\). De plus, chaque \(-1\) inclus est immédiatement précédé d'un \(-1\) sauté ; ces paires (sauté, inclus) sont disjointes, et il y a au plus \(1011\) termes égaux à \(-1\), donc au plus \(\left\lfloor \frac{1011}{2} \right\rfloor = 505\) termes \(-1\) sont inclus. La somme est donc au moins \(1011 - 505 = 506\).
On ne peut pas toujours faire mieux. Considérons la suite
découpée en blocs (les accolades). Il y a \(1012\) blocs : \(506\) contiennent des \(+1\) et \(506\) contiennent des \(-1\) (les deux blocs des extrémités contiennent un seul terme, les autres deux termes). Montrons que toute sous-suite admissible a une somme comprise entre \(-506\) et \(506\).
Supposons qu'une sous-suite admissible utilise des termes de \(k\) blocs de \(+1\). Ces blocs sont consécutifs parmi les blocs de \(+1\), et entre deux d'entre eux se trouve un bloc de deux \(-1\) ; comme on ne peut pas sauter deux termes consécutifs, la sous-suite inclut au moins un \(-1\) de chacun de ces \(k - 1\) blocs. Elle inclut au plus deux \(+1\) par bloc de \(+1\). Sa somme est donc au plus \(2k - (k - 1) = k + 1\).
- Si \(k < 506\), cela fait au plus \(506\).
- Si \(k = 506\), la sous-suite utilise tous les blocs de \(+1\), dont celui de l'extrémité droite qui ne contient qu'un \(+1\) : la somme est alors au plus \(k = 506\), et non \(k + 1\).
Donc toute sous-suite admissible a une somme \(\sum_i a_{t_i} \leq 506\). De façon analogue (le bloc d'extrémité gauche \(\{-1\}\) joue le même rôle), \(\sum_i a_{t_i} \geq -506\). Ainsi \(C \leq 506\), et finalement \(C = 506\). \(\blacksquare\)
Remarques¶
Remarque 1 (reformulation). On peut reformuler le problème ainsi : \(2022\) seaux d'eau sont alignés, chacun colorié en rouge ou en bleu. Sally le saumon choisit un seau de départ, puis, autant de fois qu'elle veut, saute soit dans le seau suivant, soit par-dessus celui-ci dans le seau d'après (jamais par-dessus plus d'un seau). Elle s'arrête quand elle veut ; son score est la valeur absolue de la différence entre le nombre de seaux rouges et de seaux bleus visités. Déterminer le plus grand \(C\) tel que, quelle que soit la coloration, Sally puisse obtenir un score d'au moins \(C\).