Shortlist 2006, G10¶
Domaine : Géométrie · Difficulté : ★★★★★ · Proposé par : Serbia
Concepts : Géométrie combinatoire : enveloppe convexe, points du réseau · Coordonnées et nombres complexes
Solution officielle : Shortlist officielle 2006 (avec solutions), p. 51 (page 52 du PDF)
Problème 6 de l'OIM 2006
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2006, où il était le problème 6 (jour 2).
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é¶
To each side \(a\) of a convex polygon we assign the maximum area of a triangle contained in the polygon and having \(a\) as one of its sides. Show that the sum of the areas assigned to all sides of the polygon is not less than twice the area of the polygon.
Indices : les idées clés
- Lemme : un \((2n)\)-gone convexe d'aire \(S\) a un côté et un sommet formant un triangle d'aire au moins \(S/n\) ; les triangles \(\Delta_b\) définis par les diagonales principales recouvrent le polygone.
- Approximation rationnelle : si \(\sum S_i/S < 2\), on choisit \(q_i = k_i/n > S_i/S\) avec \(\sum k_i = 2n\), on découpe chaque côté \(a_i\) en \(k_i\) morceaux et l'on applique le lemme.
- Solution 2 : le polygone associé \(Q\), centralement symétrique, de vecteurs côtés \(\pm\overrightarrow{A_iA_{i+1}}\), vérifie \([Q] = 2\sum S_i\) et \([Q] \geq 4[P]\) (récurrence sur le nombre de directions de côtés).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2006 (deux solutions). C'est le problème 6 de l'OIM 2006.
Solution 1¶
Lemme. Tout \((2n)\)-gone convexe d'aire \(S\) a un côté et un sommet qui forment ensemble un triangle d'aire au moins \(S/n\).
Preuve. On appelle diagonales principales du \((2n)\)-gone celles qui le partagent en deux polygones ayant le même nombre de côtés. Pour tout côté \(b\) du \((2n)\)-gone, notons \(\Delta_b\) le triangle \(ABP\), où \(A\), \(B\) sont les extrémités de \(b\) et \(P\) le point d'intersection des diagonales principales \(AA'\), \(BB'\). Montrons que la réunion des triangles \(\Delta_b\), sur tous les côtés, recouvre tout le polygone.
Pour cela, choisissons un côté \(AB\) quelconque et considérons la diagonale principale \(AA'\) comme un segment orienté. Soit \(X\) un point quelconque du polygone, sur aucune diagonale principale. Pour fixer les idées, supposons que \(X\) soit à gauche de la demi-droite \(AA'\). Considérons la suite des diagonales principales \(AA', BB', CC', \ldots\), où \(A, B, C, \ldots\) sont des sommets consécutifs, situés à droite de \(AA'\).
Le \(n\)-ième terme de cette suite est la diagonale \(A'A\) (c'est-à-dire \(AA'\) retournée), qui a \(X\) à sa droite. Il existe donc deux sommets consécutifs \(K\), \(L\) de la suite \(A, B, C, \ldots\) avant \(A'\) tels que \(X\) soit encore à gauche de \(KK'\) mais à droite de \(LL'\). Cela signifie que \(X\) est dans le triangle \(\Delta_{\ell'}\), où \(\ell' = K'L'\). Un raisonnement analogue s'applique aux points \(X\) situés à droite de \(AA'\) (les points situés sur les diagonales principales peuvent être ignorés sans risque). Les triangles \(\Delta_b\) recouvrent donc bien tout le polygone.
La somme de leurs aires est au moins \(S\). On peut donc trouver deux côtés opposés, disons \(b = AB\) et \(b' = A'B'\) (avec \(AA'\), \(BB'\) diagonales principales), tels que \([\Delta_b] + [\Delta_{b'}] \geq S/n\), où \([\cdots]\) désigne l'aire d'une région. Soit \(P\) le point d'intersection de \(AA'\) et \(BB'\) ; supposons sans perte de généralité que \(PB \geq PB'\). Alors
ce qui prouve le lemme. \(\square\)
Soit maintenant \(\mathcal{P}\) un polygone convexe quelconque, d'aire \(S\), à \(m\) côtés \(a_1, \ldots, a_m\). Soit \(S_i\) l'aire du plus grand triangle de \(\mathcal{P}\) ayant \(a_i\) pour côté. Supposons, contrairement à l'énoncé, que
Il existe alors des rationnels \(q_1, \ldots, q_m\) tels que \(\sum q_i = 2\) et \(q_i > S_i/S\) pour tout \(i\). Soit \(n\) un dénominateur commun des \(m\) fractions \(q_1, \ldots, q_m\). Écrivons \(q_i = k_i/n\) ; ainsi \(\sum k_i = 2n\). Découpons chaque côté \(a_i\) de \(\mathcal{P}\) en \(k_i\) segments égaux, ce qui crée un \((2n)\)-gone convexe d'aire \(S\) (avec certains angles égaux à \(180^\circ\)), auquel on applique le lemme. Ce polygone raffiné a donc un côté \(b\) et un sommet \(H\) formant un triangle \(T\) d'aire \([T] \geq S/n\). Si \(b\) est un morceau du côté \(a_i\) de \(\mathcal{P}\), alors le triangle \(W\) de base \(a_i\) et de sommet \(H\) a pour aire
ce qui contredit la définition de \(S_i\). Cela termine la preuve. \(\blacksquare\)
Solution 2¶
Comme dans la première solution, on autorise de nouveau des angles de \(180^\circ\) en certains sommets des polygones convexes considérés.
À chaque \(n\)-gone convexe \(\mathcal{P} = A_1A_2 \ldots A_n\), on associe un \((2n)\)-gone convexe \(\mathcal{Q}\) centralement symétrique, de vecteurs côtés \(\pm\overrightarrow{A_iA_{i+1}}\), \(1 \leq i \leq n\). La construction est la suivante. On place les \(2n\) vecteurs \(\pm\overrightarrow{A_iA_{i+1}}\) en une origine commune et on les note \(\vec{b}_1, \vec{b}_2, \ldots, \vec{b}_{2n}\) dans le sens direct ; le choix du premier vecteur \(\vec{b}_1\) n'importe pas. L'ordre de numérotation est bien défini si \(\mathcal{P}\) n'a ni côtés parallèles ni angles de \(180^\circ\). Sinon, plusieurs vecteurs colinéaires de même sens sont numérotés consécutivement \(\vec{b}_j, \vec{b}_{j+1}, \ldots, \vec{b}_{j+r}\). On peut supposer que, dans ces cas, les vecteurs opposés apparaissent dans l'ordre \(-\vec{b}_j, -\vec{b}_{j+1}, \ldots, -\vec{b}_{j+r}\), ce qui garantit \(\vec{b}_{j+n} = -\vec{b}_j\) pour \(j = 1, \ldots, 2n\). Les indices sont pris cycliquement ici et dans les situations analogues ci-dessous.
Choisissons des points \(B_1, B_2, \ldots, B_{2n}\) tels que \(\overrightarrow{B_jB_{j+1}} = \vec{b}_j\) pour \(j = 1, \ldots, 2n\). La ligne polygonale \(\mathcal{Q} = B_1B_2 \ldots B_{2n}\) est fermée, puisque \(\sum_{j=1}^{2n}\vec{b}_j = \vec{0}\). De plus, \(\mathcal{Q}\) est un \((2n)\)-gone convexe grâce à la disposition des vecteurs \(\vec{b}_j\), avec éventuellement des angles de \(180^\circ\). Les vecteurs côtés de \(\mathcal{Q}\) sont \(\pm\overrightarrow{A_iA_{i+1}}\), \(1 \leq i \leq n\). En particulier, \(\mathcal{Q}\) est centralement symétrique, puisqu'il contient comme vecteurs côtés \(\overrightarrow{A_iA_{i+1}}\) et \(-\overrightarrow{A_iA_{i+1}}\) pour tout \(i = 1, \ldots, n\). Remarquons que \(B_jB_{j+1}\) et \(B_{j+n}B_{j+n+1}\) sont des côtés opposés de \(\mathcal{Q}\), \(1 \leq j \leq n\). On appelle \(\mathcal{Q}\) l'associé de \(\mathcal{P}\).
Soit \(S_i\) l'aire maximale d'un triangle de \(\mathcal{P}\) de côté \(A_iA_{i+1}\), \(1 \leq i \leq n\). Prouvons que
et
Il est clair que (1) et (2) impliquent la conclusion du problème.
Lemme. Pour un côté \(A_iA_{i+1}\) de \(\mathcal{P}\), soit \(h_i\) la distance maximale d'un point de \(\mathcal{P}\) à la droite \(A_iA_{i+1}\), \(i = 1, \ldots, n\). Notons \(B_jB_{j+1}\) le côté de \(\mathcal{Q}\) tel que \(\overrightarrow{A_iA_{i+1}} = \overrightarrow{B_jB_{j+1}}\). Alors la distance entre \(B_jB_{j+1}\) et son côté opposé dans \(\mathcal{Q}\) vaut \(2h_i\).
Preuve. Choisissons un sommet \(A_k\) de \(\mathcal{P}\) à distance \(h_i\) de la droite \(A_iA_{i+1}\). Soit \(u\) le vecteur unitaire perpendiculaire à \(A_iA_{i+1}\) et dirigé vers l'intérieur de \(\mathcal{P}\). En notant \(x \cdot y\) le produit scalaire des vecteurs \(x\) et \(y\), on a
Dans \(\mathcal{Q}\), la distance \(H_i\) entre les côtés opposés \(B_jB_{j+1}\) et \(B_{j+n}B_{j+n+1}\) est donnée par
Le choix du sommet \(A_k\) implique que les \(n\) vecteurs consécutifs \(\vec{b}_j, \vec{b}_{j+1}, \ldots, \vec{b}_{j+n-1}\) sont exactement \(\overrightarrow{A_iA_{i+1}}, \ldots, \overrightarrow{A_{k-1}A_k}\) et \(\overrightarrow{A_iA_{i-1}}, \ldots, \overrightarrow{A_{k+1}A_k}\), pris dans un certain ordre. Cela implique \(H_i = 2h_i\). \(\square\)
Pour prouver (1), appliquons le lemme à chaque côté de \(\mathcal{P}\). Si \(O\) est le centre de \(\mathcal{Q}\), alors, avec les notations du lemme,
La somme sur tous les côtés de \(\mathcal{P}\) donne (1).
Posons \(d(\mathcal{P}) = [\mathcal{Q}] - 4[\mathcal{P}]\) pour un polygone convexe \(\mathcal{P}\) d'associé \(\mathcal{Q}\). L'inégalité (2) signifie que \(d(\mathcal{P}) \geq 0\) pour tout polygone convexe \(\mathcal{P}\). Prouvons cette dernière inégalité par récurrence sur le nombre \(\ell\) de directions de côtés de \(\mathcal{P}\), c'est-à-dire le nombre de droites deux à deux non parallèles contenant chacune un côté de \(\mathcal{P}\).
On commence la récurrence avec \(\ell = 1\) comme cas de base, ce qui signifie qu'on autorise certains polygones dégénérés. Plus précisément, on considère comme polygones convexes dégénérés toutes les lignes polygonales fermées de la forme \(X_1X_2 \ldots X_kY_1Y_2 \ldots Y_mX_1\), où \(X_1, X_2, \ldots, X_k\) sont des points dans cet ordre sur un segment \(X_1Y_1\), de même que \(Y_m, Y_{m-1}, \ldots, Y_1\). La construction initiale s'applique aux polygones dégénérés ; leurs associés sont aussi dégénérés, et la valeur de \(d\) est nulle. Pour l'hérédité, considérons un polygone convexe \(\mathcal{P}\) ayant \(\ell\) directions de côtés, en supposant \(d(\mathcal{P}) \geq 0\) pour les polygones ayant une valeur de \(\ell\) plus petite.
Supposons d'abord que \(\mathcal{P}\) ait une paire de côtés parallèles, c'est-à-dire des côtés sur des droites parallèles distinctes. Soient \(A_iA_{i+1}\) et \(A_jA_{j+1}\) une telle paire, avec \(A_iA_{i+1} \leq A_jA_{j+1}\). Retirons de \(\mathcal{P}\) le parallélogramme \(R\) défini par les vecteurs \(\overrightarrow{A_iA_{i+1}}\) et \(\overrightarrow{A_iA_{j+1}}\). On obtient ainsi deux polygones. En translatant l'un d'eux du vecteur \(\overrightarrow{A_iA_{i+1}}\), on obtient un nouveau polygone convexe \(\mathcal{P}'\), d'aire \([\mathcal{P}] - [R]\) et de valeur de \(\ell\) au plus celle de \(\mathcal{P}\). On appelle cette construction l'opération A.
L'associé de \(\mathcal{P}'\) s'obtient à partir de \(\mathcal{Q}\) en diminuant les longueurs de deux côtés opposés de \(2A_iA_{i+1}\). D'après le lemme, la distance entre ces côtés opposés est le double de la distance entre \(A_iA_{i+1}\) et \(A_jA_{j+1}\). L'opération A diminue donc \([\mathcal{Q}]\) de l'aire d'un parallélogramme de base et de hauteur doubles de celles de \(R\), c'est-à-dire de \(4[R]\). Donc A laisse la différence \(d(\mathcal{P}) = [\mathcal{Q}] - 4[\mathcal{P}]\) inchangée.
Maintenant, si \(\mathcal{P}'\) a aussi une paire de côtés parallèles, on lui applique l'opération A. On continue ainsi avec les polygones obtenus tant que c'est possible. L'opération A diminue le nombre \(p\) de paires de côtés parallèles de \(\mathcal{P}\). Ses applications répétées réduisent donc \(p\) à \(0\), et de nouvelles applications de A deviennent impossibles après un certain nombre d'étapes. Pour plus de clarté, notons encore \(\mathcal{P}\) le polygone obtenu à ce stade.
L'hérédité est terminée si \(\mathcal{P}\) est dégénéré. Sinon, \(\ell > 1\) et \(p = 0\), c'est-à-dire que \(\mathcal{P}\) n'a pas de côtés parallèles. Remarquons qu'alors \(\ell \geq 3\). En effet, \(\ell = 2\) signifie que les sommets de \(\mathcal{P}\) sont tous sur le bord d'un parallélogramme, ce qui implique \(p > 0\).
De plus, comme \(\mathcal{P}\) n'a pas de côtés parallèles, les vecteurs colinéaires consécutifs de la suite \((\vec{b}_k)\) (s'il y en a) correspondent à des angles de \(180^\circ\) consécutifs de \(\mathcal{P}\). En supprimant les sommets de ces angles, on obtient un polygone convexe de même valeur \(d(\mathcal{P})\).
En résumé, si l'opération A est impossible pour un polygone non dégénéré \(\mathcal{P}\), alors \(\ell \geq 3\). De plus, on peut supposer que \(\mathcal{P}\) n'a pas d'angles de \(180^\circ\).
Ces deux dernières conditions sont alors aussi vraies pour l'associé \(\mathcal{Q}\) de \(\mathcal{P}\), et l'on effectue la construction suivante. Comme \(\ell \geq 3\), il existe un côté \(B_jB_{j+1}\) de \(\mathcal{Q}\) tel que la somme des angles en \(B_j\) et \(B_{j+1}\) dépasse \(180^\circ\). (Un tel côté existe dans tout \(k\)-gone convexe pour \(k > 4\).) Naturellement, \(B_{j+n}B_{j+n+1}\) est un côté ayant la même propriété. Prolongeons les paires de côtés \(B_{j-1}B_j\), \(B_{j+1}B_{j+2}\) et \(B_{j+n-1}B_{j+n}\), \(B_{j+n+1}B_{j+n+2}\) jusqu'à leurs intersections \(U\) et \(V\) respectivement. Soit \(\mathcal{Q}'\) le \(2(n + 1)\)-gone convexe centralement symétrique obtenu à partir de \(\mathcal{Q}\) en insérant \(U\) et \(V\) comme nouveaux sommets dans la suite \(B_1, \ldots, B_{2n}\), entre \(B_j\), \(B_{j+1}\) et \(B_{j+n}\), \(B_{j+n+1}\) respectivement. Informellement, on ajoute à \(\mathcal{Q}\) les triangles isométriques \(B_jB_{j+1}U\) et \(B_{j+n}B_{j+n+1}V\). Remarquons que \(B_j\), \(B_{j+1}\), \(B_{j+n}\) et \(B_{j+n+1}\) restent des sommets de \(\mathcal{Q}'\), bien que \(B_jB_{j+1}\) et \(B_{j+n}B_{j+n+1}\) n'en soient plus des côtés.
Soit \(A_iA_{i+1}\) le côté de \(\mathcal{P}\) tel que \(\overrightarrow{A_iA_{i+1}} = \overrightarrow{B_jB_{j+1}} = \vec{b}_j\). Considérons le point \(W\) tel que le triangle \(A_iA_{i+1}W\) soit isométrique au triangle \(B_jB_{j+1}U\) et extérieur à \(\mathcal{P}\). Insérons \(W\) dans la suite \(A_1, A_2, \ldots, A_n\) comme nouveau sommet entre \(A_i\) et \(A_{i+1}\) pour obtenir un \((n + 1)\)-gone \(\mathcal{P}'\). Montrons que \(\mathcal{P}'\) est convexe et que son associé est \(\mathcal{Q}'\).
Les vecteurs \(\overrightarrow{A_iW}\) et \(\vec{b}_{j-1}\) sont colinéaires et de même sens, de même que les vecteurs \(\overrightarrow{WA_{i+1}}\) et \(\vec{b}_{j+1}\). Comme \(\vec{b}_{j-1}\), \(\vec{b}_j\), \(\vec{b}_{j+1}\) sont des termes consécutifs de la suite \((\vec{b}_k)\), les inégalités d'angles \(\measuredangle(\vec{b}_{j-1}, \vec{b}_j) \leq \measuredangle(\overrightarrow{A_{i-1}A_i}, \vec{b}_j)\) et \(\measuredangle(\vec{b}_j, \vec{b}_{j+1}) \leq \measuredangle(\vec{b}_j, \overrightarrow{A_{i+1}A_{i+2}})\) sont vraies. Elles montrent que \(\mathcal{P}'\) est un polygone convexe. Pour construire son associé, il faut supprimer les vecteurs \(\pm\overrightarrow{A_iA_{i+1}} = \pm\vec{b}_j\) de la suite \((\vec{b}_k)\) définissant \(\mathcal{Q}\), et insérer convenablement les vecteurs \(\pm\overrightarrow{A_iW}\), \(\pm\overrightarrow{WA_{i+1}}\). On peut le faire ainsi :
Cette suite mise à jour produit \(\mathcal{Q}'\) comme associé de \(\mathcal{P}'\).
Il découle de la construction que \([\mathcal{P}'] = [\mathcal{P}] + [A_iA_{i+1}W]\) et \([\mathcal{Q}'] = [\mathcal{Q}] + 2[A_iA_{i+1}W]\). Donc \(d(\mathcal{P}') = d(\mathcal{P}) - 2[A_iA_{i+1}W] < d(\mathcal{P})\).
Pour terminer la récurrence, il reste à remarquer que la valeur de \(\ell\) pour \(\mathcal{P}'\) est inférieure à celle de \(\mathcal{P}\). En effet, le côté \(A_iA_{i+1}\) a été retiré. Les nouveaux côtés \(A_iW\) et \(WA_{i+1}\) n'introduisent pas de nouvelles directions : chacun est parallèle à un côté de \(\mathcal{P}\) ou situé sur la droite portant un tel côté. Par hypothèse de récurrence, \(d(\mathcal{P}') \geq 0\), donc \(d(\mathcal{P}) > d(\mathcal{P}') \geq 0\). La preuve est complète. \(\blacksquare\)