Shortlist 2016, C5

Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : non indiqué

Concepts : Géométrie combinatoire : enveloppe convexe, points du réseau · Principe extrémal · Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2016 (avec solutions), p. 36 (page 39 du PDF)

Figures reprises du livret officiel de la Shortlist.

Énoncé

Let \(n \geq 3\) be a positive integer. Find the maximum number of diagonals of a regular \(n\)-gon one can select, so that any two of them do not intersect in the interior or they are perpendicular to each other.

Indices : les idées clés

• Cas impair : deux diagonales ne sont jamais perpendiculaires (sinon le polygone contiendrait deux points diamétralement opposés), donc les diagonales choisies ne se coupent pas.
• Géométrie combinatoire : enveloppe convexe, points du réseau : des diagonales qui ne se coupent pas découpent le polygone en au plus \(n - 2\) triangles, donc il y en a au plus \(n - 3\).
• Principe extrémal : les extrémités de la plus longue diagonale choisie dans chaque direction ne sont extrémités d'aucune autre diagonale de cette direction.
• Découpage en groupes de sommets consécutifs (solution 1) : les diagonales hors de \(S\) restent dans un même groupe, situé d'un même côté d'un diamètre.
• Récurrence et constructions récursives (solution 2) : récurrence sur le nombre de côtés d'un polygone inscrit, en coupant le long d'une diagonale qui n'en coupe aucune autre.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2016 (deux solutions).

Réponse. Le maximum vaut \(n - 2\) si \(n\) est pair et \(n - 3\) si \(n\) est impair.

Solution 1

On distingue deux cas selon la parité de \(n\).

