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é¶
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.