Shortlist 2007, C2

Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : Japan

Concepts : Principe extrémal · Coloriages et pavages

Solution officielle : Shortlist officielle 2007 (avec solutions), p. 28 (page 29 du PDF)

Figures reprises du livret officiel de la Shortlist.

Énoncé

A unit square is dissected into \(n > 1\) rectangles such that their sides are parallel to the sides of the square. Any line, parallel to a side of the square and intersecting its interior, also intersects the interior of some rectangle. Prove that in this dissection, there exists a rectangle having no point on the boundary of the square.

Indices : les idées clés

• Contre-exemple minimal : deux rectangles ayant un côté commun peuvent être fusionnés, ce qui contredit la minimalité.
• Coin inférieur : avec les rectangles \(a\) et \(b\) des coins \(A\) et \(B\), et \(c\) voisin de \(a\), le rectangle \(d\) qui touche à la fois \(a\) et \(c\) doit toucher \(CD\), et son côté fournit une droite séparatrice.
• Solution 2 : deux rectangles « opposés » (attachés à des côtés opposés) se touchent ; leur point commun mène à une droite séparatrice (découpage).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2007 (deux solutions).

Solution 1

Appelons horizontale et verticale les directions des côtés du carré. Une droite horizontale ou verticale qui coupe l'intérieur du carré mais ne coupe l'intérieur d'aucun rectangle est appelée une droite séparatrice. Un rectangle n'ayant aucun point sur le bord du carré est appelé un rectangle intérieur.

Supposons au contraire qu'il existe un découpage du carré en plus d'un rectangle sans rectangle intérieur ni droite séparatrice. Considérons un tel découpage avec le plus petit nombre possible de rectangles. Remarquons que ce nombre est supérieur à \(2\), sinon leur côté commun fournirait une droite séparatrice.

S'il existe deux rectangles ayant un côté commun, on peut les remplacer par leur réunion (voir figure 1). Le nombre de rectangles était supérieur à \(2\), donc dans le nouveau découpage il est supérieur à \(1\). Évidemment, il n'y a dans le nouveau découpage ni droite séparatrice ni rectangle intérieur. Cela contredit le choix du découpage initial.

Notons \(ABCD\) le carré initial, avec \(A\) et \(B\) les sommets inférieurs gauche et droit. Considérons les deux rectangles \(a\) et \(b\) contenant respectivement les sommets \(A\) et \(B\). (Remarquons que \(a \neq b\), sinon son côté supérieur fournirait une droite séparatrice.) On peut supposer que la hauteur de \(a\) ne dépasse pas celle de \(b\). Considérons alors le rectangle \(c\) voisin du coin inférieur droit de \(a\) (il se peut que \(c = b\)). D'après ce qui précède, les hauteurs de \(a\) et \(c\) sont différentes. Deux cas sont alors possibles.

Cas 1 : la hauteur de \(c\) est inférieure à celle de \(a\). Considérons le rectangle \(d\) qui est adjacent à la fois à \(a\) et à \(c\), c'est-à-dire celui qui contient l'angle marqué sur la figure 2. Ce rectangle n'a aucun point commun avec \(BC\) (puisque \(a\) n'est pas plus haut que \(b\)), ni avec \(AB\) ou \(AD\) (évidemment). Donc \(d\) a un point commun avec \(CD\), et son côté gauche fournit une droite séparatrice. Contradiction.

Cas 2 : la hauteur de \(c\) est supérieure à celle de \(a\). De même, considérons le rectangle \(d\) contenant l'angle marqué sur la figure 3. Il n'a aucun point commun avec \(AD\) (sinon il aurait un côté commun avec \(a\)), ni avec \(AB\) ou \(BC\) (évidemment). Donc \(d\) a un point commun avec \(CD\). Son côté droit fournit donc une droite séparatrice, et l'on obtient de nouveau une contradiction. \(\blacksquare\)

Solution 2

Supposons de nouveau le contraire. Considérons un contre-exemple quelconque. On sait alors que chaque rectangle est attaché à au moins un côté du carré. Remarquons qu'un rectangle ne peut pas être attaché à deux côtés opposés, sinon l'un de ses côtés serait sur une droite séparatrice.

On dit que deux rectangles sont opposés s'ils sont attachés à des côtés opposés de \(ABCD\). Montrons qu'il existe deux rectangles opposés ayant un point commun.

Considérons la réunion \(L\) de tous les rectangles attachés à gauche. Supposons au contraire que \(L\) n'ait aucun point commun avec les rectangles attachés à droite. Prenons une ligne polygonale \(p\) reliant les côtés haut et bas du carré et passant juste à droite du bord de \(L\) (voir figure 4). Alors tous ses points appartiennent à des rectangles attachés soit en haut, soit en bas. De plus, l'extrémité supérieure de \(p\) appartient à un rectangle attaché en haut, et l'extrémité inférieure à un autre rectangle attaché en bas. Il existe donc un point de \(p\) où des rectangles attachés en haut et en bas se rencontrent. Ainsi, il existe toujours un couple de rectangles opposés voisins.

Prenons maintenant deux rectangles opposés voisins \(a\) et \(b\). On peut supposer que \(a\) est attaché à gauche et \(b\) à droite. Soit \(X\) leur point commun. Si \(X\) appartient à leurs côtés horizontaux (en particulier, \(X\) peut être un sommet commun de \(a\) et \(b\)), alors ces côtés fournissent une droite séparatrice (voir figure 5). Sinon, \(X\) est sur les côtés verticaux. Soit \(\ell\) la droite contenant ces côtés.

Comme \(\ell\) n'est pas une droite séparatrice, elle coupe l'intérieur d'un certain rectangle. Soit \(c\) un tel rectangle, le plus proche de \(X\) ; on peut supposer que \(c\) est au-dessus de \(X\). Soit \(Y\) le point commun de \(\ell\) et du côté inférieur de \(c\) (voir figure 6). Alors \(Y\) est aussi un sommet de deux rectangles situés sous \(c\).

Soit donc \(Y\) le coin supérieur droit du rectangle \(a'\) et le coin supérieur gauche du rectangle \(b'\). Alors \(a'\) et \(b'\) ne sont pas plus bas que \(a\) et \(b\) respectivement (il se peut que \(a = a'\) ou \(b = b'\)). Montrons que \(a'\) est attaché à gauche. Si \(a = a'\), c'est évident. Si \(a \neq a'\), alors \(a'\) est au-dessus de \(a\), sous \(c\) et à gauche de \(b'\) ; il ne peut donc être attaché qu'à gauche.

De même, \(b'\) est attaché à droite. Les côtés supérieurs de ces deux rectangles passent par \(Y\) ; ils fournissent donc de nouveau une droite séparatrice. Cette dernière contradiction termine la preuve. \(\blacksquare\)