Cas 1 : \(n\) impair. Montrons d'abord qu'aucune paire de diagonales n'est perpendiculaire. Supposons que \(A\), \(B\), \(C\), \(D\) soient des sommets avec \((AB) \perp (CD)\), et soit \(E\) le sommet situé sur la médiatrice de \([AB]\) (il existe car \(n\) est impair). Soit \(E'\) le point diamétralement opposé à \(E\) sur le cercle circonscrit. La droite \((EE')\) est perpendiculaire à \((AB)\), donc parallèle à \((CD)\) ; par la symétrie d'axe la médiatrice de \([CD]\) (un diamètre), on a \(EC = E'D\). Comme \(C\), \(D\), \(E\) sont des sommets du polygone régulier, \(E'\) doit aussi être un sommet du polygone. Cela contredit le fait qu'un polygone régulier ayant un nombre impair de sommets ne contient pas deux points diamétralement opposés.

Dans le cas impair, on ne peut donc choisir que des diagonales qui ne se coupent pas. Dans le cas maximal, ces diagonales découpent le \(n\)-gone régulier en \(n - 2\) triangles (géométrie combinatoire : triangulation d'un polygone convexe), donc on peut en choisir au plus \(n - 3\). C'est réalisable, par exemple en choisissant toutes les diagonales issues d'un même sommet.

Cas 2 : \(n\) pair. S'il n'y a aucune intersection, l'argument du cas impair s'applique. Supposons donc que deux diagonales perpendiculaires aient été choisies. Soit \(S\) l'ensemble des diagonales choisies parallèles à l'une d'elles et qui coupent au moins une autre diagonale choisie. Supposons que \(S\) contienne \(k\) diagonales, et que ces \(k\) diagonales aient \(l\) extrémités distinctes au total.

Considérons d'abord, par le principe extrémal, la plus longue diagonale de \(S\) dans l'une des deux directions. Aucune autre diagonale de \(S\) ne peut partir de l'une de ses extrémités, sinon elle devrait couper une autre diagonale de \(S\) plus longue. Il en va de même dans l'autre direction. En mettant de côté ces deux plus longues diagonales et leurs quatre extrémités, les \(k - 2\) diagonales restantes ont leurs extrémités parmi \(l - 4\) sommets, chacun étant extrémité d'au plus deux diagonales de \(S\) (une par direction). Cela donne \(2(l - 4) \geq 2(k - 2)\), donc

\[k \leq l - 2.\]

Considérons un groupe de sommets consécutifs du \(n\)-gone tel que les deux sommets extrêmes soient des extrémités de diagonales de \(S\), et les sommets intérieurs non. Il y a \(l\) tels groupes, que l'on note \(P_1, P_2, \ldots, P_l\) dans l'ordre. Montrons que toute diagonale choisie hors de \(S\) relie deux sommets d'un même groupe \(P_i\). Soit \(d\) une diagonale reliant des sommets de groupes distincts \(P_i\) et \(P_j\). Soient \(d_1\) et \(d_2\) deux diagonales de \(S\) ayant chacune pour extrémité l'un des sommets extrêmes de \(P_i\). Alors \(d\) doit couper \(d_1\), \(d_2\), ou une diagonale de \(S\) perpendiculaire à \(d_1\) et à \(d_2\). Dans tous les cas, \(d\) coupe une diagonale de \(S\), donc lui est perpendiculaire, et devrait donc appartenir à \(S\) par définition : contradiction.

À l'intérieur d'un même groupe \(P_i\), il n'y a pas de diagonales perpendiculaires, car les sommets sont d'un même côté d'un diamètre du cercle circonscrit. Il y a donc au plus \(|P_i| - 2\) diagonales choisies à l'intérieur de \(P_i\), y compris celle qui relie les deux sommets extrêmes de \(P_i\) lorsque \(|P_i| > 2\). Comme chaque extrémité de diagonale de \(S\) appartient à exactement deux groupes, \(\sum_{i=1}^l |P_i| = n + l\). Le nombre de diagonales choisies est donc au plus

\[\sum_{i=1}^{l} (|P_i| - 2) + k = \sum_{i=1}^{l} |P_i| - 2l + k = (n + l) - 2l + k = n - l + k \leq n - 2.\]

Cette borne est atteinte. Prenons un sommet \(A\) et soit \(A'\) le sommet tel que \([AA']\) soit un diamètre du cercle circonscrit. Choisissons toutes les diagonales issues de \(A\), ainsi que la diagonale \(d'\) reliant les deux voisins de \(A'\). Alors la seule paire de diagonales qui se coupent est \(\{AA', d'\}\), et ces deux diagonales sont perpendiculaires. Au total, on a choisi \((n - 3) + 1 = n - 2\) diagonales.

Le maximum est donc \(n - 2\) si \(n\) est pair et \(n - 3\) si \(n\) est impair. \(\blacksquare\)

Solution 2

Les constructions et le cas impair sont les mêmes que dans la solution 1. Au lieu de traiter à part le cas pair, on démontre plus généralement, par récurrence, qu'on peut choisir au plus \(n - 2\) diagonales dans tout \(n\)-gone inscrit dans un cercle \(\Gamma\).

Le cas \(n = 3\) est évident puisqu'il n'y a aucune diagonale. Supposons la borne vraie pour tout polygone inscrit ayant moins de \(n\) côtés. Pour un \(n\)-gone inscrit, s'il existe une diagonale choisie qui ne coupe aucune autre diagonale choisie, elle partage le \(n\)-gone en un \(m\)-gone et un \(l\)-gone (avec \(m + l = n + 2\)), et chaque autre diagonale choisie appartient à l'un des deux. Sans perte de généralité, le \(m\)-gone est situé d'un même côté d'un diamètre de \(\Gamma\). Alors deux diagonales choisies du \(m\)-gone ne peuvent pas être perpendiculaires, donc ne se coupent pas, et on en choisit au plus \(m - 3\). On applique l'hypothèse de récurrence au \(l\)-gone. Le nombre de diagonales choisies est donc au plus \((m - 3) + (l - 2) + 1 = n - 2\).

Il reste le cas où chaque diagonale choisie coupe au moins une autre diagonale choisie. Considérons deux diagonales choisies perpendiculaires \(d_1\), \(d_2\). Elles découpent le cercle \(\Gamma\) en quatre arcs, chacun situé d'un même côté d'un diamètre de \(\Gamma\). S'il y avait deux diagonales choisies qui se coupent, dont aucune n'est parallèle à \(d_1\) ou à \(d_2\), elles ne couperaient ni \(d_1\) ni \(d_2\), donc leurs extrémités appartiendraient au même arc déterminé par \(d_1\), \(d_2\), et elles ne pourraient pas être perpendiculaires : cela contredirait la condition. Donc toutes les diagonales choisies sont parallèles à \(d_1\) ou à \(d_2\).

Prenons la plus longue diagonale choisie dans l'une des deux directions (principe extrémal). Comme dans la solution 1, ses extrémités n'appartiennent à aucune autre diagonale choisie ; de même pour la plus longue diagonale dans l'autre direction. En dehors de ces quatre extrémités, chacun des \(n - 4\) autres sommets appartient à au plus deux diagonales choisies. On peut donc choisir au plus

\[\frac{1}{2}\big(2(n - 4) + 4\big) = n - 2\]

diagonales, ce qui achève la récurrence. \(\blacksquare\)