Shortlist 2025, C7

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

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

Solution officielle : Shortlist officielle 2025 (avec solutions), section C7 (livret PDF)

Figures reprises du livret officiel de la Shortlist.

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

Let \(\mathcal{P}\) be a regular \(100\)-gon. An Aussie triangulation is formed by dividing \(\mathcal{P}\) into a set \(\mathcal{T}\) of non-overlapping triangles such that:

• there are exactly \(2025\) different points, including the \(100\) vertices of \(\mathcal{P}\), that are a vertex of at least one triangle in \(\mathcal{T}\), and
• no three of these \(2025\) points are collinear.

A quokkalateral is a convex quadrilateral that consists of two triangles in \(\mathcal{T}\) sharing a common side. Two quokkalaterals may share a triangle in \(\mathcal{T}\).

Determine the minimum number of quokkalaterals among all Aussie triangulations.

Indices : les idées clés

• Double comptage : la somme des angles des triangles donne \(|\mathcal{T}| = 2n - m - 2\), et le décompte des côtés donne le nombre \(e = 3n - 2m - 3\) d'arêtes intérieures ; on compte ensuite les flèches par leur sommet d'arrivée.
• Flèches sur les arêtes non convexes : une arête intérieure dont le quadrilatère n'est pas convexe reçoit une flèche vers le sommet où l'angle dépasse \(180°\) ; minimiser les quokkalatères revient à maximiser le nombre de flèches.
• Géométrie combinatoire : enveloppe convexe, points du réseau : un sommet reçoit au plus trois flèches, et les « faces optimales » (deux côtés fléchés de même sommet d'arrivée) sont des triangles distincts, d'où deux inégalités qui donnent \(q \geq \frac{n-4}{2}\).

Solutions

La solution ci-dessous suit la solution officielle de la Shortlist 2025 (une solution et une remarque).

Réponse : \(1011\).

Solution

On traite le cas général : \(\mathcal{P}\) est un \(m\)-gone régulier et il y a exactement \(n\) points sommets d'au moins un triangle de \(\mathcal{T}\) ; on note \(q\) le nombre de quokkalatères. Il s'agit de minimiser \(q\) pour \(n = 2025\) et \(m = 100\).

Décomptes. Les \(n - m\) sommets qui ne sont pas des sommets de \(\mathcal{P}\) sont dits intérieurs, et les arêtes qui ne sont pas des côtés de \(\mathcal{P}\) sont dites intérieures. Sommons les angles de tous les triangles de \(\mathcal{T}\) : chaque sommet intérieur contribue \(360°\) et les sommets de \(\mathcal{P}\) contribuent la somme des angles de \(\mathcal{P}\). Donc

\[|\mathcal{T}| \cdot 180° = (n - m) \cdot 360° + (m - 2) \cdot 180° \implies |\mathcal{T}| = 2n - m - 2.\]

Soit \(e\) le nombre d'arêtes intérieures. En comptant les trois côtés de chaque triangle, chaque côté de \(\mathcal{P}\) est compté une fois et chaque arête intérieure deux fois (double comptage) :

\[3|\mathcal{T}| = m + 2e \implies e = 3n - 2m - 3.\]

Flèches. Soit \(xy\) une arête intérieure, côté des triangles \(xyz\) et \(xyw\).

• Si le quadrilatère \(xzyw\) a un angle intérieur supérieur à \(180°\) (il ne peut en avoir qu'un), ce n'est ni en \(z\) ni en \(w\) (ce sont des angles de triangles), donc c'est en exactement l'un des sommets \(x\), \(y\), disons \(y\). On met alors sur \(xy\) une flèche pointant vers \(y\) ; on dit que \(y\) est la tête de la flèche \(\overrightarrow{xy}\).
• Si \(xzyw\) est convexe, on ne marque pas l'arête \(xy\) : c'est un quokkalatère.

Une flèche \(\overrightarrow{xy}\) signifie que les deux angles en \(y\) adjacents à l'arête \(xy\) ont une somme supérieure à \(180°\). Quelques observations :

1. Comme \(\mathcal{P}\) est convexe, seuls les sommets intérieurs peuvent être têtes de flèches.
2. Si \(y\) est la tête de deux flèches \(\overrightarrow{x_1y}\) et \(\overrightarrow{x_2y}\), alors \(x_1y\) et \(x_2y\) sont deux arêtes consécutives autour de \(y\) ; sinon, les deux paires d'angles en \(y\) séparées par \(x_1y\) et par \(x_2y\) formeraient quatre angles disjoints autour de \(y\) de somme supérieure à \(360°\), ce qui est impossible.
3. Par conséquent, un sommet est la tête d'au plus trois flèches, et s'il est la tête de trois flèches \(\overrightarrow{x_1y}\), \(\overrightarrow{x_2y}\), \(\overrightarrow{x_3y}\), alors \(y\) n'est incident à aucune autre arête.

Soit \(V_k\) l'ensemble des sommets intérieurs qui sont la tête d'exactement \(k\) flèches, \(k = 0, 1, 2, 3\). On a \(|V_3| + |V_2| + |V_1| + |V_0| = n - m\) ; en multipliant par \(3\) et en supprimant certains termes,

\[3|V_3| + 3|V_2| + 2|V_1| \leq 3(n - m). \tag{1}\]

Comme \(e\) est fixé, minimiser le nombre d'arêtes intérieures sans flèche revient à maximiser le nombre de flèches, qui vaut (en comptant les têtes autour de chaque sommet)

\[3|V_3| + 2|V_2| + |V_1|.\]

Faces optimales. Une face optimale est un triangle de \(\mathcal{T}\) dont deux côtés sont des flèches de même tête. Autour de chaque \(v \in V_3\), il y a trois faces optimales, et autour de chaque \(u \in V_2\), une face optimale. Le nombre total de faces optimales est donc \(3|V_3| + |V_2|\), et comme ce sont des triangles de \(\mathcal{T}\) (distincts),

\[3|V_3| + |V_2| \leq |\mathcal{T}| = 2n - m - 2. \tag{2}\]

En additionnant (1) et (2),

\[\left(3|V_3| + 3|V_2| + 2|V_1|\right) + \left(3|V_3| + |V_2|\right) \leq 3(n - m) + (2n - m - 2) \implies 3|V_3| + 2|V_2| + |V_1| \leq \frac{5n - 4m - 2}{2}.\]

Les quokkalatères sont en bijection avec les arêtes intérieures sans flèche, donc

\[q = e - \left(3|V_3| + 2|V_2| + |V_1|\right) \geq (3n - 2m - 3) - \frac{5n - 4m - 2}{2} = \frac{n - 4}{2}.\]

Cette borne, de façon un peu inattendue, ne dépend pas de \(m\). Pour \(n = 2025\), on obtient \(q \geq 1010{,}5\), donc \(q \geq 1011\).

Construction avec \(1011\) quokkalatères. On colore les arêtes, en s'assurant que les arêtes noires sont toutes des flèches. On triangule d'abord \(\mathcal{P} = A_1A_2\ldots A_{100}\) par les \(97\) diagonales bleues issues de \(A_1\) (\(98\) triangles). Dans chaque triangle \(A_1A_iA_{i+1}\) (\(i = 3, 4, \ldots, 99\)), on ajoute un sommet \(v_i\) relié par trois arêtes noires à \(A_1\), \(A_i\) et \(A_{i+1}\) ; on ne mettra pas d'autre point dans ces triangles, donc ces arêtes noires sont des flèches. On ne le fait pas pour \(i = 2\) : il y a pour l'instant \(97\) sommets intérieurs.

Il reste à placer \(2025 - 100 - 97 = 2 \times 914\) sommets dans le triangle \(A_1A_2A_3\). Les transformations affines préservant la convexité, on peut le dessiner équilatéral. On trace un arc convexe de \(A_1\) à \(A_3\) et l'on y choisit, dans l'ordre, \(914\) points \(B_1, B_2, \ldots, B_{914}\). On trace en noir \(A_1B_1, B_1B_2, \ldots, B_{913}B_{914}\), on relie \(A_2\) à chaque \(B_i\) par une arête noire et \(A_3\) à chaque \(B_i\) par une arête bleue. Enfin, on ajoute un point dans chaque triangle \(B_iB_{i+1}A_3\), relié à \(B_i\), \(B_{i+1}\) et \(A_3\), assez près de \(A_3\) pour que \(B_iB_{i+1}\) soit une flèche dirigée vers \(B_{i+1}\) ; de même, on ajoute un point dans le triangle \(A_1B_1A_3\). Par le choix de ces points, chaque arête noire est une flèche. Le nombre de quokkalatères est le nombre d'arêtes bleues, soit \(97 + 914 = 1011\).

La borne étant atteinte, le minimum vaut \(1011\). \(\blacksquare\)

Remarques

Remarque 1. Il existe beaucoup d'autres constructions atteignant \(q = \left\lceil \frac{n-4}{2} \right\rceil\). Pour trouver une triangulation optimale quand \(n \geq 2m - 2\), on cherche à maximiser le nombre de sommets de \(V_2 \cup V_3\) tout en ayant le plus possible de triangles optimaux.

• Pour \(n\) pair, la borne est atteinte par toute construction avec \(V_0 = V_1 = \varnothing\) dans laquelle tous les triangles sont optimaux.
• Pour \(n\) impair, les constructions optimales sont de deux types : soit \(V_0 = V_1 = \varnothing\) et un seul triangle n'est pas optimal ; soit \(V_0 = \varnothing\), \(|V_1| = 1\) et tous les triangles sont optimaux.

Une analyse un peu plus fine des inégalités (1) et (2) montre que les triangulations optimales (pour \(n = 2025\), \(m = 100\)) ont \(|V_2| = 914\) et \(|V_3| = 1011\) (comme dans l'exemple), ou bien \(|V_2| = 912\), \(|V_3| = 1012\) et un sommet dans \(V_1\).