Shortlist 2019, C7¶
Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : Czech Republic
Concepts : Jeux et stratégies gagnantes
Solution officielle : Shortlist officielle 2019 (avec solutions), section C7 (livret PDF)
Énoncé¶
There are \(60\) empty boxes \(B_1, \ldots, B_{60}\) in a row on a table and an unlimited supply of pebbles. Given a positive integer \(n\), Alice and Bob play the following game.
In the first round, Alice takes \(n\) pebbles and distributes them into the \(60\) boxes as she wishes. Each subsequent round consists of two steps:
(a) Bob chooses an integer \(k\) with \(1 \leq k \leq 59\) and splits the boxes into the two groups \(B_1, \ldots, B_k\) and \(B_{k+1}, \ldots, B_{60}\).
(b) Alice picks one of these two groups, adds one pebble to each box in that group, and removes one pebble from each box in the other group.
Bob wins if, at the end of any round, some box contains no pebbles. Find the smallest \(n\) such that Alice can prevent Bob from winning.
Indices : les idées clés
- Jeux et stratégies gagnantes : il faut à la fois une stratégie pour Alice avec \(M\) cailloux et une stratégie pour Bob contre toute configuration d'au plus \(M - 1\) cailloux.
- Configurations en V : \(V_i\) met \(1 + |j - i|\) cailloux dans la boîte \(B_j\) ; la plus économique, \(V_{\lceil N/2 \rceil}\), contient exactement \(M\) cailloux.
- Domination : si Bob gagne contre une configuration, il gagne contre toute configuration qu'elle domine ; d'où l'observation A, qui permet de supposer qu'Alice choisit toujours le même côté.
- Alterner les réponses (solution 2, Alice) : pour chaque coupe, Alice alterne gauche et droite, si bien que chaque boîte perd au plus un caillou par coupe possible.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2019 (deux stratégies pour Alice et trois pour Bob, numérotées comme dans le livret : solutions 1 et 2 pour Alice, solutions 1, 2 et 3 pour Bob).
Réponse : \(n = 960\). Plus généralement, avec \(N > 1\) boîtes, la réponse est \(n = \left\lfloor \frac N2 + 1 \right\rfloor \left\lceil \frac N2 + 1 \right\rceil - 1\).
Remarques communes. On traite le cas général de \(N > 1\) boîtes, et on note \(M = \left\lfloor \frac N2 + 1 \right\rfloor \left\lceil \frac N2 + 1 \right\rceil - 1\) la réponse annoncée (pour \(N = 60\), \(M = 31 \cdot 31 - 1 = 960\)). Pour \(1 \leq k < N\), Bob fait un \(k\)-coup s'il sépare les boîtes en un groupe gauche \(\{B_1, \ldots, B_k\}\) et un groupe droit \(\{B_{k+1}, \ldots, B_N\}\). Une configuration en domine une autre si elle a au moins autant de cailloux dans chaque boîte, et la domine strictement si elle en a en plus strictement plus dans au moins une boîte. (Si Bob gagne dans une configuration, il gagne aussi dans toute configuration qu'elle domine.)
On utilise des configurations « en V » : pour \(1 \leq i \leq N\), \(V_i\) est la configuration où \(B_j\) contient \(1 + |j - i|\) cailloux (la \(i\)-ième boîte en a un seul, et le nombre augmente de un dans chaque direction ; la première boîte en a \(i\), la dernière \(N + 1 - i\)). \(V_i\) contient \(\frac12 i(i+1) + \frac12(N+1-i)(N+2-i) - 1\) cailloux ; pour \(i = \lceil N/2 \rceil\), ce nombre vaut \(M\).
Les solutions se découpent naturellement en une stratégie pour Alice (avec \(M\) cailloux, elle empêche Bob de gagner) et une stratégie pour Bob (il gagne contre toute configuration initiale d'au plus \(M - 1\) cailloux). L'observation suivante simplifie l'étude des stratégies de Bob.
Observation A. Considérons deux tours consécutifs. Si au premier Bob fait un \(k\)-coup et Alice choisit le groupe gauche, puis au second Bob fait un \(\ell\)-coup avec \(\ell > k\), on peut supposer sans perte de généralité qu'Alice choisit encore le groupe gauche.
Preuve. Si Alice choisit le groupe droit au second tour, l'effet combiné des deux tours est que chacune des boîtes \(B_{k+1}, \ldots, B_\ell\) perd deux cailloux (les autres boîtes sont inchangées). La configuration obtenue est strictement dominée par celle d'avant le premier tour, et il suffit d'étudier l'autre réponse d'Alice. \(\square\)
Solution 1 (Alice)¶
Alice place initialement les cailloux selon \(V_{\lceil N/2 \rceil}\). Supposons que la configuration courante domine \(V_i\). Si Bob fait un \(k\)-coup avec \(k \geq i\), Alice choisit le groupe gauche, ce qui donne une configuration dominant \(V_{i+1}\). Si Bob fait un \(k\)-coup avec \(k < i\), Alice choisit le groupe droit, ce qui donne une configuration dominant \(V_{i-1}\). Comme aucune des configurations \(V_1, \ldots, V_N\) n'a de boîte vide, Alice empêche Bob de gagner. \(\blacksquare\)
Solution 1 (Bob)¶
L'idée clé est l'affirmation suivante.
Affirmation. S'il existe un entier \(k \geq 1\) et au moins \(2k\) boîtes contenant chacune au plus \(k\) cailloux, Bob peut forcer la victoire.
Preuve. On ignore les autres boîtes. Bob commence par un \(k\)-coup (qui sépare les \(2k\) boîtes en deux groupes de \(k\)). Sans perte de généralité, Alice choisit le groupe gauche. Bob fait ensuite un \((k+1)\)-coup, ..., un \((2k-1)\)-coup (toujours relativement aux \(2k\) boîtes). D'après l'observation A, on peut supposer qu'Alice choisit toujours le groupe gauche. Après le \((2k-1)\)-coup, la boîte la plus à droite a perdu \(k\) cailloux : elle est vide et Bob gagne. \(\square\)
Montrons que si \(n < M\), alors soit il y a déjà une boîte vide, soit il existe \(k \geq 1\) et \(2k\) boîtes contenant chacune au plus \(k\) cailloux (et Bob gagne). Sinon, chaque boîte contient au moins \(1\) caillou, et pour chaque \(1 \leq k \leq \lfloor N/2 \rfloor\), au moins \(N - (2k - 1) = N + 1 - 2k\) boîtes contiennent au moins \(k + 1\) cailloux. En sommant, il y a au total au moins autant de cailloux que dans \(V_{\lceil N/2 \rceil}\), c'est-à-dire au moins \(M\), contradiction. \(\blacksquare\)
Solution 2 (Alice)¶
Soit \(K = \lfloor N/2 + 1 \rfloor\). Alice part de la configuration \(V_K\). Pour chacun des \(N - 1\) coups possibles de Bob, considérons les tours où il joue ce coup. Sur ces tours, Alice alterne entre le groupe gauche et le groupe droit ; la première fois que Bob joue ce coup, Alice choisit le groupe contenant la \(K\)-ième boîte.
Ainsi, à tout moment, le nombre de cailloux dans chaque boîte ne dépend que de l'ensemble des coups que Bob a joués un nombre impair de fois. Le nombre de cailloux d'une boîte peut donc diminuer au plus du nombre de coups pour lesquels Alice commencerait par retirer un caillou du groupe contenant cette boîte. Ces nombres sont, boîte par boîte,
Ils sont, boîte par boîte, strictement inférieurs aux nombres initiaux de cailloux (\(1 + |j - K|\) pour la boîte \(B_j\)), donc aucune boîte ne se vide avec cette stratégie. \(\blacksquare\)
Solution 2 (Bob)¶
Soit \(K = \lfloor N/2 + 1 \rfloor\). On considère une configuration \(X\) d'au plus \(M - 1\) cailloux et on utilise l'observation A. Considérons deux configurations à \(M\) cailloux : \(V_K\) et \(V_{N+1-K}\) (si \(N\) est impair, c'est la même ; si \(N\) est pair, l'une est le reflet de l'autre). (Le livret écrit « si \(n\) est impair » ; il faut lire \(N\).) La configuration \(X\) a moins de cailloux que \(V_K\) dans au moins une boîte, et moins que \(V_{N+1-K}\) dans au moins une boîte.
Premier cas. Supposons que, par rapport à l'une de ces configurations (disons \(V_K\)), \(X\) a moins de cailloux dans une des boîtes de la moitié où \(V_K\) en a \(1, 2, \ldots, \lceil N/2 \rceil\) (la moitié droite de \(V_K\) si \(N\) est pair ; si \(N\) est impair, on peut supposer que c'est la moitié droite, la configuration étant symétrique). Ce ne peut pas être la boîte où \(V_K\) a \(1\) caillou, sinon elle serait vide. Bob fait alors un \(K\)-coup. Si Alice choisit le groupe droit, le nombre total de cailloux diminue et Bob recommence sa stratégie avec moins de cailloux. Si Alice choisit le groupe gauche, Bob enchaîne avec un \((K+1)\)-coup, un \((K+2)\)-coup, etc. ; d'après l'observation A, on peut supposer qu'Alice choisit toujours le groupe gauche. Mais alors la boîte de la moitié droite qui avait moins de cailloux dans \(X\) que dans \(V_K\) finit par se vider au cours de cette suite de coups.
Second cas. Sinon, \(N\) est pair et, pour chacune des deux configurations, \(X\) n'a moins de cailloux que du côté où elle en a \(2, 3, \ldots, \frac N2 + 1\). Autrement dit, les nombres de cailloux de \(X\) sont au moins
avec égalité au moins une fois de chaque côté. Bob fait un \(\frac N2\)-coup. Quel que soit le groupe choisi par Alice, le total de cailloux ne change pas, et le côté qui perd des cailloux contient maintenant une boîte ayant moins de cailloux que dans (C) ; on applique alors le premier cas. \(\blacksquare\)
Solution 3 (Bob)¶
Pour une configuration \(C\), soit \(L(C)\) le plus grand entier tel que, pour tout \(0 \leq i \leq N - 1\), la boîte \(B_{i+1}\) contient au moins \(L(C) - i\) cailloux. De même, soit \(R(C)\) le plus grand entier tel que, pour tout \(0 \leq i \leq N - 1\), la boîte \(B_{N-i}\) contient au moins \(R(C) - i\) cailloux. (Ainsi \(C\) domine la « moitié gauche » de \(V_{L(C)}\) et la « moitié droite » de \(V_{N+1-R(C)}\).) Alors \(C\) domine une configuration en V si et seulement si \(L(C) + R(C) \geq N + 1\). Si \(C\) domine une configuration en V, elle contient au moins \(M\) cailloux.
Supposons qu'il y ait moins de \(M\) cailloux, donc \(L(C) + R(C) \leq N\). Bob fait un \(L(C)\)-coup (ou plus généralement tout coup laissant au moins \(L(C)\) boîtes à gauche et au moins \(R(C)\) boîtes à droite). Soit \(C'\) la nouvelle configuration ; supposons qu'aucune boîte ne soit vide (sinon Bob a gagné). Si Alice choisit le groupe gauche, \(L(C') = L(C) + 1\) et \(R(C') = R(C) - 1\) ; sinon, \(L(C') = L(C) - 1\) et \(R(C') = R(C) + 1\). Dans les deux cas, \(L(C') + R(C') \leq N\).
Bob répète cette stratégie jusqu'à ce qu'une boîte se vide. Comme la condition de l'observation A est vérifiée, on peut supposer qu'Alice choisit toujours un groupe du même côté. Alors l'une des quantités \(L\), \(R\) décroît strictement ; disons \(L\). On finit par atteindre \(L = 1\). Si \(B_2\) n'est pas vide, alors \(B_1\) contient un seul caillou. Bob fait un \(1\)-coup et, d'après l'observation A, Alice doit (tôt ou tard) choisir le groupe droit, ce qui vide cette boîte. \(\blacksquare\)