Shortlist 2021, C3¶

Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : non indiqué

Concepts : Invariants et monovariants · Coloriages et pavages

Solution officielle : Shortlist officielle 2021 (avec solutions), p. 28 (page 28 du PDF)

Problème 5 de l'OIM 2021

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2021, où il était le problème 5 (jour 2).

Énoncé¶

A thimblerigger has \(2021\) thimbles numbered from \(1\) through \(2021\). The thimbles are arranged in a circle in arbitrary order. The thimblerigger performs a sequence of \(2021\) moves; in the \(k\)-th move, he swaps the positions of the two thimbles adjacent to thimble \(k\).

Prove that there exists a value of \(k\) such that, in the \(k\)-th move, the thimblerigger swaps some thimbles \(a\) and \(b\) such that \(a < k < b\).

Indices : les idées clés

Raisonnement par l'absurde : on suppose qu'aucun mouvement n'échange deux dés \(a < k < b\), et on en tire une structure très rigide.
Invariants et monovariants : sous cette hypothèse, une position ne change de « couleur » qu'au mouvement où elle est centrale ; chaque position est donc centrale exactement une fois.
Coloriages et pavages : on colorie les positions en rouge ou vert selon le type du mouvement dont elles sont centrales ; deux positions voisines ont des couleurs différentes.
Parité : un cercle de \(2021\) positions (nombre impair) ne peut pas être colorié en alternance.

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2021 (une solution et deux remarques).

Solution¶

Supposons le contraire. Appelons le dé (à coudre) numéro \(k\) le dé central du \(k\)-ième mouvement, et sa position pendant ce mouvement la position centrale du mouvement.

Étape 1 : coloriage noir et blanc. Avant le début, peignons tous les dés en blanc. Après chaque mouvement, repeignons son dé central en noir. À la fin, tous les dés sont noirs.

Par hypothèse, à chaque mouvement \(k\), les deux dés échangés ont la même couleur : leurs numéros sont soit tous deux plus grands que \(k\) (dés encore blancs), soit tous deux plus petits que \(k\) (dés déjà noirs). Attribuons à chaque instant à chaque position la couleur du dé qui s'y trouve. Échanger deux dés de même couleur ne change la couleur d'aucune position ; la seule position qui change de couleur lors d'un mouvement est donc sa position centrale. C'est un invariant : une position ne change de couleur (de blanc à noir) qu'une fois. En particulier, chaque position est centrale pour exactement un mouvement (celui où elle devient noire).

Étape 2 : coloriage rouge et vert. Colorions maintenant les positions. Si, lors du \(k\)-ième mouvement, les deux dés échangés ont des numéros tous deux inférieurs à \(k\), on peint la position centrale du mouvement en rouge ; sinon, on la peint en vert. D'après l'étape 1, chaque position est ainsi peinte en rouge ou en vert exactement une fois.

Montrons que, de deux positions adjacentes, l'une est verte et l'autre rouge. Ce sera la contradiction cherchée : les \(2021\) positions forment un cercle de longueur impaire, qu'on ne peut pas colorier en alternant deux couleurs.

Soient \(A\) et \(B\) deux positions adjacentes, centrales respectivement aux mouvements \(a\) et \(b\), avec \(a < b\).

Au mouvement \(a\), le dé situé en \(B\) est blanc (la position \(B\) ne deviendra noire qu'au mouvement \(b > a\)), donc son numéro est supérieur à \(a\). Ainsi \(A\) devient verte, et le dé en \(A\) devient noir.
D'après l'étape 1, la position \(A\) ne contient plus que des dés noirs après le mouvement \(a\). Au mouvement \(b\), la position \(A\) contient donc un dé noir, dont le numéro est inférieur à \(b\), tandis que le dé \(b\) est en \(B\). Les dés échangés au mouvement \(b\) ont donc des numéros inférieurs à \(b\) (ils sont de même couleur, par hypothèse), et \(B\) devient rouge.

Ainsi \(A\) et \(B\) sont de couleurs différentes, ce qui est impossible sur un cercle de longueur \(2021\). \(\blacksquare\)

Remarques¶

Remarque 1. L'étape 1 prouve en fait (sous l'hypothèse par l'absurde) deux affirmations : (1) chaque position \(P\) est centrale pour exactement un mouvement, disons le \(k\)-ième ; (2) avant le \(k\)-ième mouvement, \(P\) contient toujours un dé de numéro supérieur au numéro du mouvement en cours, et après, toujours un dé de numéro inférieur. On peut les prouver sans couleurs, mais les couleurs aident à visualiser.

L'étape 2 peut alors se faire autrement. À tout moment, les positions noires forment des blocs de positions noires consécutives, séparés par des positions blanches. On montre par récurrence sur \(k\) qu'après le \(k\)-ième mouvement, tous les blocs ont une taille impaire : à chaque mouvement, la nouvelle position noire forme un bloc isolé (de taille \(1\)) ou fusionne deux blocs de tailles \(a\) et \(b\) en un bloc de taille \(a + b + 1\). Or, après le \(2020\)-ième mouvement, les positions noires forment un seul bloc de taille \(2020\), paire : contradiction. Variante : on peut aussi vérifier qu'après le début du processus, l'un des blocs de positions blanches est de taille paire.

Remarque 2. La solution vaut pour tout nombre impair de dés supérieur à \(1\). En revanche, l'énoncé analogue est faux pour un nombre pair \(n = 2k \geq 4\) : on numérote les positions de \(1\) à \(n\) dans le sens horaire, on place les dés \(1, 2, \ldots, k\) sur les positions impaires et les dés \(k+1, \ldots, 2k\) sur les positions paires.