Shortlist 2015, G8¶
Domaine : Géométrie · Difficulté : ★★★★★ · Proposé par : Bulgaria
Concepts : Principe extrémal · Géométrie combinatoire : enveloppe convexe, points du réseau
Solution officielle : Shortlist officielle 2015 (avec solutions), p. 61 (page 62 du 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é¶
A triangulation of a convex polygon \(\Pi\) is a partitioning of \(\Pi\) into triangles by diagonals having no common points other than the vertices of the polygon. We say that a triangulation is a Thaiangulation if all triangles in it have the same area.
Prove that any two different Thaiangulations of a convex polygon \(\Pi\) differ by exactly two triangles. (In other words, prove that it is possible to replace one pair of triangles in the first Thaiangulation with a different pair of triangles so as to obtain the second Thaiangulation.)
Indices : les idées clés
- Principe extrémal : on raisonne sur un contre-exemple ayant le moins de côtés possible.
- Géométrie combinatoire : convexité et somme des angles extérieurs (\(360^\circ\)) d'un polygone convexe ; deux triangles de même aire sur une même base donnent des droites parallèles.
- Lemme 1 : une triangulation ne peut pas contenir deux parallélogrammes.
- Lemme 2 (solution 1) : par une transformation affine, chaque triangle d'une Thaiangulation contient un côté du polygone.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2015 (deux solutions et deux remarques).
Notons \([S]\) l'aire d'un polygone \(S\). Les deux solutions utilisent les observations préliminaires et le lemme 1 ci-dessous.
Solution 1¶
Préliminaires. Toute triangulation d'un \(n\)-gone convexe compte exactement \(n - 2\) triangles. Donc tous les triangles de deux Thaiangulations quelconques de \(\Pi\) ont la même aire. Soit \(T\) une triangulation de \(\Pi\) ; si quatre sommets \(A\), \(B\), \(C\), \(D\) de \(\Pi\) forment un parallélogramme et si \(T\) contient deux triangles dont la réunion est ce parallélogramme, on dit que \(T\) contient le parallélogramme \(ABCD\). Si deux Thaiangulations \(T_1\) et \(T_2\) diffèrent par deux triangles, la réunion de ces triangles est un quadrilatère dont chaque diagonale coupe l'aire en deux, c'est-à-dire un parallélogramme.
Lemme 1. Une triangulation d'un polygone convexe \(\Pi\) ne peut pas contenir deux parallélogrammes.
Preuve. Par l'absurde, supposons qu'une triangulation \(T\) contienne deux parallélogrammes \(P_1\) et \(P_2\). S'ils ont un triangle commun dans \(T\), on peut supposer que \(P_1\) est formé des triangles \(ABC\) et \(ADC\), et \(P_2\) des triangles \(ADC\) et \(CDE\) (voir la figure). Alors \(BC \parallel AD \parallel CE\), donc les sommets \(B\), \(C\), \(E\) de \(\Pi\) sont alignés : absurde.
Supposons maintenant que \(P_1\) et \(P_2\) n'ont aucun triangle commun. Soit \(P_1 = ABCD\). Les côtés \(AB\), \(BC\), \(CD\), \(DA\) découpent \(\Pi\) en plusieurs parties, et \(P_2\) est contenu dans l'une d'elles ; on peut supposer qu'elle est séparée de \(P_1\) par \(AD\). On peut alors nommer \(X\), \(Y\), \(Z\), \(T\) les sommets de \(P_2\) de sorte que le polygone \(ABCDXYZT\) soit convexe (il se peut que \(D = X\) et/ou \(T = A\), mais ce polygone a au moins six sommets). Or la somme de ses angles extérieurs en \(B\), \(C\), \(Y\) et \(Z\) vaut déjà \(360^\circ\) (deux angles consécutifs d'un parallélogramme sont supplémentaires), ce qui est impossible. \(\square\)
Lemme 2. Tout triangle d'une Thaiangulation \(T\) de \(\Pi\) contient un côté de \(\Pi\).
Preuve. Soit \(ABC\) un triangle de \(T\). Appliquons une transformation affine qui envoie \(ABC\) sur un triangle équilatéral \(A'B'C'\) et \(\Pi\) sur \(\Pi'\) ; \(T\) devient une Thaiangulation \(T'\) de \(\Pi'\) (les rapports d'aires sont conservés). Supposons qu'aucun côté de \(A'B'C'\) ne soit un côté de \(\Pi'\). Alors \(T'\) contient d'autres triangles \(A'B'Z\), \(C'A'Y\), \(B'C'X\) sur ces côtés, et \(A'ZB'XC'Y\) est un hexagone convexe (voir la figure). La somme de ses angles extérieurs en \(X\), \(Y\), \(Z\) est inférieure à \(360^\circ\), donc l'un d'eux (disons en \(Z\)) est inférieur à \(120^\circ\), d'où \(\angle A'ZB' > 60^\circ\). Alors \(Z\) est à l'intérieur du disque circonscrit à \(A'B'C'\), et la hauteur \(ZH\) du triangle \(A'B'Z\) est inférieure à \(\frac{\sqrt{3}}{2} A'B'\). Ainsi \([A'B'Z] < [A'B'C']\), et \(T'\) n'est pas une Thaiangulation : contradiction. \(\square\)
La preuve. On appelle oreille d'une triangulation un triangle qui contient deux côtés de \(\Pi\) ; toute triangulation contient au moins une oreille.
Par l'absurde, choisissons (principe extrémal) un polygone convexe \(\Pi\) ayant le moins de côtés possible tel que deux Thaiangulations \(T_1\) et \(T_2\) de \(\Pi\) contredisent l'énoncé (\(\Pi\) a donc au moins cinq côtés). Soit \(ABC\) une oreille de \(T_1\), où \(AC\) est une diagonale de \(\Pi\). Si \(T_2\) contenait aussi \(ABC\), on pourrait découper \(ABC\) et obtenir un polygone ayant moins de côtés qui contredit encore l'énoncé : impossible. Donc \(T_2\) ne contient pas \(ABC\).
\(T_1\) contient un autre triangle de côté \(AC\), disons \(ACD\). Par le lemme 2, il contient un côté de \(\Pi\), donc \(D\) est voisin de \(A\) ou de \(C\) sur le bord de \(\Pi\) ; on peut supposer que \(D\) est voisin de \(C\).
Supposons que \(T_2\) ne contienne pas le triangle \(BCD\). Alors \(T_2\) contient deux triangles distincts \(BCX\) et \(CDY\) (éventuellement \(X = Y\)) ; comme ils n'ont pas de point intérieur commun, le polygone \(ABCDYX\) est convexe (voir la figure). Mais \([ABC] = [BCX]\) et \([ACD] = [CDY]\) donnent \(AX \parallel BC\) et \(AY \parallel CD\), ce qui est impossible. Donc \(T_2\) contient \(BCD\).
Par conséquent \([ABD] = [ABC] + [ACD] - [BCD] = [ABC]\), et \(ABCD\) est un parallélogramme contenu dans \(T_1\). Soit \(T'\) la Thaiangulation obtenue à partir de \(T_1\) en remplaçant la diagonale \(AC\) par \(BD\) ; \(T'\) est distincte de \(T_2\) (sinon \(T_1\) et \(T_2\) différeraient par deux triangles). De plus, \(T'\) et \(T_2\) ont l'oreille \(BCD\) en commun. En découpant cette oreille, la minimalité montre que \(T_2\) et \(T'\) diffèrent par deux triangles formant un parallélogramme différent de \(ABCD\). Ainsi \(T'\) contient deux parallélogrammes, ce qui contredit le lemme 1. \(\blacksquare\)
Solution 2¶
On utilise les observations préliminaires et le lemme 1 de la solution 1.
Par l'absurde, choisissons un polygone convexe \(\Pi\) ayant le moins de côtés possible tel que deux Thaiangulations \(T_1\) et \(T_2\) de \(\Pi\) contredisent l'énoncé (\(\Pi\) a au moins cinq côtés). Supposons que \(T_1\) et \(T_2\) aient une diagonale commune \(d\) qui coupe \(\Pi\) en deux polygones plus petits \(\Pi_1\) et \(\Pi_2\). L'énoncé étant vrai pour eux, les Thaiangulations induites sur chaque \(\Pi_i\) diffèrent par deux triangles formant un parallélogramme (elles ne peuvent pas coïncider, sinon \(T_1\) et \(T_2\) différeraient d'au plus deux triangles). Mais ces deux parallélogrammes sont contenus dans \(T_1\), ce qui contredit le lemme 1. Donc \(T_1\) et \(T_2\) n'ont aucune diagonale commune, et donc aucun triangle commun.
Cas 1 : un sommet \(B\) de \(\Pi\) est extrémité d'une diagonale de \(T_1\) et d'une diagonale de \(T_2\). Soient \(A\) et \(C\) les voisins de \(B\). Alors \(T_1\) contient des triangles \(ABX\) et \(BCY\), et \(T_2\) des triangles \(ABX'\) et \(BCY'\). Certains des points \(X\), \(X'\), \(Y\), \(Y'\) peuvent coïncider, mais d'après l'hypothèse et l'absence de triangle commun, les quatre triangles \(ABX\), \(BCY\), \(ABX'\), \(BCY'\) sont distincts.
Comme \([ABX] = [BCY] = [ABX'] = [BCY']\), on a \(XX' \parallel AB\) et \(YY' \parallel BC\). Si \(X = Y\), alors \(X'\) et \(Y'\) sont sur deux droites différentes passant par \(X\) et distincts de \(X\), donc \(X' \neq Y'\) ; on peut alors échanger les rôles des deux Thaiangulations. On suppose donc désormais \(X \neq Y\).
Dans le pentagone convexe \(ABCYX\), on a \(\angle BAX + \angle AXY > 180^\circ\) ou \(\angle XYC + \angle YCB > 180^\circ\) (ou les deux) ; par symétrie, on suppose la première inégalité. Soit \(r\) la demi-droite issue de \(X\) de même sens que \(\overrightarrow{AB}\) ; l'inégalité montre que \(r\) pointe vers l'intérieur du pentagone (donc de \(\Pi\)). La demi-droite opposée pointe hors de \(\Pi\), donc \(X'\) est sur \(r\) ; de plus \(X'\) est sur l'« arc » \(CY\) de \(\Pi\) ne contenant pas \(X\). Les segments \(XX'\) et \(YB\) se coupent donc (voir la figure).
Soit \(O\) l'intersection des demi-droites \(r\) et \([BC)\). Comme les triangles \(ABX'\) et \(BCY'\) n'ont pas de point intérieur commun, \(Y'\) doit être sur l'« arc » \(CX'\), situé dans le triangle \(XBO\). La droite \(YY'\) coupe donc deux côtés du triangle \(XBO\), et aucun d'eux ne peut être \(XB\) (sinon les diagonales \(XB\) et \(YY'\) se couperaient). Donc \(YY'\) coupe \(BO\), ce qui contredit \(YY' \parallel BC\).
Cas 2 : chaque sommet de \(\Pi\) est extrémité de diagonales d'au plus une des deux triangulations. Une triangulation ne peut pas avoir deux sommets consécutifs dont ne part aucune diagonale. Donc les sommets de \(\Pi\) émettent des diagonales alternativement dans \(T_1\) et dans \(T_2\) ; en particulier \(\Pi\) a un nombre pair de côtés, donc au moins six.
On peut choisir cinq sommets consécutifs \(A\), \(B\), \(C\), \(D\), \(E\) de \(\Pi\) tels que
Il suffit de choisir trois sommets consécutifs \(B\), \(C\), \(D\) dont la somme des angles extérieurs est au plus \(180^\circ\), ce qui est possible puisque \(\Pi\) a au moins six côtés.
On peut supposer que \(T_1\) n'a pas de diagonale issue de \(B\) ni de \(D\) (donc contient les triangles \(ABC\) et \(CDE\)), tandis que \(T_2\) n'a pas de diagonale issue de \(A\), \(C\), \(E\) (donc contient le triangle \(BCD\)). Comme \([ABC] = [BCD] = [CDE]\), on a \(AD \parallel BC\) et \(BE \parallel CD\) (voir la figure). Par (2), \(AD > BC\) et \(BE > CD\). Soient \(X = AC \cap BD\) et \(Y = CE \cap BD\) ; ces inégalités donnent \(AX > CX\) et \(EY > CY\).
Enfin, \(T_2\) contient aussi un triangle \(BDZ\) avec \(Z \neq C\) ; la demi-droite \([CZ)\) est alors dans l'angle \(\angle ACE\). Comme \([BCD] = [BDZ]\), la diagonale \(BD\) coupe \(CZ\) en son milieu. Avec les inégalités précédentes, cela montre que \(Z\) est à l'intérieur du triangle \(ACE\) (et distinct de \(A\) et \(E\)), ce qui est impossible pour un sommet de \(\Pi\). Contradiction finale. \(\blacksquare\)
Remarques¶
Remarque 1 (lien avec l'inégalité d'Erdős–Debrunner). Le lemme 2 équivaut à l'inégalité d'Erdős–Debrunner : pour tout triangle \(PQR\) et des points \(A\), \(B\), \(C\) sur les côtés \(QR\), \(RP\), \(PQ\),
Pour déduire (1) du lemme 2, on suppose (1) fausse et on choisit \(X\), \(Y\), \(Z\) à l'intérieur des triangles \(BCP\), \(CAQ\), \(ABR\) avec \([ABC] = [ABZ] = [BCX] = [CAY]\) ; l'hexagone convexe \(AZBXCY\) a alors une Thaiangulation contenant \(ABC\), ce qui contredit le lemme 2. Réciproquement, si une Thaiangulation contient un triangle \(ABC\) sans côté de \(\Pi\), avec les triangles voisins \(ABZ\), \(AYC\), \(XBC\), l'hexagone \(AZBXCY\) est convexe ; les parallèles à \(YZ\), \(ZX\), \(XY\) passant par \(A\), \(B\), \(C\) forment un triangle \(X'Y'Z'\) semblable à \(XYZ\), et (1) donne
donc ce n'est pas une Thaiangulation.
Remarque 2. Le cas 2 peut aussi se traiter avec le lemme 2 : une triangulation d'un \(n\)-gone a \(n - 2\) triangles, dont aucun ne contient trois côtés de \(\Pi\) ; le lemme 2 entraîne donc que chaque Thaiangulation contient exactement deux oreilles. Mais chaque sommet de \(\Pi\) est sommet d'une oreille de \(T_1\) ou de \(T_2\), donc \(\Pi\) aurait au plus quatre sommets.