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 place des bonbons sur une grille \(1000 \times 1000\). Au départ, toutes les cases de la grille sont vides. À chaque étape, Bluey choisit une ligne ou une colonne dont le nombre total de bonbons est un multiple de \(3\), choisit une case vide de cette ligne ou de cette colonne, et y place un bonbon. S'il n'existe pas de telle ligne ni de telle colonne, Bluey s'arrête.
Déterminer le nombre maximal de bonbons que Bluey peut placer.
Énoncé original (anglais)
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 :

Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2024 C1 ★☆☆☆☆ : \(n\) élèves, \(n\) courses, et un score qui récompense les bons classements : quelle somme des scores au maximum ?
- 2017 C2 ★☆☆☆☆ : Pour tout mot à \(n\) lettres \(a\), \(b\), \(c\), un autre mot est à au moins \(3n^2/2\) échanges de voisins.
- 2017 G8 ★★★★★ : On trace des segments tangents entre \(2017\) cercles sans croisement jusqu'à blocage : combien de segments à la fin ?
- 2014 C9 ★★★★★ : Un escargot change de cercle et de sens à chaque intersection : s'il parcourt tous les cercles, leur nombre est impair.