Shortlist 2014, C7¶
Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : Russia
Concepts : Invariants et monovariants · Géométrie combinatoire : enveloppe convexe, points du réseau · Double comptage
Solution officielle : Shortlist officielle 2014 (avec solutions), p. 40 (page 41 du PDF)
Figures reprises du livret officiel de la Shortlist.
Énoncé¶
Let \(M\) be a set of \(n \geq 4\) points in the plane, no three of which are collinear. Initially these points are connected with \(n\) segments so that each point in \(M\) is the endpoint of exactly two segments. Then, at each step, one may choose two segments \(AB\) and \(CD\) sharing a common interior point and replace them by the segments \(AC\) and \(BD\) if none of them is present at this moment. Prove that it is impossible to perform \(n^3/4\) or more such moves.
Indices : les idées clés
- Une « longueur » discrète : la valeur d'un segment est le nombre de droites rouges (droites passant par deux points de \(M\)) qui le coupent en son intérieur.
- Monovariant : la valeur totale vaut au départ moins de \(n \cdot \frac{n^2}{2}\), et chaque étape la fait baisser d'au moins \(2\).
- Géométrie combinatoire : une droite qui coupe \(AC\) recoupe le triangle \(ACS\) sur \(AS\), \(CS\) ou en \(S\), donc elle coupe \(AB\) ou \(CD\) ; et les droites \((AB)\), \((CD)\) comptent d'un côté seulement.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2014 (une solution et trois remarques).
Solution¶
Une droite est dite rouge si elle contient deux points de \(M\). Comme trois points de \(M\) ne sont jamais alignés, chaque droite rouge détermine une unique paire de points de \(M\), et il y a exactement \(\binom{n}{2} < \frac{n^2}{2}\) droites rouges. La valeur d'un segment est le nombre de droites rouges qui le coupent en son intérieur, et la valeur d'un ensemble de segments est la somme des valeurs de ses éléments. On va montrer que (i) la valeur de l'ensemble de segments initial est inférieure à \(\frac{n^3}{2}\), et que (ii) chaque étape diminue la valeur de l'ensemble des segments présents d'au moins \(2\). Comme cette valeur n'est jamais négative, ces deux affirmations prouvent l'énoncé.
Pour (i), il suffit de remarquer que chaque segment a une valeur inférieure à \(\frac{n^2}{2}\). La valeur totale des \(n\) segments initiaux est donc inférieure à \(n \cdot \frac{n^2}{2} = \frac{n^3}{2}\).
Reste (ii). Supposons qu'à un moment on ait deux segments \(AB\) et \(CD\) ayant un point intérieur commun \(S\), et qu'au moment suivant on ait à la place les segments \(AC\) et \(BD\). Notons \(X_{AB}\) l'ensemble des droites rouges qui coupent le segment \(AB\) en son intérieur, et définissons de même \(X_{AC}\), \(X_{BD}\) et \(X_{CD}\). Il s'agit de prouver que
Montrons d'abord que
En effet, si \(g\) est une droite rouge qui coupe, par exemple, le segment \(AC\) en son intérieur, elle doit recouper le triangle \(ACS\), soit à l'intérieur de son côté \(AS\), soit à l'intérieur de son côté \(CS\), soit en \(S\) ; donc elle appartient à \(X_{AB}\) ou à \(X_{CD}\) (voir la figure 1). De plus, les droites rouges \((AB)\) et \((CD)\) comptent dans \(X_{AB} \cup X_{CD}\) mais pas dans \(X_{AC} \cup X_{BD}\). Cela prouve (1).
De façon analogue mais plus simple, on obtient
En effet, une droite rouge \(h\) de \(X_{AC} \cap X_{BD}\) appartient aussi, pour des raisons analogues, à \(X_{AB} \cap X_{CD}\). Pour être précis, on peut distinguer les cas \(S \in h\) (figure 2) et \(S \notin h\) (figure 3). Cela prouve (2).
En additionnant (1) et (2), on obtient la conclusion voulue (car \(\lvert X \cup Y \rvert + \lvert X \cap Y \rvert = \lvert X \rvert + \lvert Y \rvert\)), ce qui achève la solution. \(\blacksquare\)
Remarques¶
Remarque 1. Un problème du folklore se résout avec le même type d'opération :
On se donne \(n\) points rouges et \(n\) points verts dans le plan. Montrer qu'on peut tracer \(n\) segments deux à deux disjoints reliant chacun un point rouge à un point vert.
L'approche classique consiste à tracer \(n\) segments quelconques reliant les points rouges aux points verts, et à effectuer l'opération ci-dessus chaque fois que deux segments se coupent. À chaque étape, la longueur totale des segments diminue, par l'inégalité triangulaire. Comme il n'y a qu'un nombre fini de configurations de segments possibles, le processus s'arrête.
Dans le problème posé, en revanche, la somme des longueurs euclidiennes des segments présents ne semble pas très utile : elle montre que le processus s'arrête après un nombre fini d'étapes, mais ne donne pas facilement une borne polynomiale en \(n\) sur ce nombre. On peut voir la valeur d'un segment, introduite dans la solution, comme une version discrétisée de la longueur euclidienne, adaptée pour obtenir une telle borne. Le comité a tout de même jugé le problème suffisamment original pour la compétition.
Remarque 2. Il y a d'autres présentations essentiellement équivalentes de la même solution. Par exemple, on pose \(M = \{A_1, A_2, \ldots, A_n\}\), on note \(\{e_1, e_2, \ldots, e_n\}\) l'ensemble des segments présents à un moment donné, et l'on dit qu'un triplet \((i, j, k)\) d'indices avec \(i \neq j\) est sécant si la droite \(A_i A_j\) coupe le segment \(e_k\). On montre alors que le nombre \(S\) de triplets sécants vérifie \(0 \leq S < n^3\) au départ et diminue d'au moins \(4\) à chaque étape.
Remarque 3. Il n'est pas difficile de construire un exemple où \(cn^2\) coups sont possibles (pour une constante absolue \(c > 0\)). Il serait intéressant d'en dire plus sur l'écart entre \(cn^2\) et \(cn^3\).