Shortlist 2007, C8

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

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

Solution officielle : Shortlist officielle 2007 (avec solutions), p. 37 (page 38 du PDF)

Figures reprises du livret officiel de la Shortlist.

Énoncé

Given a convex \(n\)-gon \(P\) in the plane. For every three vertices of \(P\), consider the triangle determined by them. Call such a triangle good if all its sides are of unit length.

Prove that there are not more than \(\frac{2}{3}n\) good triangles.

Indices : les idées clés

• Attributions : en chaque sommet \(A\), les sommets des bons triangles contenant \(A\) sont sur un arc du cercle unité de centre \(A\) ; on attribue à \(A\) les deux bons triangles extrémaux (au plus deux attributions par sommet).
• Double comptage : chaque bon triangle reçoit au moins trois attributions, d'où \(3t \leq 2n\).
• Argument géométrique : sinon, deux points \(X\), \(Y\) des cercles \(\omega_B\), \(\omega_C\) placeraient \(A\) dans le quadrilatère \(XYBC\), ce qui contredit la convexité.

Solutions

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

Solution

Considérons tous les bons triangles contenant un sommet donné \(A\). Les deux autres sommets d'un tel triangle sont sur le cercle \(\omega_A\) de rayon \(1\) et de centre \(A\). Comme \(P\) est convexe, tous ces sommets sont sur un arc d'angle inférieur à \(180^\circ\). Soit \(L_AR_A\) le plus court arc de ce type, orienté dans le sens des aiguilles d'une montre (voir figure 1). Chacun des segments \(AL_A\) et \(AR_A\) appartient à un unique bon triangle. On dit que le bon triangle de côté \(AL_A\) est attribué dans le sens direct à \(A\), et que le second, de côté \(AR_A\), est attribué dans le sens horaire à \(A\). Dans les cas où un seul bon triangle contient le sommet \(A\), ce triangle est attribué deux fois à \(A\).

Chaque sommet du polygone reçoit au plus deux attributions. (Les sommets qui n'appartiennent à aucun bon triangle n'en reçoivent pas.) Le nombre d'attributions est donc au plus \(2n\).

Considérons un bon triangle quelconque \(ABC\), de sommets rangés dans le sens horaire. Montrons que \(ABC\) est attribué à ses sommets au moins trois fois. Alors, en notant \(t\) le nombre de bons triangles, on obtient que le nombre \(K\) de toutes les attributions est au plus \(2n\), alors qu'il est au moins \(3t\). Donc \(3t \leq K \leq 2n\), comme voulu.

En fait, montrons que le triangle \(ABC\) est attribué soit dans le sens direct à \(C\), soit dans le sens horaire à \(B\). Alors, par la symétrie cyclique des sommets, on obtient que le triangle \(ABC\) est attribué soit dans le sens direct à \(A\), soit dans le sens horaire à \(C\), et soit dans le sens direct à \(B\), soit dans le sens horaire à \(A\), ce qui donne l'affirmation.

Supposons au contraire que \(L_C \neq A\) et \(R_B \neq A\). Notons \(A'\), \(B'\), \(C'\) les points d'intersection des cercles \(\omega_A\), \(\omega_B\) et \(\omega_C\), distincts de \(A\), \(B\), \(C\) (voir figure 2). Soit \(CL_CL'_C\) le bon triangle contenant \(CL_C\). Remarquons que l'angle de l'arc \(L_CA\) est inférieur à \(120^\circ\). L'un des points \(L_C\) et \(L'_C\) appartient alors à l'arc \(B'A\) de \(\omega_C\) ; soit \(X\) ce point. Dans le cas où \(L_C = B'\) et \(L'_C = A\), on choisit \(X = B'\).

De même, en considérant le bon triangle \(BR'_BR_B\) qui contient \(BR_B\) comme côté, on voit que l'un des points \(R_B\) et \(R'_B\) est sur l'arc \(AC'\) de \(\omega_B\). Notons ce point \(Y\), \(Y \neq A\). Alors les angles \(XAY\), \(YAB\), \(BAC\) et \(CAX\) (orientés dans le sens horaire) ne dépassent pas \(180^\circ\). Le point \(A\) est donc dans le quadrilatère \(XYBC\) (soit à l'intérieur, soit sur le segment \(XY\)). C'est impossible, puisque ces cinq points sont tous des sommets de \(P\).

Chaque bon triangle reçoit donc au moins trois attributions, et l'énoncé est prouvé. \(\blacksquare\)

Remarques

Remarque 1. En considérant un diamètre \(AB\) du polygone, on peut prouver que tout bon triangle contenant \(A\) ou \(B\) reçoit au moins quatre attributions. Cette observation mène à \(t \leq \left\lfloor \frac{2}{3}(n - 1) \right\rfloor\).

Remarque 2. Le résultat \(t \leq \left\lfloor \frac{2}{3}(n - 1) \right\rfloor\) est optimal. Pour construire un polygone à \(n = 3k + 1\) sommets et \(t = 2k\) triangles, prenons un losange \(AB_1C_1D_1\) de côté unité avec \(\angle B_1 = 60^\circ\). Faisons-le ensuite tourner autour de \(A\) de petits angles pour obtenir des losanges \(AB_2C_2D_2, \ldots, AB_kC_kD_k\) (voir figure 3). Le polygone \(AB_1 \ldots B_kC_1 \ldots C_kD_1 \ldots D_k\) a \(3k + 1\) sommets et contient \(2k\) bons triangles.

La construction pour \(n = 3k\) et \(n = 3k - 1\) s'obtient en supprimant les sommets \(D_n\) et \(D_{n-1}\).