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é¶

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

\[D_k = 2k\log_2 k.\]

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

\[2(k - i) + 2i + D_i + D_{k-i} \geq 2k + 2i\log_2 i + 2(k - i)\log_2(k - i). \tag{1}\]

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

\[p = 2\left(\sum_{i=1}^{M} r_i + \sum_{i=1}^{M} c_i\right).\]

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

\[2^n \geq \sum_{i=1}^{M} 2^{n - r_i - c_i} = 2^n\sum_{i=1}^{M} 2^{-(r_i + c_i)}. \tag{2}\]

En appliquant l'inégalité de Jensen à la fonction convexe \(f(x) = 2^{-x}\), on obtient

\[\frac{1}{M}\sum_{i=1}^{M} 2^{-(r_i + c_i)} \geq 2^{-\frac{1}{M}\sum_{i=1}^{M}(r_i + c_i)} = 2^{-\frac{p}{2M}}. \tag{3}\]

De (2) et (3), on tire

\[1 \geq M2^{-\frac{p}{2M}},\]

ce qui équivaut à

\[p \geq m2^{m+1}. \qquad \blacksquare\]