Aller au contenu

Shortlist 2024, C6

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

Concepts : Invariants et monovariants · Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2024 (avec solutions), section C6 (livret PDF)

Énoncé

Soient \(n\) et \(T\) des entiers strictement positifs. James a \(4n\) billes de masses \(1, 2, \ldots, 4n\). Il les place sur les deux plateaux d'une balance, de sorte que les deux plateaux aient la même masse. Andrew peut faire passer une bille d'un plateau à l'autre, à condition que la différence (en valeur absolue) des masses des deux plateaux reste au plus égale à \(T\).

Trouver, en fonction de \(n\), le plus petit entier \(T\) strictement positif tel qu'Andrew puisse effectuer une suite de déplacements à l'issue de laquelle chaque bille se trouve sur l'autre plateau, quelle que soit la répartition initiale choisie par James.

Énoncé original (anglais)

Let \(n\) and \(T\) be positive integers. James has \(4n\) marbles with weights \(1, 2, \ldots, 4n\). He places them on a balance scale, so that both sides have equal weight. Andrew may move a marble from one side of the scale to the other, so that the absolute difference in weights of the two sides remains at most \(T\).

Find, in terms of \(n\), the minimum positive integer \(T\) such that Andrew may make a sequence of moves such that each marble ends up on the opposite side of the scale, regardless of how James initially placed the marbles.

Indices : les idées clés
  • Réversibilité (solution 1) : les coups étant réversibles, il suffit d'amener toute configuration à une configuration « standard » \(C\) depuis laquelle on sait tout inverser.
  • Paires de somme constante (solution 1) : grouper les poids en paires \((t, 4n + 1 - t)\) ; on sait échanger une paire avec \((2n, 2n+1)\) en cinq coups.
  • Monovariant : le nombre de paires séparées (solution 1), ou le nombre de billes mal placées (lemme 1 de la solution 2), diminue strictement.
  • Récurrence (solution 2) : tout entier de \(1\) à \(\frac{k(k+1)}{2}\) est somme d'entiers distincts de \(\{1, \ldots, k\}\) ; les petites billes servent alors de « monnaie d'appoint » pour déplacer les grosses, de la plus lourde à la plus légère.
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2024 (deux solutions).

Réponse. La valeur minimale est \(T = 4n\).

Solution 1

Il faut \(T \geq 4n\), sinon on ne peut jamais déplacer la bille de poids \(4n\). Montrons que \(T = 4n\) convient : pour toute configuration initiale, il existe une suite de coups, sans jamais dépasser \(4n\) en valeur absolue de la différence, à l'issue de laquelle chaque bille est passée de l'autre côté. Comme les coups sont réversibles, il suffit d'exhiber au moins une configuration \(C\) pour laquelle on sait le faire, et de montrer que toute configuration initiale peut atteindre une telle configuration \(C\).

Échanger des paires. Groupons les poids en paires \((t, 4n + 1 - t)\), et supposons que chaque plateau contient \(n\) de ces paires. Si un plateau contient la paire \((t, 4n + 1 - t)\) avec \(1 \leq t < 2n\) et que l'autre contient \((2n, 2n + 1)\), la suite de coups suivante échange ces deux paires sans que la différence dépasse \(4n\) (on n'écrit que ces quatre billes ; les autres paires s'équilibrent) :

\[\begin{aligned} &t,\ 4n + 1 - t \ \big|\ 2n,\ 2n + 1 && \text{(différence } 0\text{)} \\ &t,\ 2n,\ 4n + 1 - t \ \big|\ 2n + 1 && \text{(différence } 4n\text{)} \\ &t,\ 2n \ \big|\ 2n + 1,\ 4n + 1 - t && \text{(différence } 4n + 2 - 2t\text{)} \\ &t,\ 2n,\ 2n + 1 \ \big|\ 4n + 1 - t && \text{(différence } 2t\text{)} \\ &2n,\ 2n + 1 \ \big|\ t,\ 4n + 1 - t && \text{(différence } 0\text{)} \end{aligned}\]

En appliquant deux fois cette manœuvre, on échange deux paires quelconques \((t, 4n + 1 - t)\) et \((t', 4n + 1 - t')\) entre les plateaux. On peut donc réaliser n'importe quel échange de paires, et \(C\) peut être n'importe quelle configuration où chaque plateau contient \(n\) paires.

Atteindre une telle configuration. Le poids total vaut \(2n(4n + 1)\) ; posons \(A = n(4n + 1)\). Considérons une configuration où un plateau pèse \(A - s\) et l'autre \(A + s\), avec \(0 \leq s \leq 2n\), et où une paire est séparée entre les deux plateaux (si aucune paire n'est séparée, les deux plateaux ont le même poids et c'est terminé). Les coups permis sont : déplacer un poids \(w\) avec \(1 \leq w \leq 2n + s\) du plateau \(A + s\) vers le plateau \(A - s\), et déplacer un poids \(w\) avec \(1 \leq w \leq 2n - s\) du plateau \(A - s\) vers le plateau \(A + s\). Soit \((t, 4n + 1 - t)\), avec \(t \leq 2n\), une paire séparée. Si \(t\) est sur le plateau \(A + s\), ou sur le plateau \(A - s\) avec \(t \leq 2n - s\), on peut le changer de plateau. Sinon, \(t\) est sur le plateau \(A - s\) et \(t \geq 2n - s + 1\), donc \(4n + 1 - t \leq 2n + s\) est sur le plateau \(A + s\) et peut changer de plateau. On réunit ainsi les deux poids de la paire sans séparer aucune autre paire ; le nombre de paires séparées diminue (monovariant), et en répétant on atteint une configuration sans paire séparée. \(\blacksquare\)

