Shortlist 2016, C3¶

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

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

Énoncé¶

Let \(n\) be a positive integer relatively prime to \(6\). We paint the vertices of a regular \(n\)-gon with three colours so that there is an odd number of vertices of each colour. Show that there exists an isosceles triangle whose three vertices are of different colours.

Indices : les idées clés

Raisonnement par l'absurde : on suppose qu'aucun triangle isocèle n'a ses trois sommets de couleurs différentes.
Double comptage : on compte les couples (triangle isocèle, côté bicolore) de deux façons.
Parité : un des comptages est pair, l'autre est impair car \(b\), \(c\), \(d\) sont impairs.
Géométrie du polygone régulier : par deux sommets passent exactement trois triangles isocèles distincts, car \(n\) est impair et premier avec \(3\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2016 (une solution et une remarque).

Solution¶

Pour \(k = 1, 2, 3\), soit \(a_k\) le nombre de triangles isocèles (à sommets parmi ceux du polygone) dont les sommets portent exactement \(k\) couleurs. Supposons par l'absurde que \(a_3 = 0\). Soient \(b\), \(c\), \(d\) les nombres de sommets de chacune des trois couleurs. Comptons de deux façons le nombre de couples \((\Delta, E)\), où \(\Delta\) est un triangle isocèle et \(E\) un côté de \(\Delta\) dont les extrémités sont de couleurs différentes (double comptage).

Premier comptage. Comme \(a_3 = 0\), un triangle d'un tel couple a exactement deux couleurs, et il a alors exactement deux côtés bicolores. Chaque triangle contribue donc deux fois, et le nombre de couples est \(2a_2\).

Second comptage. Choisissons deux sommets \(A\), \(B\) de couleurs différentes. Il y a exactement trois triangles isocèles ayant \(A\) et \(B\) pour sommets : deux où \([AB]\) n'est pas la base (de sommet principal \(A\) ou \(B\)), et un où \([AB]\) est la base, car \(n\) est impair et la médiatrice de \([AB]\) passe par exactement un sommet du polygone. Ces trois triangles sont distincts car \(\operatorname{pgcd}(n, 3) = 1\) (il n'y a pas de triangle équilatéral). On obtient ainsi \(3(bc + cd + db)\) couples.

Or \(2a_2\) est pair, tandis que \(3(bc + cd + db)\) est impair puisque \(b\), \(c\), \(d\) le sont. C'est une contradiction, donc \(a_3 \geq 1\) : il existe un triangle isocèle dont les trois sommets sont de couleurs différentes. \(\blacksquare\)

Remarques¶

Remarque 1. On peut renforcer l'énoncé en remplaçant la condition \(\operatorname{pgcd}(n, 6) = 1\) par « \(n\) impair » (les triangles équilatéraux étant considérés comme isocèles). La seule différence est que, pour deux sommets \(A\), \(B\) fixés, il y a exactement un ou trois triangles isocèles les contenant ; comme seule la parité intervient, la preuve est la même.

La condition « chaque couleur apparaît un nombre impair de fois » est nécessaire. Prenons \(n = 25\) et les sommets \(A_0, A_1, \ldots, A_{24}\) : la couleur 1 pour \(A_0\), la couleur 2 pour \(A_5, A_{10}, A_{15}, A_{20}\), et la couleur 3 pour tous les autres. Un triangle isocèle ayant les couleurs 1 et 2 contient \(A_0\) et l'un des \(A_5, A_{10}, A_{15}, A_{20}\) ; son troisième sommet a alors un indice multiple de \(5\), donc n'est pas de couleur 3.