Shortlist 2014, C5

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

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

Solution officielle : Shortlist officielle 2014 (avec solutions), p. 34 (page 35 du PDF)

Problème 6 de l'OIM 2014

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2014, où il était le problème 6 (jour 2).

Figures reprises du livret officiel de la Shortlist.

Énoncé

Consider \(n \geq 3\) lines in the plane such that no two lines are parallel and no three have a common point. These lines divide the plane into polygonal regions; let \(\mathcal{F}\) be the set of regions having finite area. Prove that it is possible to colour \(\left\lceil \sqrt{n/2} \right\rceil\) of the lines blue in such a way that no region in \(\mathcal{F}\) has a completely blue boundary. (For a real number \(x\), \(\lceil x \rceil\) denotes the least integer which is not smaller than \(x\).)

Indices : les idées clés

• Principe extrémal : on prend un ensemble \(B\) de droites bleues maximal pour l'inclusion ; pour chaque droite rouge \(\ell\), la maximalité fournit une région finie dont le seul côté rouge est sur \(\ell\).
• Associer un point bleu : cette région a au moins trois côtés, donc un sommet intersection de deux droites bleues ; on l'associe à \(\ell\).
• Double comptage : chaque point bleu est associé à au plus quatre droites rouges, d'où \(n - k \leq 4\binom{k}{2}\), donc \(n \leq 2k^2\).

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2014 (une solution et deux remarques).

Solution

Soit \(L\) l'ensemble des droites. Choisissons un sous-ensemble \(B \subseteq L\) maximal pour l'inclusion tel que, si l'on colorie en bleu les droites de \(B\), aucune région de \(\mathcal{F}\) n'a un bord entièrement bleu. Posons \(\lvert B \rvert = k\). On affirme que \(k \geq \left\lceil \sqrt{n/2} \right\rceil\).

Colorions en rouge toutes les droites de \(L \setminus B\). Appelons bleu un point d'intersection de deux droites bleues. Il y a \(\binom{k}{2}\) points bleus.

Considérons une droite rouge \(\ell\). Par maximalité de \(B\), il existe au moins une région \(A \in \mathcal{F}\) dont le seul côté rouge est sur \(\ell\). Comme \(A\) a au moins trois côtés, elle a au moins un sommet bleu. Prenons un tel sommet et associons-le à \(\ell\).

Chaque point bleu appartient à quatre régions (dont certaines peuvent être non bornées), donc il est associé à au plus quatre droites rouges. Le nombre de droites rouges est donc au plus \(4\binom{k}{2}\). Comme ce nombre vaut \(n - k\),

\[n - k \leq 2k(k - 1), \quad \text{donc} \quad n \leq 2k^2 - k \leq 2k^2,\]

et finalement \(k \geq \left\lceil \sqrt{n/2} \right\rceil\), ce qui donne le résultat. \(\blacksquare\)

Remarques

Remarque 1. On peut améliorer la constante de plusieurs façons ; en voici deux. En revanche, le comité ne connaît aucun résultat montrant qu'il est parfois impossible de colorier \(k\) droites avec la propriété voulue pour \(k \gg \sqrt{n}\). Il a donc préféré garder la formulation d'origine.

1. Montrons d'abord que, dans la preuve ci-dessus, on a en fait \(k = \lvert B \rvert \geq \left\lceil \sqrt{2n/3} \right\rceil\). On fait des associations pondérées. Si une région \(A\) dont le seul côté rouge est sur \(\ell\) a \(k\) sommets, dont \(k - 2\) bleus, on associe chacun de ces sommets bleus à \(\ell\) avec le poids \(\frac{1}{k - 2}\). La somme des poids de toutes les associations vaut exactement \(n - k\). On vérifie que, parmi les quatre régions adjacentes à un sommet bleu \(v\), au plus deux sont des triangles. La somme des poids des associations qui concernent \(v\) est donc au plus \(1 + 1 + \frac{1}{2} + \frac{1}{2} = 3\). On en déduit

   \[n - k \leq 3\binom{k}{2}, \quad \text{soit} \quad 2n \leq 3k^2 - k < 3k^2,\]

   ce qui donne \(k \geq \left\lceil \sqrt{2n/3} \right\rceil\).

2. Montrons même que \(k = \lvert B \rvert \geq \lceil \sqrt{n} \rceil\), en associant autrement des points aux droites rouges. Appelons rouge un point situé à la fois sur une droite rouge et sur une droite bleue. Pour une droite rouge \(\ell\), prenons une région \(A \in \mathcal{F}\) dont le seul côté rouge est sur \(\ell\), et soient \(r', r, b_1, \ldots, b_k\) ses sommets dans le sens des aiguilles d'une montre, avec \(r', r \in \ell\) ; les points \(r', r\) sont rouges et les points \(b_1, \ldots, b_k\) sont bleus. On associe à \(\ell\) le point rouge \(r\) et le point bleu \(b_1\). À chaque paire formée d'un point rouge \(r\) et d'un point bleu \(b\), on associe ainsi au plus une droite rouge, car il y a au plus une région \(A\) ayant \(r\) et \(b\) comme sommets consécutifs dans le sens des aiguilles d'une montre.

On affirme que chaque point bleu \(b\) est associé à au plus deux droites rouges ; cela donne la borne voulue

\[n - k \leq 2\binom{k}{2} \iff n \leq k^2.\]

Supposons au contraire que trois droites rouges \(\ell_1\), \(\ell_2\), \(\ell_3\) soient associées au même point bleu \(b\), et soient \(r_1\), \(r_2\), \(r_3\) les points rouges associés ; ils sont distincts. Le point \(b\) définit quatre demi-droites bleues, et chaque \(r_i\) est le point rouge le plus proche de \(b\) sur l'une d'elles. On peut donc supposer que \(r_2\) et \(r_3\) sont sur une même droite bleue passant par \(b\), et \(r_1\) sur l'autre.

Considérons la région \(A\) qui a servi à associer \(r_1\) et \(b\) à \(\ell_1\). Trois de ses sommets consécutifs (dans le sens des aiguilles d'une montre) sont \(r_1\), \(b\), et \(r_2\) ou \(r_3\) (disons \(r_2\)). Comme \(A\) n'a qu'un côté rouge, c'est le triangle \(r_1 b r_2\) ; mais alors \(\ell_1\) et \(\ell_2\) passent toutes deux par \(r_2\), de même qu'une droite bleue, ce qui contredit les hypothèses.

Remarque 2. L'hypothèse que les droites ne sont pas parallèles n'est essentiellement pas utilisée dans la solution, ni dans la remarque précédente ; on peut donc l'omettre.