Aller au contenu

Shortlist 2022, C2

Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : France

Concepts : Invariants et monovariants

Solution officielle : Shortlist officielle 2022 (avec solutions), p. 25 (page 27 du PDF)

Problème 1 de l'OIM 2022

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

Énoncé

The Bank of Oslo issues coins made out of two types of metal: aluminium (denoted \(A\)) and copper (denoted \(C\)). Morgane has \(n\) aluminium coins, and \(n\) copper coins, and arranges her \(2n\) coins in a row in some arbitrary initial order. Given a fixed positive integer \(k \leq 2n\), she repeatedly performs the following operation: identify the largest subsequence containing the \(k\)-th coin from the left which consists of consecutive coins made of the same metal, and move all coins in that subsequence to the left end of the row. For example, if \(n = 4\) and \(k = 4\), the process starting from the configuration \(AACCCACA\) would be

\[AACCCACA \to CCCAAACA \to AAACCCCA \to CCCCAAAA \to \cdots.\]

Find all pairs \((n, k)\) with \(1 \leq k \leq 2n\) such that for every initial configuration, at some point of the process there will be at most one aluminium coin adjacent to a copper coin.

Indices : les idées clés
  • Reformuler en blocs : la configuration voulue est celle qui n'a que deux blocs (tous les \(A\), puis tous les \(C\), ou l'inverse).
  • Monovariant : le nombre de blocs ne peut pas augmenter ; il diminue dès qu'on déplace un bloc qui n'est pas à une extrémité.
  • Configurations bloquées : \(A^{n-1}C^{n-1}AC\) pour \(k < n\), et un cycle de quatre blocs \(A^aC^bA^bC^a\) pour \(k > \frac{3n+1}{2}\).
  • Sommer les contraintes : si le bloc de droite était toujours déplacé, on aurait \(k \geq 2n + 1 - a_i\) pour chaque taille de bloc \(a_i\) ; en sommant, \(k \geq \frac{3n}{2} + 1\).
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2022 (une solution).

Réponse : tous les couples \((n, k)\) tels que \(n \leq k \leq \dfrac{3n + 1}{2}\).

Solution 1

Appelons bloc une sous-suite maximale de pièces consécutives du même métal, et notons \(M^b\) un bloc de \(b\) pièces du métal \(M\). La propriété « au plus une pièce d'aluminium est voisine d'une pièce de cuivre » équivaut clairement au fait que la configuration n'a que deux blocs, l'un formé de tous les \(A\) et l'autre de tous les \(C\).

Les couples qui ne conviennent pas.

  • Si \(k < n\), la configuration \(A^{n-1}C^{n-1}AC\) reste fixe sous l'opération (la \(k\)-ième pièce est dans le premier bloc, déjà tout à gauche) : elle a toujours \(4\) blocs.

  • Si \(k > \frac{3n+1}{2}\), posons \(a = k - n - 1\) et \(b = 2n - k + 1\) (donc \(a, b \geq 1\) et \(a + b = n\)). Alors \(k > 2a + b\) et \(k > 2b + a\), donc la \(k\)-ième pièce est toujours dans le dernier bloc, et la configuration \(A^aC^bA^bC^a\) garde quatre blocs :

    \[A^aC^bA^bC^a \to C^aA^aC^bA^b \to A^bC^aA^aC^b \to C^bA^bC^aA^a \to A^aC^bA^bC^a \to \cdots\]

Un couple \((n, k)\) ne peut donc convenir que si \(n \leq k \leq \frac{3n+1}{2}\).

Tous ces couples conviennent. Le nombre de blocs ne peut pas augmenter : à chaque opération, il diminue ou reste constant (c'est un monovariant). Montrons que, tant qu'il y a plus de deux blocs, le nombre de blocs finit par diminuer après un nombre fini d'étapes.

Considérons une configuration à \(c \geq 3\) blocs. Comme \(k \geq n\), le bloc le plus à gauche ne peut pas être celui qui est déplacé : sinon il contiendrait au moins \(k \geq n\) pièces, donc toutes les \(n\) pièces de l'un des métaux, et il n'y aurait que deux blocs. Si le bloc déplacé n'est ni le plus à gauche ni le plus à droite, ses deux voisins (du même métal) fusionnent, et le nombre de blocs diminue.

Le seul cas où le nombre de blocs ne diminue pas est donc celui où l'on déplace le bloc le plus à droite. Si \(c\) est impair, le bloc de gauche et celui de droite sont du même métal, et ce déplacement les fusionne. Donc \(c \geq 4\) est pair. Supposons qu'il existe une configuration à \(c\) blocs, de tailles \(a_1, \ldots, a_c\), pour laquelle l'opération déplace toujours le bloc de droite :

\[A^{a_1} \cdots A^{a_{c-1}} C^{a_c} \to C^{a_c} A^{a_1} \cdots A^{a_{c-1}} \to A^{a_{c-1}} C^{a_c} A^{a_1} \cdots C^{a_{c-2}} \to \cdots\]

Chaque bloc devient à son tour le bloc de droite, et comme c'est toujours lui qui est déplacé, \(k \geq 2n + 1 - a_i\) pour tout \(i\). Puisque \(\sum a_i = 2n\), en sommant sur tous les \(i\) :

\[ck \geq 2cn + c - \sum_i a_i = 2cn + c - 2n, \quad \text{donc} \quad k \geq 2n + 1 - \frac{2n}{c} \geq \frac{3n}{2} + 1\]

(car \(c \geq 4\)). Cela contredit \(k \leq \frac{3n+1}{2}\). Donc, à un certain moment, l'opération ne déplace pas le bloc de droite, et le nombre de blocs diminue. En répétant, on arrive à une configuration à deux blocs. \(\blacksquare\)