Shortlist 2006, C2¶

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

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

Solution officielle : Shortlist officielle 2006 (avec solutions), p. 21 (page 22 du PDF)

Problème 2 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 2 (jour 1).

Énoncé¶

A diagonal of a regular \(2006\)-gon is called odd if its endpoints divide the boundary into two parts, each composed of an odd number of sides. Sides are also regarded as odd diagonals.

Suppose the \(2006\)-gon has been dissected into triangles by \(2003\) nonintersecting diagonals. Find the maximum possible number of isosceles triangles with two odd sides.

Indices : les idées clés

Lemme : si une diagonale découpe une partie \(L\) du bord formée de \(n\) côtés, le nombre de triangles isocèles impairs dont les sommets sont sur \(L\) est au plus \(n/2\) (récurrence avec la plus longue diagonale \(PQ\)).
Conclusion : avec la plus longue diagonale de la triangulation, on découpe le bord en trois morceaux, d'où au plus \(1003\) triangles.
Solution 2 : à chaque triangle isocèle impair, on attribue deux côtés du polygone qui n'appartiennent à aucun autre (géométrie combinatoire) ; l'exemple « une diagonale sur deux » atteint \(1003\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2006 (deux solutions). C'est le problème 2 de l'OIM 2006.

Solution 1¶

Réponse : \(1003\).

On appelle impair un triangle isocèle ayant deux côtés impairs. Supposons donnée une triangulation comme dans l'énoncé. Un triangle de la triangulation qui est impair et isocèle sera appelé, pour abréger, iso-impair.

Lemme. Soit \(AB\) l'une des diagonales de la triangulation, et soit \(L\) la plus courte des deux parties du bord du \(2006\)-gone d'extrémités \(A\), \(B\). Supposons que \(L\) soit formée de \(n\) segments. Alors le nombre de triangles iso-impairs dont les sommets sont sur \(L\) ne dépasse pas \(n/2\).

Preuve. C'est évident pour \(n = 2\). Prenons \(n\) avec \(2 < n \leq 1003\), et supposons l'affirmation vraie pour toute partie \(L\) de longueur inférieure à \(n\). Soit maintenant \(L\) (d'extrémités \(A\), \(B\)) formée de \(n\) segments. Soit \(PQ\) la plus longue diagonale qui est un côté d'un triangle iso-impair \(PQS\) dont tous les sommets sont sur \(L\) (s'il n'y a pas de tel triangle, il n'y a rien à prouver). Tout triangle dont les sommets sont sur \(L\) est obtusangle ou rectangle ; donc \(S\) est le sommet principal de \(PQS\). On peut supposer que les cinq points \(A\), \(P\), \(S\), \(Q\), \(B\) sont sur \(L\) dans cet ordre et découpent \(L\) en quatre morceaux \(L_{AP}\), \(L_{PS}\), \(L_{SQ}\), \(L_{QB}\) (ceux des extrémités pouvant se réduire à un point).

Par définition de \(PQ\), un triangle iso-impair ne peut pas avoir de sommets à la fois sur \(L_{AP}\) et sur \(L_{QB}\). Chaque triangle iso-impair dans \(L\) a donc tous ses sommets sur un seul des quatre morceaux. En appliquant l'hypothèse de récurrence à chacun de ces morceaux et en additionnant les quatre inégalités, on obtient que le nombre de triangles iso-impairs dans \(L\) autres que \(PQS\) ne dépasse pas \(n/2\). Et comme chacun des morceaux \(L_{PS}\), \(L_{SQ}\) est formé d'un nombre impair de côtés, les inégalités pour ces deux morceaux sont en fait strictes, ce qui laisse un excédent de \(1/2 + 1/2\). Le triangle \(PSQ\) est donc lui aussi couvert par l'estimation \(n/2\). Cela termine l'hérédité et prouve le lemme. \(\square\)

La suite de la solution reprend en fait l'argument de la preuve ci-dessus. Considérons la plus longue diagonale \(XY\) de la triangulation. Soit \(L_{XY}\) la plus courte des deux parties du bord d'extrémités \(X\), \(Y\), et soit \(XYZ\) le triangle de la triangulation dont le sommet \(Z\) n'est pas sur \(L_{XY}\). Remarquons que \(XYZ\) est acutangle ou rectangle, sinon l'un des segments \(XZ\), \(YZ\) serait plus long que \(XY\). En notant \(L_{XZ}\), \(L_{YZ}\) les deux morceaux définis par \(Z\) et en appliquant le lemme à chacun des morceaux \(L_{XY}\), \(L_{XZ}\), \(L_{YZ}\), on obtient qu'il n'y a pas plus de \(2006/2\) triangles iso-impairs en tout, sauf si \(XYZ\) en est un. Mais dans ce cas, \(XZ\) et \(YZ\) sont des diagonales impaires et les inégalités correspondantes sont strictes. Cela montre que, dans ce cas aussi, le nombre total de triangles iso-impairs de la triangulation, \(XYZ\) compris, ne dépasse pas \(1003\).

Cette borne peut être atteinte. Pour cela, il suffit de choisir un sommet du \(2006\)-gone et de tracer une ligne brisée joignant un sommet sur deux, en partant du sommet choisi. Comme \(2006\) est pair, la ligne se referme. Cela donne déjà les \(1003\) triangles iso-impairs voulus. On peut ensuite compléter la triangulation de façon arbitraire. \(\blacksquare\)

Solution 2¶

On garde les notions de triangle impair et de triangle iso-impair de la première solution.

Soit \(ABC\) un triangle iso-impair, avec \(AB\) et \(BC\) côtés impairs. Cela signifie qu'il y a un nombre impair de côtés du \(2006\)-gone entre \(A\) et \(B\), ainsi qu'entre \(B\) et \(C\). On dit que ces côtés appartiennent au triangle iso-impair \(ABC\).

Au moins un côté de chacun de ces groupes n'appartient à aucun autre triangle iso-impair. En effet, tout triangle impair dont les sommets sont parmi les points entre \(A\) et \(B\) a deux côtés de même longueur et a donc au total un nombre pair de côtés qui lui appartiennent. En éliminant tous les côtés appartenant à un autre triangle iso-impair dans cette zone, il doit donc rester un côté qui n'appartient à aucun autre triangle iso-impair. Attribuons ces deux côtés (un dans chaque groupe) au triangle \(ABC\).

On a ainsi attribué à chaque triangle iso-impair une paire de côtés, deux triangles ne partageant aucun côté attribué. Il s'ensuit qu'au plus \(1003\) triangles iso-impairs peuvent apparaître dans la triangulation. Cette valeur est atteinte, comme le montre l'exemple de la première solution. \(\blacksquare\)