Shortlist 2020, C2¶
Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : Austria
Concepts : Récurrence et constructions récursives · Principe des tiroirs
Solution officielle : Shortlist officielle 2020 (avec solutions), p. 32 (page 34 du PDF)
Figures reprises du livret officiel de la Shortlist.
Énoncé¶
In a regular \(100\)-gon, \(41\) vertices are colored black and the remaining \(59\) vertices are colored white. Prove that there exist \(24\) convex quadrilaterals \(Q_1, \ldots, Q_{24}\) whose corners are vertices of the \(100\)-gon, so that
- the quadrilaterals \(Q_1, \ldots, Q_{24}\) are pairwise disjoint, and
- every quadrilateral \(Q_i\) has three corners of one color and one corner of the other color.
Indices : les idées clés
- Renforcer l'énoncé : on démontre un résultat plus général sur un \((4k+1)\)-gone dont chaque couleur apparaît au moins \(k\) fois, après avoir retiré \(3\) sommets du \(100\)-gone.
- Récurrence : on retire quatre sommets consécutifs formant un quadrilatère bicolore « 3 + 1 » et on applique l'hypothèse de récurrence au \((4k-3)\)-gone restant.
- Principe des tiroirs : en découpant les sommets en \(k\) groupes de quatre sommets consécutifs, un groupe contient plus de sommets blancs que de noirs.
- Parité (cas de base) : dans un pentagone, on retire un sommet de façon que chaque couleur apparaisse un nombre impair de fois.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2020 (une solution et une remarque).
Solution¶
Appelons mal colorié un quadrilatère qui a trois sommets d'une couleur et un sommet de l'autre. Nous démontrons l'affirmation suivante.
Affirmation. Si les sommets d'un polygone convexe \(P\) à \(4k + 1\) sommets sont coloriés en noir et blanc, chaque couleur étant utilisée au moins \(k\) fois, alors il existe \(k\) quadrilatères mal coloriés deux à deux disjoints dont les sommets sont des sommets de \(P\) (un sommet de \(P\) reste inutilisé).
L'énoncé s'en déduit en retirant \(3\) sommets quelconques du \(100\)-gone et en appliquant l'affirmation aux \(97\) sommets restants avec \(k = 24\). Précision ajoutée : chaque couleur y apparaît encore au moins \(41 - 3 = 38 \geq 24\) fois.
Preuve de l'affirmation. On raisonne par récurrence sur \(k\).
Pour \(k = 1\), on a un pentagone avec au moins un sommet noir et au moins un sommet blanc. Si le nombre de sommets noirs est pair, on retire un sommet noir ; sinon, on retire un sommet blanc. Dans le quadrilatère restant, il y a un nombre impair de sommets noirs et un nombre impair de sommets blancs, donc il est mal colorié.
Pour l'hérédité, soit \(k \geq 2\). Notons \(b\) et \(w\) les nombres de sommets noirs et blancs ; alors \(b, w \geq k\) et \(b + w = 4k + 1\). Sans perte de généralité, \(w \geq b\), donc \(k \leq b \leq 2k\) et \(2k + 1 \leq w \leq 3k + 1\).
On cherche quatre sommets consécutifs dont trois sont blancs et le quatrième noir. Numérotons les sommets \(V_1, V_2, \ldots, V_{4k+1}\) dans le sens direct, de sorte que \(V_{4k+1}\) soit noir, et considérons les \(k\) groupes
Ces groupes contiennent \(w\) sommets blancs et \(b - 1\) sommets noirs. Comme \(w > b - 1\), d'après le principe des tiroirs, l'un des groupes, disons \((V_i, V_{i+1}, V_{i+2}, V_{i+3})\), contient plus de sommets blancs que de noirs. S'il en contient trois blancs et un noir, c'est gagné. Sinon, \(V_i, V_{i+1}, V_{i+2}, V_{i+3}\) sont tous blancs ; soit alors \(V_j\) le premier sommet noir parmi \(V_{i+4}, \ldots, V_{4k+1}\) (il en existe, puisque \(V_{4k+1}\) est noir) : \(V_{j-3}\), \(V_{j-2}\), \(V_{j-1}\) sont blancs et \(V_j\) est noir.
Nous avons donc quatre sommets consécutifs formant un quadrilatère mal colorié. Les sommets restants forment un polygone convexe à \(4k - 3\) sommets, disjoint de ce quadrilatère puisque les quatre sommets retirés sont consécutifs ; \(w - 3\) de ces sommets sont blancs et \(b - 1\) sont noirs. Comme \(b - 1 \geq k - 1\) et \(w - 3 \geq (2k + 1) - 3 > k - 1\), on peut appliquer l'affirmation au rang \(k - 1\). \(\square\) \(\blacksquare\)
Remarques¶
Remarque. On ne peut pas, en général, découper les sommets du \(100\)-gone en \(25\) quadrilatères mal coloriés. Contre-exemple : \(V_1, V_3, V_5, \ldots, V_{81}\) noirs (\(41\) sommets) et les autres sommets \(V_2, V_4, \ldots, V_{80}\) et \(V_{82}, V_{83}, \ldots, V_{100}\) blancs. Pour avoir \(25\) quadrilatères mal coloriés, il faudrait que \(8\) d'entre eux aient trois sommets noirs (car \(41 = 3 \cdot 8 + 17\)). Mais un tel quadrilatère partage les \(96\) autres sommets en quatre arcs dont au moins deux contiennent un nombre impair de sommets ; ceux-ci ne peuvent donc pas être regroupés en quadrilatères disjoints.
