Shortlist 2025, C3¶
Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : Islamic Republic of Iran
Concepts : Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2025 (avec solutions), section C3 (livret PDF)
Figures reprises du livret officiel de la Shortlist.
Énoncé¶
There are \(2025\) white balls and \(2025\) black balls arranged in a row. A balanced segment is a contiguous nonempty segment of balls that contains the same number of white balls as black balls. A balanced removal is the operation of selecting a balanced segment \(S\), removing all the balls in \(S\), and shifting left the balls that were to the right of \(S\) so that the remaining balls form a contiguous row.
Determine the smallest positive integer \(N\) satisfying the following property: for every configuration of balls and for every integer \(k\) satisfying \(0 \leq k \leq 2025\), there exists a sequence of at most \(N\) balanced removals after which there are exactly \(2k\) remaining balls.
Indices : les idées clés
- Segments équilibrés minimaux : on découpe la rangée en segments équilibrés minimaux ; on retire un préfixe formé de segments entiers, puis un morceau de la bonne longueur dans le segment minimal suivant.
- Continuité discrète (solution 1) : le nombre de boules noires dans une fenêtre glissante de longueur \(2l\) varie d'au plus \(1\) à chaque pas, et passe d'un côté à l'autre de \(l\) ; il prend donc la valeur \(l\).
- Récurrence et constructions récursives (solution 2) : preuve du lemme par récurrence sur la longueur, en retirant deux boules bien choisies.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2025 (deux solutions, qui diffèrent par la preuve du lemme, et une remarque).
Réponse : \(N = 2\).
Solution 1¶
\(N = 1\) ne suffit pas. Considérons une configuration dont les deux premières et les deux dernières boules sont blanches, par exemple deux boules blanches, puis les \(2025\) boules noires, puis les \(2023\) boules blanches restantes, et prenons \(k = 1\). Il n'y a que trois segments de \(2 \cdot 2024\) boules consécutives, et aucun n'est équilibré (chacun laisse deux boules blanches). On ne peut donc pas laisser exactement \(2\) boules avec une seule suppression équilibrée.
Deux suppressions suffisent. Un segment équilibré minimal est un segment équilibré qu'on ne peut pas découper en un segment équilibré suivi d'un autre segment équilibré.
Lemme. Si \(S\) est un segment équilibré minimal de \(2m\) boules, alors pour tout entier \(1 \leq l \leq m\), \(S\) contient un segment équilibré de longueur \(2l\).
Preuve. Pour \(0 \leq i \leq 2m\), soit \(a_i\) le nombre de boules noires moins le nombre de boules blanches parmi les \(i\) premières boules de \(S\). On a \(|a_i - a_{i+1}| = 1\), et \(a_i \neq 0\) pour \(1 \leq i \leq 2m - 1\) par minimalité ; donc les \(a_i\), \(1 \leq i \leq 2m - 1\), sont tous positifs ou tous négatifs.
Pour \(0 \leq i \leq 2(m - l)\), soit \(b_i\) le nombre de boules noires dans le segment allant de la \((i+1)\)-ième à la \((i + 2l)\)-ième boule de \(S\). On a \(|b_i - b_{i+1}| \leq 1\), et
Comme \(a_{2l}\) et \(a_{2(m-l)}\) ont le même signe, on a \(b_0 \geq l \geq b_{2(m-l)}\) ou \(b_0 \leq l \leq b_{2(m-l)}\). Dans les deux cas, il existe \(i\) avec \(b_i = l\) : le segment correspondant est équilibré de longueur \(2l\). \(\square\)
On découpe la rangée de \(4050\) boules en segments équilibrés minimaux : soient
tels que le segment allant de la \((2s_i + 1)\)-ième à la \((2s_{i+1})\)-ième boule soit un segment équilibré minimal pour tout \(0 \leq i \leq p - 1\). Soit \(0 \leq k \leq 2025\). Si \(s_i = 2025 - k\) pour un certain \(i\), on retire simplement les \(2(2025 - k)\) premières boules, qui forment un segment équilibré. Sinon, il existe \(i\) tel que
On applique le lemme au segment minimal \(S\) allant de la \((2s_i + 1)\)-ième à la \((2s_{i+1})\)-ième boule : il contient un segment équilibré \(S_1\) de longueur \(2(2025 - k - s_i)\), et les \(2s_i\) premières boules forment un segment équilibré \(S_2\) disjoint de \(S\). En retirant \(S_1\) puis \(S_2\), il reste \(2k\) boules. \(\blacksquare\)
Solution 2¶
Seule la preuve du lemme change.
Preuve du lemme. Avec les \(a_i\) définis comme ci-dessus, on prouve l'énoncé plus général : si \(S\) est équilibré et \(a_i \geq 0\) pour tout \(i\), alors \(S\) contient un segment équilibré de longueur \(2l\) pour tout \(1 \leq l \leq m\). (Un segment minimal vérifie \(a_i \geq 0\) pour tout \(i\), quitte à échanger les couleurs.)
On raisonne par récurrence sur \(m\). Pour \(m = 1\), on a \(l = 1\) et c'est clair. Soit \(m \geq 2\), l'énoncé étant vrai pour les valeurs plus petites. On a \(a_1 = a_{2m-1} = 1\), donc la première boule est noire et la dernière blanche.
Cas 1 : \(a_i \geq 1\) pour tout \(1 \leq i \leq 2m - 1\). Le segment \(T\) allant de la \(2\)e à la \((2m-1)\)-ième boule est équilibré de longueur \(2m - 2\), et ses sommes partielles \(a_i - 1\) sont positives ou nulles. Par hypothèse de récurrence, \(T\) contient un segment équilibré de longueur \(2l\) pour tout \(1 \leq l \leq m - 1\) ; pour \(l = m\), on prend \(S\) lui-même.
Cas 2 : \(a_i = 0\) pour un certain \(1 \leq i \leq 2m - 1\). Quitte à retourner \(S\) et à échanger les couleurs, on peut supposer \(i \leq m\). Si \(2l \leq 2m - i\), on applique l'hypothèse de récurrence au segment équilibré formé des \(2m - i\) dernières boules. Si \(2l > 2m - i\), on remarque que la \(i\)-ième boule est blanche et la \((i+1)\)-ième noire, car \(a_{i-1} = a_{i+1} = 1\). Soit \(T\) la suite obtenue en retirant de \(S\) ces deux boules. L'hypothèse de récurrence appliquée à \(T\) donne un segment équilibré \(T' \subseteq T\) de longueur \(2(l - 1)\) (on a \(2l > m \geq 2\), donc \(l \geq 2\)). Disons que \(T'\) va de la \(x\)-ième à la \((x + 2l - 3)\)-ième boule de \(T\). Alors \(x + 2l - 3 \leq 2m - 2\) donne
et \(x \geq 1\) donne
Ainsi \(T'\) « enjambe » l'emplacement des deux boules retirées, et \(T'\) augmenté de la \(i\)-ième et de la \((i+1)\)-ième boule de \(S\) forme un segment équilibré de longueur \(2l\) dans \(S\). \(\square\)
Le reste de la solution est identique. \(\blacksquare\)
Remarques¶
Remarque 1. Le lemme peut aussi se déduire du problème des « deux alpinistes » (article Mountain Climbing, Ladder Moving, and the Ring-Width of a Polygon de Goodman, Pach et Yap). Par le théorème des valeurs intermédiaires, il existe un instant où la distance entre les alpinistes vaut \(2l\). Si leurs coordonnées sont entières, c'est terminé ; sinon, on montre que les pentes sur lesquelles ils se trouvent sont parallèles (car \(2l\) est un entier pair), et on peut faire descendre simultanément les deux alpinistes jusqu'à des coordonnées entières.