Shortlist 2025, C8¶
Domaine : Combinatoire · Difficulté : ★★★★★ · Proposé par : Singapore
Concepts : Coloriages et pavages · Principe extrémal · Double comptage · AM-GM et moyennes · Graphes : degrés, chemins, arbres
Solution officielle : Shortlist officielle 2025 (avec solutions), section C8 (livret PDF)
Problème 6 de l'OIM 2025
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2025, où il était le problème 6 (jour 2).
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Consider a \(2025 \times 2025\) grid of unit squares. We place on the grid some number of rectangular tiles, possibly of different sizes, such that each side of every tile lies on a grid line and every unit square is covered by at most one tile.
Determine the minimum number of tiles we need to place so that each row and each column has exactly one unit square that is not covered by any tile.
Indices : les idées clés
- Coloriages et pavages : pour \(n = k^2\), la réponse est \(k^2 + 2k - 3\) ; la construction place les cases découvertes sur un réseau incliné, avec \((k-1)^2\) carrés \(k \times k\) au centre et \(k - 1\) rectangles le long de chaque bord.
- Principe extrémal (solutions 1 et 4) : une « barrière » de longueur maximale de cases découvertes montantes borne la longueur de toutes les chaînes ; un contre-exemple minimal donne la contradiction dans le lemme de la solution 4.
- Double comptage : on regroupe cases découvertes et rectangles en chaînes alternées (solution 1), en cascades (solution 2) ou en « lignes de bouées » (solution 3), puis on compte de deux façons.
- AM-GM et moyennes : chaque fois, on aboutit à une quantité du type \(m + \frac{k^2}{m} \geq 2k\), ou \(a + b \geq 2\sqrt{ab} \geq 2\sqrt{n}\).
- Graphes : degrés, chemins, arbres (solution 4) : la formule d'Euler pour les graphes planaires ramène le problème à minorer \(E - V + L\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2025 (quatre solutions, qui diffèrent par la preuve de la minoration, et deux remarques).
Réponse : \(2025 + 2 \times 45 - 3 = 2112\) tuiles.
Solution 1¶
On traite le cas d'une grille \(n \times n\) avec \(n = k^2\), et l'on montre que la réponse est \(k^2 + 2k - 3\).
Construction (voir la figure du livret officiel, pour \(k = 4\)). Il y a \((k-1)^2\) rectangles au centre et \(k - 1\) rectangles le long de chacun des quatre bords, soit \(k^2 + 2k - 3\) rectangles. Précision ajoutée (la figure n'est pas lisible dans la version texte) : on peut prendre comme cases découvertes les cases de la ligne \(ik + j + 1\) et de la colonne \(jk + k - i\), pour \(0 \leq i, j \leq k - 1\) (une par ligne et par colonne) ; pour \(0 \leq i, j \leq k - 2\), le carré \(k \times k\) situé juste sous la case découverte \((i, j)\) (lignes \(ik + j + 2\) à \(ik + j + k + 1\), colonnes \(jk + k - i\) à \(jk + 2k - i - 1\)) ne contient aucune case découverte, et le reste de la grille se découpe en \(4(k - 1)\) rectangles ; nous l'avons vérifié par ordinateur pour \(2 \leq k \leq 7\).
Minoration. Prenons une configuration et marquons d'un X chaque case découverte. On entoure la grille de quatre rectangles \(n \times 1\).
Un chemin montant est un chemin qui suit les côtés des rectangles en allant vers le haut ou vers la droite ; on autorise les chemins de longueur nulle. Soit \(x_1, x_2, \ldots, x_m\) une suite de X la plus longue possible telle que :
- un chemin montant relie le coin inférieur gauche de la grille au coin inférieur gauche de \(x_1\) ;
- pour \(i = 1, \ldots, m - 1\), un chemin montant relie le coin supérieur droit de \(x_i\) au coin inférieur gauche de \(x_{i+1}\) ;
- un chemin montant relie le coin supérieur droit de \(x_m\) au coin supérieur droit de la grille.
Ces chemins et les cases \(x_1, \ldots, x_m\) forment une grande barrière de corail qui partage la grille en deux régions. Soit \(\mathcal{U}\) l'ensemble des X de la région supérieure, \(\mathcal{L}\) celui des X de la région inférieure, et \(\mathcal{X} = \{x_1, \ldots, x_m\}\) ; ces trois ensembles partitionnent les X.
On relie chaque X de \(\mathcal{X} \cup \mathcal{L}\) à deux rectangles : celui à sa droite et celui en dessous. On obtient des chaînes inférieures disjointes. Chaque X est relié à deux rectangles et chaque rectangle à au plus deux X, donc chaque chaîne alterne rectangles et X. Il n'y a pas de cycle, car les X d'une chaîne forment une suite croissante (chaque X est au-dessus et à droite du précédent) ; chaque chaîne commence et finit donc par un rectangle. Enfin, tous ces rectangles sont dans la région inférieure, car ils ne peuvent pas traverser la barrière.
De même, on relie chaque X de \(\mathcal{X} \cup \mathcal{U}\) au rectangle à sa gauche et à celui au-dessus : on obtient des chaînes supérieures, dont les rectangles sont dans la région supérieure, avec les mêmes propriétés. Chaînes supérieures et inférieures sont disjointes, à l'exception des X de \(\mathcal{X}\) (voir la figure du livret officiel).
Affirmation. Chaque chaîne contient au plus \(m\) X.
Preuve. Supposons qu'une chaîne contienne des X \(y_1, \ldots, y_l\) avec \(l > m\). Les rectangles de la chaîne fournissent un chemin montant entre \(y_i\) et \(y_{i+1}\) pour \(i = 1, \ldots, l - 1\). Pour relier le coin inférieur gauche de la grille à celui de \(y_1\), on remarque que, dans un pavage par rectangles, on peut toujours, depuis un sommet, descendre ou aller à gauche ; on part du coin inférieur gauche de \(y_1\) en descendant ou en allant à gauche jusqu'au coin inférieur gauche de la grille. De même, le coin supérieur droit de \(y_l\) se relie par un chemin montant au coin supérieur droit de la grille. On obtient une barrière avec plus de \(m\) X, ce qui contredit la maximalité de \(m\). \(\square\)
Conclusion. Chaque X de \(\mathcal{U} \cup \mathcal{L}\) appartient à exactement une chaîne, et chacun des \(m\) X de \(\mathcal{X}\) à exactement deux. En comptant ces derniers deux fois, on obtient \(m + k^2\) X au total. Chaque chaîne ayant au plus \(m\) X, il y a au moins \(\frac{m + k^2}{m} = 1 + \frac{k^2}{m}\) chaînes. Chaque chaîne contient exactement un rectangle de plus que de X, et deux chaînes différentes ont des rectangles différents ; il y a donc au moins
rectangles, par AM-GM. En retirant les quatre rectangles ajoutés à l'extérieur, il y a au moins \(k^2 + 2k - 3\) rectangles. \(\blacksquare\)
Solution 2¶
Autre preuve de la minoration. Soit \(n = k^2\) ; on marque d'un X chaque case découverte, et l'on ajoute deux rectangles \(n \times 1\) contre les bords gauche et droit de la grille. On trace des cascades rouges et bleues qui coulent le long des côtés des rectangles et à travers les X : les rouges vont vers le bas et la droite, les bleues vers le bas et la gauche, selon les règles suivantes.
- De chaque X, une cascade rouge coule vers le rectangle à sa droite, puis descend jusqu'au coin inférieur gauche de ce rectangle. De même, de chaque X, une cascade bleue coule vers le rectangle à sa gauche, puis descend jusqu'au coin inférieur droit de ce rectangle.
- Pour chaque rectangle \(R\) ayant un X juste en dessous : s'il y a une cascade rouge au coin inférieur gauche de \(R\), on la prolonge vers la droite jusqu'à ce qu'elle se jette dans le X ; de même, s'il y a une cascade bleue au coin inférieur droit de \(R\), on la prolonge vers la gauche jusqu'au X.
- Pour chaque rectangle \(R\) sans X juste en dessous, ayant à la fois une cascade rouge au coin inférieur gauche et une cascade bleue au coin inférieur droit :
- (a) si le X de la rangée du bas de \(R\) (posé sur la même ligne horizontale de la grille) est à gauche de \(R\), on regarde le coin inférieur droit de \(R\). S'il y a sous \(R\) un rectangle \(S\) dont le côté droit est aligné avec celui de \(R\), on prolonge la cascade bleue vers le bas jusqu'au coin inférieur droit de \(S\). Sinon, il y a à droite de \(R\) un rectangle \(T\) dont le côté inférieur est aligné avec celui de \(R\), et l'on prolonge la cascade rouge vers la droite jusqu'au coin inférieur gauche de \(T\) (voir la figure du livret officiel) ;
- (b) si ce X est à droite de \(R\), on fait de même en échangeant gauche et droite, rouge et bleu.
On applique ces règles tant qu'on peut tracer ou prolonger des cascades. Chaque cascade rouge descend depuis un X, tourne au plus une fois vers la droite, puis se jette éventuellement dans un autre X ; de même pour les bleues, vers la gauche.
Affirmation 2.1. Une cascade bleue et une cascade rouge ne peuvent pas suivre le même segment.
Preuve. Si le segment est vertical, les deux cascades viennent des deux X situés de part et d'autre de cette ligne verticale ; mais d'après la règle 2, la cascade issue du X le plus haut tourne avant de dépasser le X le plus bas : impossible. Si le segment est horizontal, c'est le côté inférieur d'un rectangle ; cela ne peut pas se produire lors d'une application de la règle 2 (les cascades se jettent dans le X en dessous avant de se rencontrer), ni de la règle 3 (une seule des deux cascades coule horizontalement). \(\square\)
Affirmation 2.2. Deux cascades de même couleur ne se rencontrent pas.
Preuve. Deux cascades ne peuvent pas fusionner en coulant verticalement, car elles viendraient de deux X d'une même colonne. Comme chaque cascade tourne au plus une fois (de vertical à horizontal), il reste le cas d'une cascade verticale rejoignant une cascade horizontale. Supposons par exemple que deux cascades bleues se rejoignent au coin inférieur gauche d'un rectangle \(R\). La cascade bleue horizontale ne peut atteindre ce coin que par la règle 3, ce qui impose une cascade rouge descendant le long du côté gauche de \(R\) ; par l'affirmation 2.1, il ne peut pas y avoir aussi une cascade bleue descendant ce côté : impossible. \(\square\)
Chaque cascade rouge se termine au coin inférieur gauche d'un rectangle, et chaque bleue au coin inférieur droit d'un rectangle ; on appelle ce rectangle le bassin de la cascade (voir la figure du livret officiel).
Affirmation 2.3. Deux cascades n'ont jamais le même bassin.
Preuve. Par l'affirmation 2.2, deux cascades de même couleur ne se rencontrent pas, donc n'ont pas le même bassin. Si une rouge et une bleue avaient le même bassin, elles finiraient respectivement aux coins inférieurs gauche et droit de ce bassin, ce qui contredit la règle 3 (l'une des deux serait prolongée). \(\square\)
Conclusion. Chaque X appartient à une cascade rouge et à une cascade bleue. Comme les bleues vont vers le bas et la gauche et les rouges vers le bas et la droite, une cascade bleue et une rouge ont au plus un X en commun. Soient \(b\) et \(r\) les nombres de cascades bleues et rouges. Une cascade bleue traverse au moins \(\frac{k^2}{b}\) X, qui appartiennent à des cascades rouges distinctes, donc \(r \geq \frac{k^2}{b}\). Par l'affirmation 2.3 et AM-GM, il y a au moins
bassins. Par ailleurs, \(k^2 - 1\) rectangles ont un X juste en dessous (un pour chaque X hors de la rangée du haut, distincts car les X sont dans des rangées distinctes), et d'après la règle 2, un bassin n'a pas de X juste en dessous : cela fait au moins \(2k\) rectangles supplémentaires. En retirant les deux rectangles extérieurs, il y a au moins \(k^2 - 1 + 2k - 2 = k^2 + 2k - 3\) rectangles. \(\blacksquare\)
Solution 3¶
Autre preuve de la minoration. Comme dans la solution 1, \(k = 45\), \(n = k^2\), et l'on entoure la grille de quatre rectangles \(n \times 1\).
Chaque case X a un unique rectangle adjacent à sa gauche et un unique rectangle adjacent à sa droite. Comme deux X ne sont jamais dans la même colonne, chaque rectangle a au plus un X adjacent à sa gauche et au plus un à sa droite. On appelle ligne de bouées une suite
où \(R_i\) est le rectangle adjacent à \(X_i\) à sa gauche, \(R_{i+1}\) le rectangle adjacent à \(X_i\) à sa droite, \(R_1\) n'a pas de X adjacent à sa gauche et \(R_{m+1}\) pas de X adjacent à sa droite. On autorise \(m = 0\) (la ligne est alors un seul rectangle). Chaque X et chaque rectangle appartient à une unique ligne de bouées.
L'intersection non vide d'une colonne avec une ligne de bouées est un bloc contigu de cases. On définit une relation \(\prec\) sur les lignes de bouées : \(C \prec C'\) si \(C \neq C'\) et s'il existe une colonne \(I\) rencontrant \(C\) et \(C'\) telle que \(I \cap C'\) soit au-dessus de \(I \cap C\).
Affirmation 3.1. Si \(C \prec C'\) et si une colonne \(I\) rencontre \(C\) et \(C'\), alors \(I \cap C'\) est au-dessus de \(I \cap C\).
Preuve. C'est vrai pour une colonne par définition. Les colonnes rencontrant à la fois \(C\) et \(C'\) forment un bloc contigu ; il suffit donc de voir que si c'est vrai pour une colonne \(I\), c'est vrai pour une colonne voisine \(I'\), ce qui est clair car \(I \cap C\) est relié à \(I' \cap C\), et de même pour \(C'\). \(\square\)
Affirmation 3.2. La relation \(\prec\) se prolonge en un ordre total sur l'ensemble des lignes de bouées.
Preuve. Par récurrence sur le cardinal \(s\) d'un ensemble \(\mathcal{S}\) de lignes de bouées ; le cas \(s = 1\) est clair. Soit \(s \geq 2\). Si une colonne rencontre toutes les lignes de \(\mathcal{S}\), alors \(\prec\) est déjà un ordre total par l'affirmation 3.1. Sinon, il existe une droite verticale \(\Delta\) telle que l'ensemble \(\mathcal{A}\) des lignes entièrement à gauche de \(\Delta\) et l'ensemble \(\mathcal{B}\) des lignes entièrement à droite de \(\Delta\) soient non vides. On a \(\mathcal{A} \cap \mathcal{B} = \varnothing\), et \(\prec\) restreinte à \(\mathcal{S} \setminus (\mathcal{A} \cup \mathcal{B})\) est un ordre total. Par hypothèse de récurrence, \(\prec\) se prolonge en un ordre total sur \(\mathcal{S} \setminus \mathcal{A}\) et sur \(\mathcal{S} \setminus \mathcal{B}\) ; les éléments de \(\mathcal{A}\) et de \(\mathcal{B}\) sont incomparables entre eux, donc on peut combiner ces deux ordres en un ordre total sur \(\mathcal{S}\) prolongeant \(\prec\). \(\square\)
On numérote les lignes de bouées \(C_0, C_1, \ldots, C_\alpha\) de sorte que \(C_i \prec C_j\) entraîne \(i < j\). Soit \(m_i\) le nombre de X de \(C_i\) ; alors \(C_i\) contient \(m_i + 1\) rectangles et \(m_0 + \cdots + m_\alpha = n\). Le nombre total de rectangles est donc \(n + \alpha + 1\).
Affirmation 3.3. Pour tout \(0 \leq i \leq \alpha\), \(m_i \leq \min(i, \alpha - i)\).
Preuve. Chaque X de \(C_0, \ldots, C_i\) a un unique rectangle adjacent en dessous. Ces rectangles sont distincts (deux X ne sont jamais dans la même rangée) et chacun est dans l'une des lignes \(C_0, \ldots, C_{i-1}\). D'où
donc \(m_i \leq i\). De même, avec les rectangles adjacents au-dessus des X, \(m_i \leq \alpha - i\). \(\square\)
On a alors \(\alpha \geq 2k = 2\sqrt{n}\), car sinon
ce qui est absurde. Le nombre de rectangles \(n + \alpha + 1\) est donc au moins \(k^2 + 2k + 1\), et après retrait des quatre rectangles auxiliaires, au moins \(k^2 + 2k - 3\). \(\blacksquare\)
Solution 4¶
On marque d'un X chaque case découverte et l'on voit la configuration comme un graphe planaire ; soient \(L\), \(V\), \(E\), \(F\) ses nombres de feuilles (sommets de degré \(1\)), de sommets, d'arêtes et de faces. Au départ, \(L = 0\). Par la formule d'Euler, \(V - E + F = 1\) (sans compter la face extérieure). Comme \(F\) est le nombre de X plus le nombre de rectangles, il suffit de montrer \(F \geq 2n + 2\sqrt{n} - 3\), c'est-à-dire
On effectue une série de modifications du graphe qui laissent \(E - V + L\) invariant (voir la figure du livret officiel) :
- pour chaque paire de X diagonalement adjacents (ayant un coin commun), on remplace ce coin par deux sommets reliés par une arête horizontale ;
- pour chaque coin d'un X qui est un sommet de degré \(4\) mais n'est le coin d'aucun autre X, on rétracte l'arête horizontale qui aboutit au X en ce coin, créant un nouveau sommet de degré \(1\) et faisant passer le degré du coin de \(4\) à \(3\) ;
- pour chaque sommet de degré \(4\) qui n'est pas un sommet d'un X, on rétracte les deux arêtes horizontales incidentes (créant deux nouveaux sommets) et l'on fusionne les deux arêtes verticales en une seule, en supprimant le sommet ;
- pour chaque sommet de degré \(3\) qui n'est pas un sommet d'un X, on rétracte l'arête sans arête opposée (créant un nouveau sommet) et l'on fusionne les deux autres, en supprimant le sommet.
On vérifie que chacune laisse \(E - V + L\) invariant. Après toutes ces modifications, on obtient un graphe \(G\). On colore les arêtes de \(G\) qui relient des coins de deux X différents : en vert si elles sont verticales, en or si elles sont horizontales. Les modifications garantissent qu'aucune arête verte ne coupe une arête dorée. Les arêtes vertes relient les X en chaînes vertes (une chaîne peut se réduire à un X isolé), et de même pour les chaînes dorées.
Lemme. Une chaîne dorée et une chaîne verte ont au plus un X en commun.
Preuve. Notons \((1, \sigma(1)), \ldots, (n, \sigma(n))\) les coordonnées des X. Supposons par l'absurde qu'une chaîne verte et une chaîne dorée aient deux X en commun, et prenons un exemple minimal : deux X \((i, \sigma(i))\) et \((j, \sigma(j))\), \(i < j\), dans les mêmes chaînes verte et dorée, avec \(j - i\) minimal. Sans perte de généralité, \(\sigma(i) < \sigma(j)\). Les abscisses des X d'une chaîne verte sont consécutives, et les ordonnées des X d'une chaîne dorée aussi :
Par minimalité de \(j - i\), il n'y a pas de X en \((l, \sigma(l))\) avec \(i < l < j\) et \(\sigma(i) < \sigma(l) < \sigma(j)\) (il serait dans les deux chaînes). Le rectangle \([i+1, j-1] \times [\sigma(i)+1, \sigma(j)-1]\) ne contient donc aucun X. Mais la chaîne dorée doit traverser ce rectangle horizontalement et la chaîne verte verticalement (éventuellement le long de son bord), ce qui contredit le fait qu'aucune arête verte ne touche une arête dorée. \(\square\)
Soient \(a\) le nombre de chaînes vertes et \(b\) celui des chaînes dorées. Chaque X est sur exactement une chaîne verte et une chaîne dorée, donc par le lemme \(n \leq ab\). Une chaîne verte de \(t\) X contient \(t - 1\) arêtes vertes, donc il y a \(n - a\) arêtes vertes, et de même \(n - b\) arêtes dorées. Soit \(g = (n - a) + (n - b)\) le nombre total d'arêtes vertes et dorées. Par AM-GM,
Soit \(c\) le nombre de X situés dans un coin de la grille. Chaque sommet de \(G\) est un sommet d'un X, un coin de la grille ou une feuille, donc
On minore \(E\) en ne comptant que les arêtes incidentes à un X : chaque X a quatre côtés, plus une arête issue de chacun de ses coins, sauf si ce coin est un coin de la grille ; les arêtes incidentes à deux X distincts sont exactement les arêtes vertes et dorées. Ainsi
On en déduit
et par (1),
Remarques¶
Remarque 1. Le problème a une réponse et une construction bien plus jolies que dans le cas général, parce que \(2025\) est un carré parfait. Pour \(n\) quelconque, la solution 1 s'adapte pour montrer que la borne est \(\lceil n + 2\sqrt{n} - 3 \rceil\), mais la construction est plus compliquée.
Remarque 2. Le problème 5 de la Romanian Master of Mathematics 2017 est un problème d'apparence voisine, avec des tuiles \(1 \times m\) au lieu de rectangles quelconques ; mais il est beaucoup plus simple, et ses idées n'aident pas du tout ici.