Shortlist 2022, C3¶
Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : Colombia
Concepts : Coloriages et pavages · Jeux et stratégies gagnantes · Principe des tiroirs
Solution officielle : Shortlist officielle 2022 (avec solutions), p. 26 (page 28 du PDF)
Énoncé¶
In each square of a garden shaped like a \(2022 \times 2022\) board, there is initially a tree of height \(0\). A gardener and a lumberjack alternate turns playing the following game, with the gardener taking the first turn:
- The gardener chooses a square in the garden. Each tree on that square and all the surrounding squares (of which there are at most eight) then becomes one unit taller.
- The lumberjack then chooses four different squares on the board. Each tree of positive height on those squares then becomes one unit shorter.
We say that a tree is majestic if its height is at least \(10^6\). Determine the largest number \(K\) such that the gardener can ensure there are eventually \(K\) majestic trees on the board, no matter how the lumberjack plays.
Indices : les idées clés
- Réponse : \(K = 5 \cdot \frac{2022^2}{9} = 2271380\) ; plus généralement \(K = 5N^2\) pour un plateau \(3N \times 3N\).
- Coloriages et pavages : on colorie les cases dont une coordonnée est multiple de \(3\) ; tout carré \(3 \times 3\) contient exactement \(5\) cases coloriées, donc au plus \(4\) cases non coloriées que le bûcheron peut couper.
- Jeux et stratégies gagnantes : on donne une stratégie à chaque joueur, et on rend le jeu plus difficile pour le jardinier pour simplifier l'analyse.
- Principe des tiroirs : si le jardinier joue \(M\ell\) fois sur un même sous-plateau, l'une des \(M = \binom{9}{5}\) « cartes » est choisie au moins \(\ell\) fois.
- Jouer des nombres de coups qui décroissent géométriquement : \(10^6 M (M+1)^b\) coups sur le sous-plateau \(b\) compensent toutes les coupes ultérieures.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2022 (une solution).
Solution¶
Réponse : \(K = 5 \cdot \dfrac{2022^2}{9} = 2271380\). Plus généralement, pour un plateau \(3N \times 3N\), \(K = 5N^2\).
On traite un plateau \(3N \times 3N\) quelconque.
Le bûcheron peut empêcher plus de \(5N^2\) arbres majestueux. On repère les cases par leurs coordonnées de façon naturelle et on colorie chaque case dont au moins une coordonnée est divisible par \(3\) (voir la figure du livret officiel pour un plateau \(9 \times 9\)). Chaque carré \(3 \times 3\) du plateau contient exactement \(5\) cases coloriées ; donc chaque coup du jardinier fait pousser au plus \(4\) arbres sur des cases non coloriées. Le bûcheron peut couper ces arbres-là : ainsi, après chacun de ses tours, aucun arbre situé sur une case non coloriée n'a de hauteur positive. Il ne peut donc jamais y avoir plus d'arbres majestueux que de cases coloriées, c'est-à-dire \((3N)^2 - (2N)^2 = 5N^2\).
Le jardinier peut obtenir \(5N^2\) arbres majestueux. On le montre même dans un jeu modifié, plus difficile pour le jardinier : au tour du bûcheron, celui-ci peut diminuer de \(1\) la hauteur de tous les arbres du plateau sauf ceux que le jardinier vient de faire pousser, et en plus de quatre des arbres que le jardinier vient de faire pousser. (Le livret écrit « sauf ceux que le jardinier n'a pas fait pousser » ; il faut lire « sauf ceux qu'il vient de faire pousser ».) Clairement, une suite de coups qui assure \(K\) arbres majestueux dans le jeu modifié l'assure aussi dans le jeu original.
Soit \(M = \binom{9}{5}\) ; on appelle carte l'une des \(M\) façons de marquer \(5\) cases dans un carré \(3 \times 3\). Dans le jeu modifié, quand le jardinier choisit un sous-plateau \(3 \times 3\), le bûcheron choisit en fait une carte dans ce sous-plateau, et le résultat cumulé des deux coups est : chaque arbre marqué sur la carte gagne \(1\), chaque arbre du sous-plateau non marqué reste inchangé, et chaque arbre hors du sous-plateau perd \(1\) (s'il est de hauteur positive). Remarquons aussi que si le jardinier choisit un même sous-plateau \(M\ell\) fois, le bûcheron doit choisir une même carte au moins \(\ell\) fois (principe des tiroirs) ; il y a donc au moins \(5\) arbres qui gagnent chacun au moins \(\ell\) pendant ces coups.
La stratégie du jardinier : il découpe le plateau en \(N^2\) sous-plateaux \(3 \times 3\) disjoints, numérotés \(0, \ldots, N^2 - 1\) dans un ordre quelconque. Puis, pour \(b = N^2 - 1, \ldots, 0\) dans cet ordre, il joue \(10^6 M (M+1)^b\) fois sur le sous-plateau numéro \(b\).
Sur le sous-plateau \(b\), ces coups font d'abord croître \(5\) de ses arbres d'au moins \(10^6 (M+1)^b\), puis chaque coup ultérieur diminue leur hauteur d'au plus \(1\). (Comme les arbres du sous-plateau \(b\) avaient une hauteur nulle avant que le jardinier ne commence à y jouer, les coups joués sur les sous-plateaux d'indice \(> b\) n'ont pas diminué leur hauteur.) Après avoir fini le sous-plateau \(b\), le jardinier joue encore
coups. Donc, sur le sous-plateau \(b\), il reste à la fin \(5\) arbres de hauteur au moins
Chacun des \(N^2\) sous-plateaux contient ainsi \(5\) arbres majestueux, soit \(5N^2\) au total. \(\blacksquare\)