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)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
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) :
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\)