Shortlist 2024, C3¶
Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : Belarus
Concepts : Double comptage · Invariants et monovariants · Principe extrémal · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2024 (avec solutions), section C3 (livret PDF)
Énoncé¶
Let \(n\) be a positive integer. There are \(2n\) knights sitting at a round table. They consist of \(n\) pairs of partners, each pair of which wishes to shake hands. A pair can shake hands only when next to each other. Every minute, one pair of adjacent knights swaps places.
Find the minimum number of exchanges of adjacent knights such that, regardless of the initial arrangement, every knight can meet her partner and shake hands at some time.
Indices : les idées clés
- Cordes (« chaînes ») : relier chaque couple par une corde et classer les paires de cordes en sécantes, emboîtées ou disjointes, avec \(k + l + m = \frac{n(n-1)}{2}\).
- Double comptage (lemme 1, preuve 2) : chaque couple opposé doit parcourir au moins \(n - 1\) pas, et chaque échange fait faire un pas à deux chevaliers.
- Monovariant (lemme 2, preuve 1) : on trouve toujours un échange qui fait baisser \(2k + l\) de \(1\).
- Principe extrémal (lemme 3) : partir d'une corde de longueur maximale (preuve 1), ou d'un ensemble \(R\) minimisant \(\sum k_{C'}\) (preuve 2).
- Récurrence : sur \(2k + l\) (lemme 2) et sur \(n\) (lemme 3) pour établir \(k \leq m\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2024 (une solution organisée en trois lemmes, chacun avec deux preuves, et une remarque).
Réponse. Le nombre minimal d'échanges est \(\dfrac{n(n-1)}{2}\).
Remarque commune du livret. La solution est découpée en trois lemmes, et l'on donne plusieurs preuves de chacun.
Solution¶
On relie les deux chevaliers de chaque couple par une corde à travers la table ; on appelle ces cordes des chaînes.
Minoration. Montrons d'abord que \(n(n-1)/2\) échanges sont nécessaires pour certaines dispositions.
Lemme 1. Si chaque chevalier est initialement assis exactement en face de son partenaire, il faut au moins \(n(n-1)/2\) échanges pour que tous les couples puissent se serrer la main.
Preuve 1. Dans cette disposition, deux chaînes quelconques se coupent. Pour que deux partenaires soient voisins, il faut que leur chaîne ne coupe aucune autre chaîne ; chaque paire de chaînes doit donc être « décroisée » à un moment. Un échange de deux voisins ne peut décroiser qu'une seule paire de chaînes sécantes, donc il faut au moins autant d'échanges que de paires de chaînes, soit \(n(n-1)/2\). \(\square\)
Preuve 2. Dans cette disposition, les deux chevaliers de chaque couple sont séparés par \(n - 1\) places dans chaque sens ; chaque couple doit donc effectuer au total au moins \(n - 1\) pas pour devenir voisin. Il y a \(n\) couples, et chaque échange fait faire un pas à deux chevaliers : par double comptage, il faut au moins \(n(n-1)/2\) échanges. \(\square\)
Majoration. Montrons maintenant que \(n(n-1)/2\) échanges suffisent toujours. On prouve même plus : tous les couples peuvent être voisins à la fin, une fois tous les échanges effectués.
On place un pilier au centre de la table. Pour chaque chaîne qui passe par le centre, on choisit arbitrairement un côté de la chaîne et l'on décrète que le pilier est de ce côté. On ne déplacera jamais un chevalier si cela fait passer le pilier de l'autre côté d'une chaîne. On dit qu'une chaîne passe devant un chevalier si elle passe entre ce chevalier et le pilier, et l'on appelle longueur d'une chaîne le nombre de chevaliers devant lesquels elle passe ; elle est comprise entre \(0\) et \(n - 1\).
On dit qu'une chaîne \(C\) englobe une chaîne \(C'\) si \(C\) et \(C'\) ne se coupent pas et que \(C\) passe entre \(C'\) et le pilier. Deux chaînes sont sécantes si elles se coupent, emboîtées si l'une englobe l'autre, et disjointes sinon. Notons \(k\), \(l\), \(m\) les nombres de paires de chaînes respectivement emboîtées, sécantes et disjointes. Alors
Lemme 2. \(2k + l\) échanges suffisent pour atteindre une position où tous les couples sont voisins.
Preuve 1. Par récurrence sur \(2k + l\). Si toutes les chaînes sont de longueur \(0\), tous les couples sont voisins et il n'y a rien à faire.
Sinon, soient \(A\) et \(B\) un couple dont la chaîne \(C_0\) a une longueur \(q \geq 1\). Posons \(S_0 = A\), et soient \(S_1, \ldots, S_q\) les chevaliers devant lesquels passe \(C_0\), dans l'ordre de \(A\) vers \(B\). La chaîne \(C_1\) de \(S_1\) relève de l'un des trois cas suivants.
- Si \(C_1\) passe devant \(S_0\), alors \(C_0\) et \(C_1\) sont sécantes, et l'échange de \(S_0\) et \(S_1\) les rend disjointes : \(2k + l\) diminue de \(1\).
- Si \(C_1\) ne passe ni devant \(S_0\) ni devant \(B\), alors \(C_1\) est englobée par \(C_0\), et l'échange de \(S_0\) et \(S_1\) rend \(C_0\) et \(C_1\) sécantes : \(l\) augmente de \(1\) et \(k\) diminue de \(1\), donc \(2k + l\) diminue de \(1\).
- Si \(C_1\) passe devant \(B\), on ne trouve pas immédiatement d'échange favorable.
Dans le troisième cas, on examine successivement les chevaliers \(S_i\) et \(S_{i+1}\), pour chaque \(i\) : à chaque fois, ou bien on trouve un échange favorable (comme dans les deux premiers cas), ou bien la chaîne \(C_{i+1}\) de \(S_{i+1}\) passe devant \(B\). Finalement, ou bien on trouve un échange favorable, ou bien la chaîne \(C_q\) de \(S_q\) passe devant \(B\) ; dans ce dernier cas, \(C_q\) et \(C_0\) sont sécantes et l'échange de \(S_q\) et \(B\) les rend disjointes. Dans tous les cas, \(2k + l\) diminue de \(1\) (monovariant).
Enfin, une chaîne ne s'allonge que lorsqu'elle est englobée par une autre chaîne, ce qui est impossible pour une chaîne contenant le pilier : aucune chaîne ne franchit donc le pilier. \(\square\)
Preuve 2. Oublions d'abord les places, et laissons chaque chevalier marcher librement vers une destination fixée à l'avance : chaque couple marche autour de la table vers l'un des deux points du cercle situés à mi-chemin entre ses deux positions initiales, à savoir celui pour lequel la chaîne passe entre le pilier et la destination. Si plusieurs couples avaient la même destination, on ajuste légèrement les destinations pour qu'elles soient distinctes.
On imagine chaque chevalier marchant à vitesse constante (différente selon les chevaliers), tous partant et s'arrêtant en même temps, et l'on compte le nombre de fois où deux chevaliers se croisent (en sens opposés, ou dans le même sens à des vitesses différentes). Pour deux couples, ce nombre dépend de la relation entre leurs chaînes :
- chaînes sécantes : un croisement, entre les deux chevaliers pour lesquels l'autre chaîne passe entre eux et le pilier ;
- chaînes emboîtées : deux croisements, l'un des chevaliers de la chaîne englobante croisant les deux chevaliers de la chaîne englobée ;
- chaînes disjointes : aucun croisement.
Le nombre de croisements vaut donc \(2k + l\). Si plusieurs croisements avaient lieu au même instant, on ajuste légèrement les vitesses pour qu'ils aient lieu à des instants distincts. On transforme alors cette suite de croisements en une suite d'échanges de places, ce qui montre que \(2k + l\) échanges suffisent. \(\square\)
Lemme 3. \(k \leq m\).
Preuve 1. Par récurrence sur \(n\) ; le cas \(n = 2\) est clair. Considérons une chaîne \(C\) de longueur maximale (principe extrémal), qui relie \(A\) et \(B\). Soit \(x\) le nombre de chaînes sécantes à \(C\) et \(y\) le nombre de chaînes englobées par \(C\) ; aucune chaîne ne peut englober \(C\). La chaîne \(C\) passe devant un chevalier de chaque couple dont la chaîne coupe \(C\), et devant les deux chevaliers de chaque couple dont la chaîne est englobée par \(C\). Sa longueur vaut donc \(x + 2y \leq n - 1\), et le nombre de chaînes disjointes de \(C\) vaut
On retire alors \(A\) et \(B\) et l'on applique l'hypothèse de récurrence ; il faut vérifier que chaque chaîne restante est de longueur au plus \(n - 2\). Aucune chaîne ne s'allonge quand on retire \(A\) et \(B\). Si une chaîne \(C'\) avait la longueur \(n - 1\), alors \(C\) aussi (longueur maximale), et \(C'\) passait devant exactement l'un des chevaliers \(A\) ou \(B\) ; elle a donc la longueur \(n - 2\) après leur retrait. Les \(y\) paires emboîtées contenant \(C\) sont compensées par au moins \(y\) paires disjointes contenant \(C\), d'où \(k \leq m\). \(\square\)
Preuve 2. Notons \(k_C\) le nombre de chaînes \(C'\) englobées par \(C\). Si \(C\) englobe \(C'\), alors \(k_{C'} < k_C\).
Il y a au moins \(k_C\) chaînes disjointes de \(C\). Soit \(x\) la longueur de \(C\), \(S\) l'ensemble des \(x\) chevaliers devant lesquels passe \(C\), et \(T\) l'ensemble des \(x\) chevaliers assis en face d'eux. Aucun chevalier de \(T\) n'a une chaîne qui englobe \(C\) ou qui est englobée par \(C\), et si un chevalier de \(T\) a une chaîne sécante à \(C\), son partenaire est dans \(S\). Donc
Mieux : notons \(m_C\) le nombre de chaînes \(C'\) disjointes de \(C\) avec \(k_{C'} < k_C\) ; alors \(m_C \geq k_C\). Soit \(R\) un ensemble de \(k_C\) chaînes disjointes de \(C\) tel que \(\sum_{C' \in R} k_{C'}\) soit minimal (principe extrémal). Si toute chaîne \(C' \in R\) vérifie \(k_{C'} < k_C\), c'est terminé. Sinon, soit \(C' \in R\) avec \(k_{C'} \geq k_C\). Il y a au moins \(k_C\) chaînes \(C''\) englobées par \(C'\) ; chacune vérifie \(k_{C''} < k_{C'}\) et est disjointe de \(C\), et l'une d'elles au moins n'est pas dans \(R\) (sinon \(R\) contiendrait \(C'\) et au moins \(k_C\) autres chaînes). En la mettant à la place de \(C'\), on obtient un ensemble \(R'\) avec \(\sum_{C' \in R'} k_{C'} < \sum_{C' \in R} k_{C'}\), ce qui contredit la minimalité de \(R\).
On conclut en sommant sur toutes les chaînes \(C\) (chaque paire disjointe est comptée au plus une fois dans les \(m_C\)) :
Conclusion. D'après le lemme 3, \(2k + l \leq k + l + m = \frac{n(n-1)}{2}\). Avec le lemme 2, \(n(n-1)/2\) échanges suffisent pour atteindre une disposition où chaque chevalier est assis à côté de son partenaire. Avec le lemme 1, le minimum cherché est \(\frac{n(n-1)}{2}\). \(\blacksquare\)
Remarques¶
Remarque 1. Chacune des deux preuves du lemme 3 peut être adaptée pour montrer que la disposition du lemme 1 (partenaires face à face) est la seule qui atteint la borne.