Solution 2

Comme dans la solution 1, \(T \geq 4n\). Notons \(\delta\) le poids du plateau gauche moins celui du plateau droit. Une configuration est légale si \(|\delta| \leq 4n\), et un coup est légal s'il mène à une configuration légale. Montrons que si \(\delta = 0\), il existe une suite de coups légaux après laquelle chaque bille est de l'autre côté.

Pour \(n = 1\), la configuration initiale a les billes \(1, 4\) d'un côté et \(2, 3\) de l'autre ; déplacer les billes \(2, 4, 3, 1\) dans cet ordre est légal et convient. On suppose désormais \(n \geq 2\). Les billes de poids au plus \(2n\) sont dites petites.

Lemme 1. Si deux configurations légales ne diffèrent que par la position de petites billes, on peut passer de l'une à l'autre par des coups légaux.

Preuve. On commence par ne déplacer que des billes mal placées qui ne sont pas sur le plateau le plus léger (en cas d'égalité, aucun plateau n'est le plus léger) ; un tel coup est toujours légal (il s'agit d'une petite bille, de poids \(\leq 2n\), retirée du plateau le plus lourd). Le nombre de billes mal placées diminue (monovariant), donc cette phase s'arrête. Alors les seules billes mal placées sont sur le plateau le plus léger ; en les déplaçant une à une, \(|\delta|\) augmente à chaque coup, et \(|\delta| \leq 4n\) à la fin (la configuration cible est légale). Tous ces coups sont donc légaux. \(\square\)

Lemme 2. Soit \(k \in \mathbb{N}^*\). Un entier strictement positif est somme d'entiers distincts de \(\{1, \ldots, k\}\) si et seulement s'il est au plus égal à \(\frac{k(k+1)}{2}\).

Preuve. La plus grande somme possible vaut \(\frac{k(k+1)}{2}\). Réciproquement, par récurrence sur \(k\) : le cas \(k = 1\) est trivial ; un entier au plus égal à \(k\) s'écrit avec un seul terme, et pour un entier plus grand (et \(\leq \frac{k(k+1)}{2}\)), on prend le terme \(k\) et l'on applique l'hypothèse de récurrence au reste, qui est entre \(1\) et \(\frac{(k-1)k}{2}\). \(\square\)

Notons aussi que \(n(2n + 1) \geq 4n\) pour \(n \geq 2\) : le poids total des petites billes est au moins \(4n\).

Déplacer une bille non petite. Soit \(2n < m \leq 4n\). Les billes de poids \(> m\) sont dites grosses, et celles de poids \(2n + 1\) à \(m\) moyennes. Supposons que toutes les grosses billes sont du bon côté (opposé à leur côté de départ), que \(m\) est du mauvais côté et que la configuration est légale. Les étapes suivantes donnent une suite de coups légaux après laquelle \(m\) est du bon côté, sans que les grosses billes aient bougé. Supposons \(m\) à gauche. À l'étape 2, on réarrange les petites billes pour pouvoir déplacer \(m\) ; ce n'est possible que si le poids des billes moyennes et grosses à droite n'est pas trop grand, d'où l'étape 1 qui retire si besoin des billes moyennes de la droite.

Étape 1. Si le poids total des billes moyennes et grosses à droite est au plus \(n(4n + 1) + 2n - m\), on passe à l'étape 2. Sinon : comme les grosses billes sont du bon côté et \(m\) du mauvais, les grosses billes à droite sont parties de gauche avec \(m\), et pèsent au plus \(n(4n + 1) - m\). Il y a donc à droite une bille moyenne \(m' < m\). Comme le poids à droite reste supérieur à \(n(4n+1) + 2n - m\), il est légal de ramener toutes les petites billes à gauche. Puis, par le lemme 2, on peut renvoyer à droite des petites billes de sorte que le plateau droit pèse exactement \(n(4n + 1) + 2n\) (soit \(\delta = -4n\)). Déplacer alors \(m'\) vers la gauche est légal. On répète cette étape ; comme le poids total des billes moyennes à droite diminue, elle n'a lieu qu'un nombre fini de fois.

Étape 2. Notons \(n(4n + 1) + 2n - m + x\) le poids total du plateau droit et \(y\) le poids des petites billes à droite ; on a \(y \geq x\). Si \(x \leq 0\), déplacer \(m\) est légal. Sinon, par le lemme 2, il existe un ensemble de petites billes de poids \(y - x\). Par le lemme 1, il existe une suite de coups légaux de petites billes après laquelle le plateau droit pèse exactement \(n(4n + 1) + 2n - m\). Déplacer alors \(m\) vers la droite est légal (on obtient \(\delta = -4n\)).

En appliquant ce procédé pour \(m = 4n, 4n - 1, \ldots, 2n + 1\), toutes les billes non petites passent de l'autre côté. Le lemme 1 permet enfin de faire passer les petites billes, ce qui achève la preuve. \(\blacksquare\)

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2022 C4 ★★☆☆☆ : \(n\) pièces entre \(n\) enfants en cercle ; un enfant peut donner une pièce à chaque voisin : quelles distributions mènent à une pièce chacun ?
  • 2006 C4 ★★★☆☆ : Deux placements de fraises, une par ligne et par colonne, comparés par rectangles de coin : on passe de l'un à l'autre par des échanges élémentaires.
  • 2022 C7 ★★★★☆ : Avec sommes et maxima coordonnée par coordonnée, combien d'uplets de départ faut-il pour tout engendrer ?
  • 2009 C8 ★★★★★ : Une opération sur l'écriture décimale qui duplique un bloc de chiffres finit toujours par atteindre \(1\).