Shortlist 2022, C6¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Croatia
Concepts : Récurrence et constructions récursives · Invariants et monovariants · Divisibilité, PGCD et algorithme d'Euclide
Solution officielle : Shortlist officielle 2022 (avec solutions), p. 32 (page 34 du PDF)
Énoncé¶
Let \(n\) be a positive integer. We start with \(n\) piles of pebbles, each initially containing a single pebble. One can perform moves of the following form: choose two piles, take an equal number of pebbles from each pile and form a new pile out of these pebbles. For each positive integer \(n\), find the smallest number of non-empty piles that one can obtain by performing a finite sequence of moves of this form.
Indices : les idées clés
- Réponse : \(1\) si \(n\) est une puissance de \(2\), et \(2\) sinon.
- Récurrence et constructions récursives : en fusionnant deux à deux des piles égales, \(2^k\) piles d'un caillou donnent une pile de \(2^k\) ; on construit ainsi deux piles dans le cas général (solutions 1 et 2).
- Invariants et monovariants : si, après un coup, toutes les piles sont divisibles par un entier impair \(d\), elles l'étaient déjà avant ; une pile unique de \(n\) cailloux est donc impossible si \(n\) a un diviseur impair \(> 1\).
- Divisibilité, PGCD et algorithme d'Euclide : la notion clé est celle de diviseur impair commun à toutes les piles.
- Raisonner à rebours (solution 3) : on inverse les coups (couper une pile paire en deux moitiés) et on caractérise toutes les configurations atteignables.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2022 (trois solutions et une remarque, accompagnées d'une remarque commune).
Remarque commune du livret. Au lieu de prendre des cailloux dans deux piles, on pourrait autoriser à prendre le même nombre de cailloux dans chacune de \(k\) piles, où \(k \geq 2\) est un entier (premier) fixé. Cela semble donner un problème bien plus difficile : pour \(k = 3\), des expériences numériques suggèrent la même réponse que pour \(k = 2\) (avec des puissances de \(3\) à la place des puissances de \(2\)), mais le cas \(k = 5\) est déjà obscur.
Solution 1¶
Réponse : \(1\) si \(n\) est une puissance de \(2\), et \(2\) sinon.
La solution présentée est simple, mais pas la plus efficace.
Cas où \(n\) est une puissance de \(2\). On peut fusionner deux piles de \(2^{k-1}\) cailloux en une pile de \(2^k\) cailloux. En particulier, à partir de \(2^k\) piles d'un caillou :
Cela prouve le résultat quand \(n\) est une puissance de \(2\).
Cas où \(n\) n'est pas une puissance de \(2\) : on obtient deux piles. Soit \(N\) tel que \(2^N < n < 2^{N+1}\), et \(m = n - 2^N\), de sorte que \(0 < m < 2^N\). On forme une pile de \(2^N\) cailloux, appelée la grande pile. (On pourrait être plus économe et former une pile de \(2^{M}\) cailloux avec \(m \leq 2^M\).) Comme \(n\) n'est pas une puissance de deux, il reste au moins une autre pile ; toutes les autres piles ont un seul caillou.
On choisit une pile d'un caillou, on prend ce caillou et un caillou de la grande pile, et on forme une pile de \(2\). Si \(m < 2^N - 1\), on prend encore un caillou de la grande pile et un caillou de la pile de \(2\), et on forme une nouvelle pile de \(2\). On répète jusqu'à ce que la grande pile contienne exactement \(m\) cailloux.
On a alors une pile de \(m\) cailloux, une pile de \(2\) cailloux, et des piles d'un caillou, au nombre de \(n - m - 2 = 2^N - 2\). On les regroupe deux par deux en piles de \(2\). On obtient \(2^{N-1}\) piles de \(2\), qu'on fusionne (comme ci-dessus) en une pile de \(2^N\). Il reste exactement deux piles.
Une seule pile est impossible si \(n\) n'est pas une puissance de \(2\). Un coup consiste à choisir deux piles de \(a\) et \(b\) cailloux, à retirer \(c \leq \min(a, b)\) cailloux de chacune et à former une nouvelle pile de \(2c\) cailloux. En comptant les piles vides, un coup modifie trois piles ainsi (les autres sont inchangées) :
Supposons qu'après le coup, toutes les piles soient divisibles par un entier impair \(d\). En particulier \(d \mid 2c\), \(d \mid a - c\) et \(d \mid b - c\). Comme \(d\) est impair, \(d \mid c\), puis \(d \mid a\) et \(d \mid b\). Donc, avant le coup aussi, toutes les piles étaient divisibles par \(d\) (invariant, lu à rebours).
Si \(n\) n'est pas une puissance de \(2\), \(n\) est divisible par un entier impair \(d > 1\) (divisibilité). Pour obtenir une seule pile de \(n\) cailloux, il faudrait partir d'une configuration où toutes les piles sont divisibles par \(d\), ce qui est faux pour des piles d'un caillou. \(\blacksquare\)
Solution 2¶
On donne une autre stratégie lorsque \(n\) n'est pas une puissance de \(2\) (le reste est comme dans la solution 1). On écrit \(n\) en binaire : \(n = 2^{i_1} + 2^{i_2} + \cdots + 2^{i_k}\) avec \(i_1 > i_2 > \cdots > i_k\) et \(k \geq 2\). On forme d'abord des piles de tailles \(2^{i_1}, 2^{i_2}, \ldots, 2^{i_k}\) (comme dans la solution 1). La pile de \(2^{i_1}\) est la grande pile, les autres sont les petites piles.
Stratégie : on prend les deux plus petites petites piles. Si elles ont la même taille \(2^a\), on les fusionne en une pile de \(2^{a+1}\). Si elles ont des tailles différentes, on double la plus petite à l'aide de la grande pile (on autorise provisoirement la grande pile à avoir un nombre négatif de cailloux : on montre ensuite que cela n'arrive pas). Toutes les nouvelles piles sont dites petites. Quand il ne reste qu'une petite pile, on s'arrête : il y a au plus \(2\) piles.
Toutes les piles restent des puissances de \(2\), et le processus se termine. (Précision ajoutée : le livret dit que chaque coup diminue le nombre de piles ; en fait c'est le cas de chaque fusion, et entre deux fusions la plus petite pile double, ce qui ne peut se produire qu'un nombre fini de fois.) Le nombre de cailloux de la grande pile ne fait que diminuer, et à la fin du processus, il vaut \(n - 2^{i_2 + 1} \geq n - 2^{i_1} > 0\). On obtient donc bien deux piles. \(\blacksquare\)
Solution 3¶
On considère les coups à rebours : on dispose de piles, et un coup consiste à prendre une pile ayant un nombre pair de cailloux, à la couper en deux moitiés égales et à ajouter chaque moitié à une pile différente, éventuellement vide (on suppose qu'il y a toujours une infinité de piles vides). Pour une configuration \(C\), on note \(|C|\) le nombre de piles non vides. Une configuration \(C_2\) est accessible depuis \(C_1\) si on peut l'obtenir à partir de \(C_1\) par une suite finie de coups. Une configuration \(C\) est dite :
- simple si chaque pile non vide contient un seul caillou ;
- bonne si au moins une pile non vide contient un nombre pair de cailloux et si les tailles des piles n'ont aucun diviseur commun impair non trivial (on dit que \(C\) a la propriété du diviseur impair) ;
- résoluble s'il existe une configuration simple accessible depuis \(C\).
Le problème demande le plus petit nombre de piles non vides d'une configuration résoluble de \(n\) cailloux.
Lemme 1. Soit \(C'\) obtenue à partir de \(C\) par un coup. Alors (i) si \(C'\) a la propriété du diviseur impair, \(C\) aussi ; (ii) la réciproque de (i) est vraie si \(|C'| \geq |C|\).
Preuve. Supposons que le coup coupe une pile de \(2a\) cailloux et ajoute \(a\) cailloux à deux piles de tailles \(b\) et \(c\) (\(a \geq 1\), \(b, c \geq 0\)). Ainsi \(C'\) s'obtient à partir de \(C\) en remplaçant les piles \(2a, b, c\) par deux piles \(a + b\) et \(a + c\). La condition \(|C'| \geq |C|\) de (ii) équivaut à : \(b\) ou \(c\) est nul.
(i) Si \(C\) n'a pas la propriété, il existe \(d > 1\) impair divisant toutes les piles de \(C\). En particulier \(d\) divise \(2a, b, c\), donc (car \(d\) est impair) \(a\), \(b\), \(c\), puis \(a + b\) et \(a + c\). Donc \(d\) divise toutes les piles de \(C'\), qui n'a pas la propriété.
(ii) Si \(C'\) n'a pas la propriété et si \(b\) ou \(c\) est nul, il existe \(d > 1\) impair divisant toutes les piles de \(C'\), en particulier \(a + b\) et \(a + c\). L'un de ces nombres vaut \(a\), donc \(d \mid a\), puis \(d\) divise \(a\), \(b\) et \(c\), donc \(2a\), \(b\) et \(c\). Ainsi \(C\) n'a pas la propriété. \(\square\)
Lemme 2. Si \(C_2\) est accessible depuis \(C_1\) et a la propriété du diviseur impair, alors \(C_1\) aussi. En particulier, toute configuration résoluble a la propriété du diviseur impair.
Preuve. La première partie s'obtient en appliquant (i) du lemme 1 par récurrence sur le nombre de coups ; la seconde en découle, car toute configuration simple a la propriété. \(\square\)
Lemme 3. Soit \(C\) une bonne configuration. Il existe une configuration \(C'\) telle que :
- \(C'\) est accessible depuis \(C\) et \(|C'| > |C|\) ;
- \(C'\) est simple ou bonne.
Preuve. Appelons terminale une configuration qui est un contre-exemple à ce lemme.
Affirmation. Soient \(a_1, \ldots, a_k\) les tailles des piles non vides d'une configuration terminale \(C\). Il existe un unique \(i \in \{1, \ldots, k\}\) tel que \(a_i\) est pair. De plus, pour tout \(t \geq 1\), on a \(a_j \equiv \frac{a_i}{2} \pmod{2^t}\) pour tout \(j \neq i\).
Preuve de l'affirmation. Comme \(C\) est bonne, il existe \(i\) tel que \(a_i\) est pair. Si l'on coupe la pile \(a_i\) en deux moitiés placées sur deux piles vides, la configuration obtenue a une pile de plus, donc n'est ni simple ni bonne (car \(C\) est terminale). Par (ii) du lemme 1, elle a la propriété du diviseur impair ; elle n'est donc pas bonne seulement si toutes ses piles sont impaires : \(\frac{a_i}{2}\) et les \(a_j\) (\(j \neq i\)) sont impairs. (Le livret renvoie ici, et plus bas, à « la partie (ii) du lemme 2 » ; il s'agit du lemme 1 (ii).)
Pour la seconde assertion, on raisonne par récurrence sur \(t\), le cas \(t = 1\) venant d'être établi. Soit \(t \geq 2\). On coupe la pile \(a_i\) en deux moitiés, l'une ajoutée à la pile \(a_j\), l'autre placée sur une pile vide. Comme \(\frac{a_i}{2}\) et \(a_j\) sont impairs, \(a_j + \frac{a_i}{2}\) est pair, donc par (ii) du lemme 1 la configuration \(C'\) obtenue est bonne. Elle a autant de piles que \(C\), donc elle est elle aussi terminale (sinon une configuration convenable accessible depuis \(C'\) le serait depuis \(C\)). Par hypothèse de récurrence appliquée à \(C'\) (dont l'unique pile paire est \(a_j + \frac{a_i}{2}\)), on a \(\frac{a_i}{2} \equiv \frac{1}{2}\left(a_j + \frac{a_i}{2}\right) \pmod{2^{t-1}}\), d'où \(a_j \equiv \frac{a_i}{2} \pmod{2^t}\). \(\square\)
Supposons par l'absurde qu'il existe une configuration comme dans l'affirmation. Alors il existe \(i\) et un entier impair \(x\) tels que \(a_i = 2x\) et \(a_j = x\) pour tout \(j \neq i\). Ainsi \(x\) est un diviseur commun impair de \(a_1, \ldots, a_k\) ; par la propriété du diviseur impair, \(x = 1\). Mais alors, en coupant l'unique pile de \(2\) cailloux en deux piles d'un caillou, on obtient une configuration simple avec une pile de plus : contradiction. \(\square\)
Lemme 4. Une configuration \(C\) est résoluble si et seulement si elle est simple ou bonne.
Preuve. (\(\Rightarrow\)) Si \(C\) n'est pas simple, il faut pouvoir faire au moins un coup, donc \(C\) a une pile paire non vide. De plus, par le lemme 2, \(C\) a la propriété du diviseur impair : elle est donc bonne.
(\(\Leftarrow\)) On applique le lemme 3 de façon répétée jusqu'à obtenir une configuration simple. Le processus s'arrête, car le nombre de piles non vides augmente à chaque fois et est majoré (par \(n\)). \(\square\)
Lemme 5. Soit \(n \geq 1\). (i) La configuration formée d'une seule pile de \(n\) cailloux est résoluble si et seulement si \(n\) est une puissance de \(2\). (ii) Si \(n \geq 2\), la configuration formée de deux piles de \(2\) et \(n - 2\) cailloux est bonne, donc résoluble.
Preuve. (i) Par le lemme 4, cette configuration est résoluble si et seulement si \(n = 1\), ou bien \(n\) est pair et sans diviseur impair non trivial, d'où la conclusion. (ii) \(2\) est pair et n'a pas de diviseur impair non trivial, donc la configuration est bonne, et le lemme 4 conclut. \(\square\)
Le lemme 5 donne la réponse : une pile si \(n\) est une puissance de \(2\), et deux piles sinon. \(\blacksquare\)
Remarques¶
Remarque 1 (configurations de départ quelconques). Le livret étudie, à la suite de la solution 1, des configurations de départ quelconques de \(n\) cailloux. Si \(n\) est une puissance de \(2\), on peut toujours obtenir une seule pile : tant qu'il y a au moins deux piles d'au moins \(2\) cailloux, on retire un caillou à deux telles piles pour former une pile de \(2\) ; on se ramène ainsi à une pile de \(2\) cailloux et des piles d'un caillou, puis on procède comme dans la solution. Si \(n = 2^k m\) avec \(m > 1\) impair, on peut obtenir une seule pile à partir de toute configuration où toutes les piles sont divisibles par \(m\), et sinon deux piles est le mieux possible. La moitié est déjà prouvée ; pour l'autre, on remplace chaque pile de \(tm\) cailloux par une pile de \(t\) « rochers » : on a \(2^k\) rochers au total, qu'on regroupe en une seule pile, puis on revient aux cailloux.