Shortlist 2021, C2¶
Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : non indiqué
Concepts : Principe des tiroirs · Récurrence et constructions récursives · Coloriages et pavages
Solution officielle : Shortlist officielle 2021 (avec solutions), p. 27 (page 27 du PDF)
Énoncé¶
Let \(n \geq 3\) be an integer. An integer \(m \geq n + 1\) is called \(n\)-colourful if, given infinitely many marbles in each of \(n\) colours \(C_1, C_2, \ldots, C_n\), it is possible to place \(m\) of them around a circle so that in any group of \(n + 1\) consecutive marbles there is at least one marble of colour \(C_i\) for each \(i = 1, \ldots, n\).
Prove that there are only finitely many positive integers which are not \(n\)-colourful. Find the largest among them.
Indices : les idées clés
- Principe des tiroirs : avec \(n(n-1) - 1\) billes, une couleur apparaît au plus \(n - 2\) fois, et les autres billes, réparties en au plus \(n-2\) groupes, en forment un de \(n + 1\) billes consécutives sans cette couleur.
- Récurrence et constructions récursives : on écrit \(m = nk + j\) et on recolle des motifs périodiques \([1, 2, \ldots, n]\) et \([1, 1, 2, \ldots, n]\).
- Coloriages et pavages : un motif de longueur \(n\) ou \(n+1\) contenant toutes les couleurs garantit la condition sur toute fenêtre de \(n + 1\) billes.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2021 (une solution).
Réponse : le plus grand entier qui n'est pas \(n\)-coloré est \(m_{\max} = n^2 - n - 1\).
Solution 1¶
\(n(n-1) - 1\) n'est pas \(n\)-coloré. Supposons qu'il y ait \(n(n-1) - 1\) billes sur le cercle. Si chaque couleur apparaissait au moins \(n - 1\) fois, il y aurait au moins \(n(n-1)\) billes ; donc une couleur, disons le bleu, apparaît au plus \(n - 2\) fois. Ces billes bleues découpent les billes non bleues en au plus \(n - 2\) groupes (d'arcs consécutifs), qui contiennent au total au moins
billes. Par le principe des tiroirs, l'un de ces groupes contient au moins \(n + 1\) billes consécutives, et aucune n'est bleue : la condition est violée.
Tout \(m \geq n(n-1)\) est \(n\)-coloré. Écrivons \(m = nk + j\) avec \(k \geq n - 1\) et \(0 \leq j \leq n - 1\) (division euclidienne de \(m\) par \(n\)). Comme \(j \leq n-1 \leq k\), on peut construire la disposition suivante autour du cercle : \(k - j\) copies du motif de couleurs \([1, 2, 3, \ldots, n]\), suivies de \(j\) copies du motif \([1, 1, 2, 3, \ldots, n]\). Le nombre total de billes est \(n(k - j) + (n+1) j = nk + j = m\).
Vérifions la condition ; appelons blocs les copies des motifs (courts, de longueur \(n\), ou longs, de longueur \(n+1\)). Il suffit de montrer que, pour chaque couleur, deux occurrences consécutives de cette couleur (en tournant autour du cercle) sont séparées par au plus \(n\) autres billes : alors toute fenêtre de \(n+1\) billes consécutives contient cette couleur. Une couleur \(c \geq 2\) apparaît une fois par bloc, en position \(c\) dans un bloc court \([1, \ldots, n]\) et en position \(c + 1\) dans un bloc long \([1, 1, 2, \ldots, n]\). Entre son occurrence dans un bloc et celle du bloc suivant, la distance vaut (longueur du premier bloc) \(-\) (position dans le premier) \(+\) (position dans le second), soit \(n\) ou \(n+1\) dans tous les cas (court puis court : \(n\) ; court puis long : \(n+1\) ; long puis court : \(n\) ; long puis long : \(n+1\)). La couleur \(1\) est en tête de chaque bloc, et la distance de la dernière bille \(1\) d'un bloc à la première du bloc suivant vaut \(n\). Une distance au plus \(n + 1\) signifie au plus \(n\) billes