Shortlist 2008, C1

Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : non indiqué

Concepts : Géométrie combinatoire : enveloppe convexe, points du réseau · Principe extrémal

Solution officielle : Shortlist officielle 2008 (avec solutions), p. 21 (page 22 du PDF)

Figures reprises du livret officiel de la Shortlist.

Énoncé

In the plane we consider rectangles whose sides are parallel to the coordinate axes and have positive length. Such a rectangle will be called a box. Two boxes intersect if they have a common point in their interior or on their boundary.

Find the largest \(n\) for which there exist \(n\) boxes \(B_1, \ldots, B_n\) such that \(B_i\) and \(B_j\) intersect if and only if \(i \not\equiv j \pm 1 \pmod n\).

Indices : les idées clés

• Projections : deux boîtes sont disjointes si et seulement si leurs projections sur l'un des axes sont disjointes.
• Lemme en dimension \(1\) : si des intervalles \(\Delta_1, \ldots, \Delta_n\) se coupent deux à deux dès qu'ils ne sont pas voisins, au plus trois paires \((\Delta_k, \Delta_{k+1})\) sont disjointes ; on le prouve avec le plus à droite des bouts gauches et le plus à gauche des bouts droits.
• Comptage : les \(n\) paires voisines disjointes se répartissent sur deux axes, d'où \(n \leq 3 + 3 = 6\) (et \(9\) en dimension \(3\)).

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2008 (une solution, une remarque et la version originale en dimension 3).

Solution

Réponse : le nombre maximal de telles boîtes est \(6\).

Un exemple est représenté sur la figure.

Montrons maintenant que \(6\) est le maximum. Supposons que des boîtes \(B_1, \ldots, B_n\) vérifient la condition. Soient \(I_k\) et \(J_k\) les intervalles fermés projections de \(B_k\) sur les axes des \(x\) et des \(y\), pour \(1 \leq k \leq n\).

Si \(B_i\) et \(B_j\) se coupent, avec un point commun \((x, y)\), alors \(x \in I_i \cap I_j\) et \(y \in J_i \cap J_j\) ; les intersections \(I_i \cap I_j\) et \(J_i \cap J_j\) sont donc non vides. Réciproquement, si \(x \in I_i \cap I_j\) et \(y \in J_i \cap J_j\) pour certains réels \(x\), \(y\), alors \((x, y)\) est un point commun de \(B_i\) et \(B_j\). Autrement dit, \(B_i\) et \(B_j\) sont disjointes si et seulement si leurs projections sur l'un au moins des axes sont disjointes.

Pour abréger, on dit que deux boîtes ou deux intervalles sont voisins si leurs indices diffèrent de \(1\) modulo \(n\), et non voisins sinon.

Les boîtes voisines \(B_k\) et \(B_{k+1}\) ne se coupent pas, pour tout \(k = 1, \ldots, n\). Donc \((I_k, I_{k+1})\) ou \((J_k, J_{k+1})\) est une paire d'intervalles disjoints, \(1 \leq k \leq n\). Il y a donc au moins \(n\) paires d'intervalles disjoints parmi \((I_1, I_2), \ldots, (I_{n-1}, I_n), (I_n, I_1)\) ; \((J_1, J_2), \ldots, (J_{n-1}, J_n), (J_n, J_1)\).

Ensuite, deux boîtes non voisines quelconques se coupent, donc leurs projections sur les deux axes se coupent aussi. L'affirmation ci-dessous montre alors qu'au plus \(3\) paires parmi \((I_1, I_2), \ldots, (I_{n-1}, I_n), (I_n, I_1)\) sont disjointes, et de même pour \((J_1, J_2), \ldots, (J_{n-1}, J_n), (J_n, J_1)\). Par conséquent, \(n \leq 3 + 3 = 6\), comme annoncé. Il reste à énoncer et justifier l'affirmation.

Affirmation. Soient \(\Delta_1, \Delta_2, \ldots, \Delta_n\) des intervalles d'une droite tels que deux intervalles non voisins quelconques se coupent. Alors \(\Delta_k\) et \(\Delta_{k+1}\) sont disjoints pour au plus trois valeurs de \(k = 1, \ldots, n\).

Preuve. Notons \(\Delta_k = [a_k, b_k]\), \(1 \leq k \leq n\). Soit \(\alpha = \max(a_1, \ldots, a_n)\) le plus à droite des bouts gauches de \(\Delta_1, \ldots, \Delta_n\), et soit \(\beta = \min(b_1, \ldots, b_n)\) le plus à gauche de leurs bouts droits. Supposons sans perte de généralité que \(\alpha = a_2\).

Si \(\alpha \leq \beta\), alors \(a_i \leq \alpha \leq \beta \leq b_i\) pour tout \(i\). Chaque \(\Delta_i\) contient \(\alpha\), et il n'existe donc aucune paire disjointe \((\Delta_i, \Delta_{i+1})\).

