Shortlist 2016, C3¶
Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : non indiqué
Concepts : Double comptage
Solution officielle : Shortlist officielle 2016 (avec solutions), p. 33 (page 36 du PDF)
Énoncé¶
Soit \(n\) un entier strictement positif premier avec \(6\). On colorie les sommets d'un \(n\)-gone régulier avec trois couleurs, de sorte que chaque couleur soit utilisée pour un nombre impair de sommets. Montrer qu'il existe un triangle isocèle dont les trois sommets sont de couleurs différentes.
Énoncé original (anglais)
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.
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2024 C3 ★★☆☆☆ : Des chevaliers en cercle échangent leurs places pour serrer la main de leur partenaire : combien d'échanges ?
- 2018 C3 ★★☆☆☆ : Sisyphe déplace des pierres d'autant de cases au plus que la pile en compte : il lui faut au moins \(\sum \lceil n/k \rceil\) tours.
- 2016 C4 ★★☆☆☆ · OIM P2 : Pour quels \(n\) peut-on remplir un tableau \(n \times n\) de \(I\), \(M\), \(O\) équilibrés sur les lignes, colonnes et certaines diagonales ?
- 2012 C3 ★★☆☆☆ : Coloriage d'un tableau \(999 \times 999\) : maximiser le nombre de triplets blanc-rouge-blanc en équerre.