Shortlist 2012, C5¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : non indiqué
Concepts : Graphes : degrés, chemins, arbres · Coloriages et pavages · Double comptage
Solution officielle : Shortlist officielle 2012 (avec solutions), p. 24 (page 24 du PDF)
Énoncé¶
Les colonnes et les lignes d'un plateau carré \(3n \times 3n\) sont numérotées \(1, 2, \ldots, 3n\). Chaque case \((x, y)\), avec \(1 \leq x, y \leq 3n\), est coloriée en asperge, en byzantin ou en citrine selon que le reste de \(x + y\) modulo \(3\) vaut respectivement \(0\), \(1\) ou \(2\). Un jeton de couleur asperge, byzantin ou citrine est placé sur chaque case, de sorte qu'il y ait \(3n^2\) jetons de chaque couleur.
On suppose qu'on peut permuter les jetons de sorte que chaque jeton soit déplacé à une distance au plus \(d\) de sa position initiale, que chaque jeton asperge prenne la place d'un jeton byzantin, chaque jeton byzantin celle d'un jeton citrine, et chaque jeton citrine celle d'un jeton asperge. Montrer qu'on peut permuter les jetons de sorte que chaque jeton soit déplacé à une distance au plus \(d + 2\) de sa position initiale, et que chaque case porte un jeton de la même couleur qu'elle.
Énoncé original (anglais)
The columns and the rows of a \(3n \times 3n\) square board are numbered \(1, 2, \ldots, 3n\). Every square \((x, y)\) with \(1 \leq x, y \leq 3n\) is colored asparagus, byzantium or citrine according as the modulo \(3\) remainder of \(x + y\) is \(0\), \(1\) or \(2\) respectively. One token colored asparagus, byzantium or citrine is placed on each square, so that there are \(3n^2\) tokens of each color.
Suppose that one can permute the tokens so that each token is moved to a distance of at most \(d\) from its original position, each asparagus token replaces a byzantium token, each byzantium token replaces a citrine token, and each citrine token replaces an asparagus token. Prove that it is possible to permute the tokens so that each token is moved to a distance of at most \(d + 2\) from its original position, and each square contains a token with the same color as the square.
Indices : les idées clés
- Se ramener à un couplage : il suffit d'envoyer les jetons \(A\) sur des cases \(A\) distinctes, chacun à distance au plus \(d + 2\).
- Pavage en triminos \(3 \times 1\), contenant chacun une case \(A\) ; on relie une case \(A\) et un jeton \(A\) si \(T\), \(\pi(T)\) ou \(\pi^{-1}(T)\) est sur le trimino de la case.
- Graphe biparti \(3\)-régulier : un double comptage des arêtes vérifie la condition de Hall, d'où un couplage parfait.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2012 (une solution et deux remarques).
Solution¶
Sans perte de généralité, il suffit de prouver que les jetons \(A\) peuvent être déplacés vers des cases \(A\) distinctes, chaque jeton \(A\) étant déplacé à une distance au plus \(d + 2\) de sa position initiale. Cela revient à trouver un couplage parfait entre les \(3n^2\) cases \(A\) et les \(3n^2\) jetons \(A\), chaque couple étant à distance au plus \(d + 2\).
Pour trouver ce couplage, construisons un graphe biparti. Les cases \(A\) forment une classe de sommets, et les jetons \(A\) l'autre classe.
Découpons le plateau en triminos horizontaux \(3 \times 1\) ; chaque trimino contient exactement une case \(A\). Prenons une permutation \(\pi\) des jetons qui envoie les jetons \(A\) sur des jetons \(B\), les jetons \(B\) sur des jetons \(C\) et les jetons \(C\) sur des jetons \(A\), chaque fois à distance au plus \(d\). Pour toute case \(A\) notée \(S\) et tout jeton \(A\) noté \(T\), relions \(S\) et \(T\) par une arête si \(T\), \(\pi(T)\) ou \(\pi^{-1}(T)\) est sur le trimino contenant \(S\). On autorise les arêtes multiples ; une même case et un même jeton peuvent même être reliés par trois arêtes. Évidemment, les longueurs des arêtes du graphe ne dépassent pas \(d + 2\) (la longueur d'une arête étant la distance entre la case \(A\) et le jeton \(A\) qu'elle relie).
Chaque jeton \(A\) noté \(T\) est relié aux trois cases \(A\) dont les triminos contiennent \(T\), \(\pi(T)\) et \(\pi^{-1}(T)\). Dans le graphe, tous les jetons sont donc de degré \(3\). Montrons qu'il en est de même des cases \(A\). Soit \(S\) une case \(A\), et \(T_1\), \(T_2\), \(T_3\) les trois jetons du trimino contenant \(S\). Pour \(i = 1, 2, 3\) : si \(T_i\) est un jeton \(A\), alors \(S\) est relié à \(T_i\) ; si \(T_i\) est un jeton \(B\), alors \(S\) est relié à \(\pi^{-1}(T_i)\) ; enfin, si \(T_i\) est un jeton \(C\), alors \(S\) est relié à \(\pi(T_i)\). Dans le graphe, les cases \(A\) sont donc aussi de degré \(3\).
Comme les cases \(A\) sont de degré \(3\), d'un ensemble \(\mathcal{S}\) de cases \(A\) partent exactement \(3\lvert \mathcal{S} \rvert\) arêtes. Ces arêtes aboutissent à au moins \(\lvert \mathcal{S} \rvert\) jetons, car les jetons \(A\) sont aussi de degré \(3\). Tout ensemble \(\mathcal{S}\) de cases \(A\) a donc au moins \(\lvert \mathcal{S} \rvert\) voisins parmi les jetons \(A\).
Par le théorème des mariages de Hall, le graphe contient donc un couplage parfait entre les deux classes de sommets. Il existe ainsi un couplage parfait entre les cases \(A\) et les jetons \(A\), avec des arêtes de longueur au plus \(d + 2\). Il s'ensuit que les jetons peuvent être permutés comme demandé. \(\blacksquare\)
Remarques¶
Remarque 1. Dans la proposition d'origine, le plateau était infini et il n'y avait que deux couleurs. Avoir \(n\) couleurs pour un entier \(n \geq 1\) était une option ; le comité a choisi \(n = 3\). De plus, il a pris un plateau fini pour éviter les graphes infinis (bien que le théorème de Hall fonctionne aussi dans le cas infini).
Avec seulement deux couleurs, le théorème de Hall n'est pas nécessaire. On découpe alors le plateau en dominos \(2 \times 1\), et dans le graphe obtenu tous les sommets sont de degré \(2\). Le graphe est formé de cycles disjoints de longueur paire et de chemins infinis, et l'existence du couplage est immédiate.
Avoir plus de trois couleurs compliquerait l'énoncé, car il faudrait un couplage entre deux classes de couleurs quelconques de jetons ; cela n'augmenterait cependant pas beaucoup la difficulté.
Remarque 2. Selon Wikipédia, la couleur asperge (code hexadécimal #87A96B) est un ton de vert qui porte le nom du légume ; Crayola l'a créée en 1993. Le byzantium (#702963) est un ton sombre de violet, dont le premier usage attesté comme nom de couleur en anglais date de 1926. Le citrine (#E4D00A) est décrit comme jaune, jaune verdâtre, jaune brunâtre ou orange ; son premier usage comme nom de couleur en anglais remonte au XIVe siècle.
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2017 A5 ★★★☆☆ : Si toute permutation a ses produits voisins de somme au moins \(-1\), que peut-on garantir sur la somme de tous les produits ?
- 2015 C5 ★★★☆☆ · OIM P6 : Une suite bornée où les \(i + a_i\) sont distincts a des sommes partielles proches de celles d'une suite constante.
- 2025 C6 ★★★★☆ : À partir d'un chemin hamiltonien d'un échidné, numéroter les cases pour que, entre voisines, le plus grand nombre soit visité en premier en ligne et en second en colonne.
- 2018 C7 ★★★★★ : Des cercles aux sommets coloriés alternativement : si un cercle porte beaucoup de points jaunes, une région est entièrement jaune.