Si \(\beta < \alpha\), alors \(\beta = b_i\) pour un certain \(i\) tel que \(a_i < b_i = \beta < \alpha = a_2 < b_2\) ; donc \(\Delta_2\) et \(\Delta_i\) sont disjoints. Or \(\Delta_2\) coupe tous les autres intervalles sauf peut-être \(\Delta_1\) et \(\Delta_3\), donc \(\Delta_2\) et \(\Delta_i\) ne peuvent être disjoints que si \(i = 1\) ou \(i = 3\). Supposons par symétrie que \(i = 3\) ; alors \(\beta = b_3\). Comme chacun des intervalles \(\Delta_4, \ldots, \Delta_n\) coupe \(\Delta_2\), on a \(a_i \leq \alpha \leq b_i\) pour \(i = 4, \ldots, n\). Donc \(\alpha \in \Delta_4 \cap \cdots \cap \Delta_n\) ; en particulier \(\Delta_4 \cap \cdots \cap \Delta_n \neq \varnothing\). De même, \(\Delta_5, \ldots, \Delta_n, \Delta_1\) coupent tous \(\Delta_3\), de sorte que \(\Delta_5 \cap \cdots \cap \Delta_n \cap \Delta_1 \neq \varnothing\), puisque \(\beta \in \Delta_5 \cap \cdots \cap \Delta_n \cap \Delta_1\). Il ne reste donc que \((\Delta_1, \Delta_2)\), \((\Delta_2, \Delta_3)\) et \((\Delta_3, \Delta_4)\) comme paires d'intervalles disjoints possibles, comme voulu. \(\square\) \(\blacksquare\)

Remarque et version originale

Le problème est une version en dimension \(2\) de la proposition originale, reproduite ci-dessous. Le manque criant de propositions faciles et adaptées a conduit le comité de sélection à retenir une variante simplifiée. La même affirmation en dimension \(1\) sert dans les deux versions.

Proposition originale. On considère des parallélépipèdes de l'espace, d'arêtes parallèles aux axes de coordonnées et de longueur strictement positive. Un tel parallélépipède est appelé une boîte. Deux boîtes se coupent si elles ont un point commun à l'intérieur ou sur leur bord. Trouver le plus grand \(n\) pour lequel il existe \(n\) boîtes \(B_1, \ldots, B_n\) telles que \(B_i\) et \(B_j\) se coupent si et seulement si \(i \not\equiv j \pm 1 \pmod n\).

Le nombre maximal de telles boîtes est \(9\). Supposons que des boîtes \(B_1, \ldots, B_n\) vérifient la condition. Soient \(I_k\), \(J_k\) et \(K_k\) les intervalles fermés projections de la boîte \(B_k\) sur les axes des \(x\), des \(y\) et des \(z\), pour \(1 \leq k \leq n\). Comme précédemment, \(B_i\) et \(B_j\) sont disjointes si et seulement si leurs projections sur l'un au moins des axes sont disjointes.

On dit de nouveau que deux boîtes ou intervalles sont voisins si leurs indices diffèrent de \(1\) modulo \(n\), et non voisins sinon.

Les boîtes voisines \(B_i\) et \(B_{i+1}\) ne se coupent pas, pour tout \(i = 1, \ldots, n\). Donc l'une au moins des paires \((I_i, I_{i+1})\), \((J_i, J_{i+1})\) et \((K_i, K_{i+1})\) est une paire d'intervalles disjoints. Il y a donc au moins \(n\) paires d'intervalles disjoints parmi les \((I_i, I_{i+1}), (J_i, J_{i+1}), (K_i, K_{i+1})\), \(1 \leq i \leq n\).

Ensuite, deux boîtes non voisines quelconques se coupent, donc leurs projections sur les trois axes se coupent aussi. D'après l'affirmation de la solution de la version en dimension \(2\), au plus \(3\) paires parmi \((I_1, I_2), \ldots, (I_{n-1}, I_n), (I_n, I_1)\) sont disjointes ; de même pour \((J_1, J_2), \ldots, (J_n, J_1)\) et \((K_1, K_2), \ldots, (K_n, K_1)\). Par conséquent, \(n \leq 3 + 3 + 3 = 9\), comme annoncé.

Pour \(n = 9\), le système de boîtes voulu existe. Considérons les intervalles du tableau suivant :

\(i\)	\(I_i\)	\(J_i\)	\(K_i\)
\(1\)	\([1, 4]\)	\([1, 6]\)	\([3, 6]\)
\(2\)	\([5, 6]\)	\([1, 6]\)	\([1, 6]\)
\(3\)	\([1, 2]\)	\([1, 6]\)	\([1, 6]\)
\(4\)	\([3, 6]\)	\([1, 4]\)	\([1, 6]\)
\(5\)	\([1, 6]\)	\([5, 6]\)	\([1, 6]\)
\(6\)	\([1, 6]\)	\([1, 2]\)	\([1, 6]\)
\(7\)	\([1, 6]\)	\([3, 6]\)	\([1, 4]\)
\(8\)	\([1, 6]\)	\([1, 6]\)	\([5, 6]\)
\(9\)	\([1, 6]\)	\([1, 6]\)	\([1, 2]\)

On a \(I_1 \cap I_2 = I_2 \cap I_3 = I_3 \cap I_4 = \varnothing\), \(J_4 \cap J_5 = J_5 \cap J_6 = J_6 \cap J_7 = \varnothing\), et enfin \(K_7 \cap K_8 = K_8 \cap K_9 = K_9 \cap K_1 = \varnothing\). Les intervalles de chaque colonne se coupent dans tous les autres cas. Il s'ensuit que les boîtes \(B_i = I_i \times J_i \times K_i\), \(i = 1, \ldots, 9\), ont la propriété voulue.