Shortlist 2009, C4¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Netherlands
Concepts : Coloriages et pavages · Convexité, inégalité de Jensen, lissage · Double comptage
Solution officielle : Shortlist officielle 2009 (avec solutions), p. 31 (page 33 du PDF)
Énoncé¶
Pour un entier \(m \geq 1\), on considère les découpages d'un échiquier \(2^m \times 2^m\) en rectangles formés de cases de l'échiquier, dans lesquels chacune des \(2^m\) cases d'une diagonale forme à elle seule un rectangle de côté \(1\). Déterminer la plus petite somme possible des périmètres des rectangles d'un tel découpage.
Énoncé original (anglais)
For an integer \(m \geq 1\), we consider partitions of a \(2^m \times 2^m\) chessboard into rectangles consisting of cells of the chessboard, in which each of the \(2^m\) cells along one diagonal forms a separate rectangle of side length \(1\). Determine the smallest possible sum of rectangle perimeters in such a partition.
Indices : les idées clés
- Deux moitiés : aucun rectangle ne recouvre à la fois des cases sous la diagonale et au-dessus ; on minimise séparément sur l'escalier \(B_k\), avec une construction récursive de périmètre \(m2^{m+1}\) pour \(k = 2^m\).
- Récurrence : le rectangle du coin a son coin supérieur gauche sur la diagonale, ce qui découpe \(B_k\) en \(B_i\) et \(B_{k-i}\) ; Jensen pour \(2x\log_2 x\) conclut.
- Comptage de sous-ensembles (solution 2) : les sous-ensembles « de type \(i\) » sont disjoints, d'où \(\sum 2^{-(r_i + c_i)} \leq 1\), puis Jensen pour \(2^{-x}\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2009 (deux solutions).
Réponse : \((m + 1)2^{m+2}\).
Solution 1¶
Pour un échiquier \(k \times k\), on introduit de façon standard des coordonnées pour les sommets des cases, et l'on suppose que la case \(C_{ij}\) de la ligne \(i\) et de la colonne \(j\) a pour sommets \((i - 1, j - 1)\), \((i - 1, j)\), \((i, j - 1)\), \((i, j)\), où \(i, j \in \{1, \ldots, k\}\). Sans perte de généralité, supposons que les cases \(C_{ii}\), \(i = 1, \ldots, k\), forment chacune un rectangle séparé. On peut alors considérer séparément le domaine \(B_k = \bigcup_{1 \leq i < j \leq k} C_{ij}\) situé d'un côté de cette diagonale et le domaine isométrique \(B'_k = \bigcup_{1 \leq j < i \leq k} C_{ij}\) de l'autre côté, car aucun rectangle ne peut recouvrir à la fois des cases de \(B_k\) et de \(B'_k\). Nous allons montrer que, pour \(k = 2^m\), le plus petit périmètre total d'une partition de \(B_k\) en rectangles est \(m2^{m+1}\). La réponse globale au problème est alors \(2 \cdot m2^{m+1} + 4 \cdot 2^m = (m + 1)2^{m+2}\).
Construisons d'abord par récurrence, pour \(m \geq 1\), une partition de \(B_{2^m}\) de périmètre total \(m2^{m+1}\). Si \(m = 0\), le domaine \(B_{2^m}\) est vide et le périmètre total est \(0\). Pour \(m \geq 0\), le domaine \(B_{2^{m+1}}\) est formé d'un carré \(2^m \times 2^m\) dans le coin inférieur droit, de sommets \((2^m, 2^m)\), \((2^m, 2^{m+1})\), \((2^{m+1}, 2^m)\), \((2^{m+1}, 2^{m+1})\), auquel sont accolés, le long des bords gauche et supérieur, deux domaines isométriques à \(B_{2^m}\). Le carré, avec les partitions récursives de ces deux domaines, donne une partition de périmètre total \(4 \cdot 2^m + 2 \cdot m2^{m+1} = (m + 1)2^{m+2}\), ce qui achève la récurrence.
Posons
Remarquons que \(D_k = m2^{m+1}\) si \(k = 2^m\). Montrons maintenant par récurrence sur \(k\) que le périmètre total d'une partition de \(B_k\) en rectangles est au moins \(D_k\). Le cas \(k = 1\) est trivial (voir \(m = 0\) ci-dessus). Supposons l'affirmation vraie pour tous les entiers strictement positifs inférieurs à \(k\). Étudions une partition de \(B_k\) en rectangles fixée, qui atteint le périmètre total minimal. Soit \(R\) le rectangle qui recouvre la case \(C_{1k}\) du coin inférieur droit, et soit \((i, j)\) le coin supérieur gauche de \(R\). Montrons d'abord que \(i = j\). Supposons \(i < j\). Alors le segment de \((i, j)\) à \((i + 1, j)\) ou celui de \((i, j)\) à \((i, j - 1)\) doit appartenir au bord d'un rectangle de la partition. Sans perte de généralité, supposons que ce soit le segment de \((i, j)\) à \((i + 1, j)\).
Cas 1. Aucun segment de \((i, l)\) à \((i + 1, l)\) avec \(j < l < k\) n'appartient au bord d'un rectangle de la partition. Il existe alors un rectangle \(R'\) de la partition qui a en commun avec \(R\) le côté de \((i, j)\) à \((i, k)\). En réunissant ces deux rectangles en un seul, on obtient une partition de périmètre total plus petit, ce qui est une contradiction.
Cas 2. Il existe un \(l\) tel que \(j < l < k\) et que le segment de \((i, l)\) à \((i + 1, l)\) appartienne au bord d'un rectangle de la partition. On remplace alors le côté supérieur de \(R\) par le segment de \((i + 1, j)\) à \((i + 1, k)\) et, pour les rectangles dont le côté inférieur est sur le segment de \((i, j)\) à \((i, k)\), on déplace ce côté inférieur vers le haut pour qu'il soit sur le segment de \((i + 1, j)\) à \((i + 1, k)\). On obtient ainsi une partition de \(B_k\) en rectangles de périmètre total plus petit, ce qui est une contradiction.
Le fait que le coin supérieur gauche de \(R\) a pour coordonnées \((i, i)\) est donc établi. Par conséquent, la partition est formée de \(R\), des rectangles d'une partition d'un domaine isométrique à \(B_i\) et de ceux d'une partition d'un domaine isométrique à \(B_{k-i}\). D'après l'hypothèse de récurrence, son périmètre total est au moins
Comme la fonction \(f(x) = 2x\log_2 x\) est convexe pour \(x > 0\), l'inégalité de Jensen montre immédiatement que le minimum du membre de droite de (1) est atteint pour \(i = k/2\). Le périmètre total de la partition optimale de \(B_k\) est donc au moins \(2k + 2\frac{k}{2}\log_2\frac{k}{2} + 2\frac{k}{2}\log_2\frac{k}{2} = D_k\). \(\blacksquare\)
Solution 2¶
On commence comme dans la solution 1, et l'on donne une autre preuve que \(m2^{m+1}\) minore le périmètre total d'une partition de \(B_{2^m}\) en \(n\) rectangles. Posons \(M = 2^m\). Pour \(1 \leq i \leq M\), notons \(r_i\) le nombre de rectangles de la partition qui recouvrent une case de la ligne \(i\), et \(c_j\) le nombre de rectangles qui recouvrent une case de la colonne \(j\). Remarquons que le périmètre total \(p\) de tous les rectangles de la partition vaut
Aucun rectangle ne peut recouvrir à la fois des cases de la ligne \(i\) et de la colonne \(i\), sinon il recouvrirait aussi la case \(C_{ii}\). Classons les ensembles \(S\) de rectangles de la partition de la façon suivante. On dit que \(S\) est de type \(i\), \(1 \leq i \leq M\), si \(S\) contient les \(r_i\) rectangles qui recouvrent une case de la ligne \(i\), mais aucun des \(c_i\) rectangles qui recouvrent une case de la colonne \(i\). Il y a en tout \(2^{n - r_i - c_i}\) ensembles de type \(i\). Montrons qu'aucun ensemble \(S\) ne peut être à la fois de type \(i\) et de type \(j\) si \(i \neq j\). Supposons le contraire, avec sans perte de généralité \(i < j\). La case \(C_{ij}\) doit être recouverte par un rectangle \(R\). L'ensemble \(S\) est de type \(i\), donc \(R\) appartient à \(S\). Mais \(S\) est de type \(j\), donc \(R\) n'appartient pas à \(S\), ce qui est une contradiction. Comme il y a \(2^n\) ensembles de rectangles de la partition, on en déduit
En appliquant l'inégalité de Jensen à la fonction convexe \(f(x) = 2^{-x}\), on obtient
De (2) et (3), on tire
ce qui équivaut à
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2012 C5 ★★★☆☆ : Si l'on peut faire tourner les couleurs des jetons à distance \(d\), on peut les remettre à leur couleur à distance \(d + 2\).
- 2007 C5 ★★★☆☆ : Des bandes verticales coloriées en rouge et bleu : un rectangle \(a \times b\) a ses quatre sommets de la même couleur.
- 2021 C7 ★★★★☆ : Des ensembles bloquants minimaux pour une grenouille sur une grille \(3m \times 3m\) : encadrer leur taille maximale.
- 2025 C8 ★★★★★ · OIM P6 : Combien de tuiles rectangulaires faut-il pour laisser exactement une case libre par ligne et par colonne ?