Shortlist 2025, C4¶
Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : China
Concepts : Invariants et monovariants · Double comptage
Solution officielle : Shortlist officielle 2025 (avec solutions), section C4 (livret PDF)
Figures reprises du livret officiel de la Shortlist.
Énoncé¶
Bluey is placing lollies on a \(1000 \times 1000\) grid. Initially, every cell of the grid is empty. At each step, Bluey chooses a row or column in which the total number of lollies is a multiple of \(3\), chooses an empty cell in this row or column, and places a lolly in it. If there is no such row or column, Bluey stops.
Determine the maximum number of lollies that Bluey can place.
Indices : les idées clés
- Généraliser : pour une grille \(n \times n\) avec \(n \geq 5\), le maximum vaut \(4n - 5\) ; pour \(n = 1000\), cela donne \(3995\).
- Invariants et monovariants (solution 1) : on suit les nombres \(P_0, P_1, P_2\) de lignes et colonnes dont le nombre de bonbons est congru à \(0\), \(1\), \(2\) modulo \(3\) ; chaque type de coup les modifie d'une façon fixée, ce qui exprime \(N\) en fonction de l'état final.
- Double comptage (solution 2) : on compte les « coups de ligne » \(R\) et les « coups de colonne » \(C\) de deux façons ; entre deux coups de ligne dans une même ligne, il faut au moins deux coups de colonne « d'assistance ».
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2025 (deux solutions et une remarque).
Réponse : \(3995\).
Solution 1¶
Soit \(n \geq 5\) ; on montre que la réponse pour une grille \(n \times n\) est \(4n - 5\), ce qui donne \(3995\) pour \(n = 1000\).
Construction. On numérote les bonbons \(1, 2, \ldots, 4n - 5\) dans l'ordre où Bluey les pose (voir la figure). En notant \((i, j)\) la case de la ligne \(i\) et de la colonne \(j\), une construction qui convient est :
- bonbon \(1\) en \((n-1, 2)\), bonbon \(2\) en \((n-1, 1)\) ;
- pour \(1 \leq r \leq n - 2\) : bonbons \(2r + 1\) et \(2r + 2\) en \((r, r+1)\) et \((r, r+2)\) ;
- bonbon \(2n - 1\) en \((n, n-1)\), bonbon \(2n\) en \((n-1, n-1)\), bonbon \(2n + 1\) en \((n-1, n-2)\) ;
- pour \(r = n-2, n-3, \ldots, 2\) : bonbons \(4n - 2 - 2r\) et \(4n - 1 - 2r\) en \((r, r)\) et \((r, r-1)\).
Nous avons vérifié par ordinateur (pour \(5 \leq n \leq 11\)) que chaque pose est autorisée et qu'à la fin aucune pose n'est plus possible.
Majoration. Soit \(N\) le nombre total de bonbons posés ; montrons \(N \leq 4n - 5\). Pour \(i = 1, \ldots, n\) et \(t = 0, 1, \ldots, N\), soit \(u_i(t) \in \{0, 1, 2\}\) le reste modulo \(3\) du nombre de bonbons de la ligne \(i\) après les \(t\) premières poses, et \(v_i(t)\) de même pour la colonne \(i\). Soient \(P_0(t)\), \(P_1(t)\), \(P_2(t)\) les nombres de \(0\), de \(1\) et de \(2\) parmi les \(2n\) valeurs \(u_1(t), \ldots, u_n(t), v_1(t), \ldots, v_n(t)\). On a \(P_0(t) + P_1(t) + P_2(t) = 2n\) et \((P_0(0), P_1(0), P_2(0)) = (2n, 0, 0)\).
Si à la \(t\)-ième étape Bluey pose un bonbon en ligne \(i\) et colonne \(j\), on a \(u_i(t) = 0\) ou \(v_j(t) = 0\). On classe les coups :
- coup A : \(u_i(t) = v_j(t) = 0\) ; les deux deviennent \(1\), et \((P_0, P_1, P_2)\) devient \((P_0 - 2, P_1 + 2, P_2)\) ;
- coup B : \(\{u_i(t), v_j(t)\} = \{0, 1\}\) ; ils deviennent \(\{1, 2\}\), et \((P_0, P_1, P_2)\) devient \((P_0 - 1, P_1, P_2 + 1)\) ;
- coup C : \(\{u_i(t), v_j(t)\} = \{0, 2\}\) ; ils deviennent \(\{0, 1\}\), et \((P_0, P_1, P_2)\) devient \((P_0, P_1 + 1, P_2 - 1)\).
Si Bluey fait \(a\) coups A, \(b\) coups B et \(c\) coups C, alors, en sommant les variations,
(le livret écrit la somme \(\sum_{i=0}^{n-1}\) ; il faut lire \(\sum_{t=0}^{N-1}\)), et de même \(P_1(N) = 2a + c\), \(P_2(N) = b - c\). On en déduit
De plus \(a \geq 1\), car le premier coup est un coup A. On conclut par une courte discussion :
- si \(a \geq 2\), alors \(N \leq 2n - 3a + P_1(N) \leq 4n - 3a < 4n - 5\), car \(P_1(N) \leq 2n\) ;
- si \(a = 1\) et \(P_1(N) \leq 2n - 2\), alors \(N \leq 2n - 3 + 2n - 2 = 4n - 5\) ;
- si \(a = 1\) et \(P_1(N) \geq 2n - 1\), alors au moins \(2n - 1\) des valeurs \(u_i(N)\), \(v_i(N)\) valent \(1\). Comme \(\sum_i u_i(N) \equiv \sum_i v_i(N) \pmod 3\) (les deux sommes comptent \(N\) modulo \(3\)), la dernière valeur vaut aussi \(1\), donc \(P_1(N) = 2n\). Le dernier coup est alors un coup A (seul un coup A laisse une ligne et une colonne toutes deux à \(1\)). Le premier coup étant aussi un coup A, soit cela contredit \(a = 1\), soit \(N = 1 < 4n - 5\).
Dans tous les cas, \(N \leq 4n - 5\). \(\blacksquare\)
Solution 2¶
Autre preuve de \(N \leq 4n - 5\). Un coup est un coup de ligne si Bluey ajoute un bonbon dans une ligne dont le nombre de bonbons était multiple de \(3\) ; soit \(r_i\) le nombre de coups de ligne dans la ligne \(i\). On définit de même les coups de colonne et \(c_i\) (un coup peut être les deux à la fois). Posons \(R = \sum_i r_i\) et \(C = \sum_i c_i\). Sans perte de généralité, le dernier coup de Bluey est un coup de ligne.
Chaque coup contribue au moins \(1\) à \(\sum_i (r_i + c_i)\), et le premier coup y contribue \(2\). Donc
Regardons les bonbons posés dans la ligne \(i\) : \(r_i\) d'entre eux le sont par des coups de ligne. Entre deux coups de ligne consécutifs dans la ligne \(i\), il faut au moins deux coups de colonne « d'assistance » ajoutant un bonbon dans la ligne \(i\) (pour revenir à un multiple de \(3\)). Aucun de ces coups ne peut être le tout premier coup, donc le nombre total de coups d'assistance est au plus \(C - 1\). Par double comptage, en sommant sur \(i\),
Le même argument sur les colonnes donne au plus \(R - 2\) coups de ligne d'assistance, car le premier et le dernier coup sont des coups de ligne qui ne peuvent pas être des coups d'assistance ; d'où
En additionnant,
Pour avoir égalité, il faudrait \(C - 1 = 2R - 2n\), soit \(2R - C = 2n - 1\), et \(R - 2 = 2C - 2n\), soit \(2C - R = 2n - 2\). En soustrayant, \(3(R - C) = 1\), ce qui est absurde pour des entiers. Donc \(N < 4n - 4\), c'est-à-dire \(N \leq 4n - 5\). \(\blacksquare\)
Remarques¶
Remarque 1. Il existe beaucoup d'autres constructions atteignant \(4n - 5\) bonbons ; le livret en donne une deuxième :
