Shortlist 2010, C4¶

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

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

Solution officielle : Shortlist officielle 2010 (avec solutions), p. 30 (page 31 du PDF)

Problème 5 de l'OIM 2010

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

Énoncé¶

Six stacks \(S_1, \ldots, S_6\) of coins are standing in a row. In the beginning every stack contains a single coin. There are two types of allowed moves:

Move 1: If stack \(S_k\) with \(1 \leq k \leq 5\) contains at least one coin, you may remove one coin from \(S_k\) and add two coins to \(S_{k+1}\).

Move 2: If stack \(S_k\) with \(1 \leq k \leq 4\) contains at least one coin, then you may remove one coin from \(S_k\) and exchange stacks \(S_{k+1}\) and \(S_{k+2}\).

Decide whether it is possible to achieve by a sequence of such moves that the first five stacks are empty, whereas the sixth stack \(S_6\) contains exactly \(2010^{2010^{2010}}\) coins.

Indices : les idées clés

Lemme 1 : \((a, 0, 0) \to (0, 2^a, 0)\), en vidant le tas du milieu par le mouvement 1 puis en échangeant par le mouvement 2.
Lemme 2 : \((a, 0, 0, 0) \to (0, P_a, 0, 0)\) où \(P_n\) est une tour de \(n\) puissances de \(2\) ; on obtient ainsi \(P_{16}\) pièces, bien plus que \(A\).
Réduction : le mouvement 2 appliqué à un tas suivi de deux tas vides retire une pièce sans rien changer d'autre (quantité contrôlée), ce qui permet de descendre exactement à \(A/4\).

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2010 (une solution et deux remarques). Le livret propose aussi la variante C4' : même problème avec \(2010^{2010}\) au lieu de \(2010^{2010^{2010}}\).

Réponse : oui (dans les deux variantes du problème). Il existe une telle suite de mouvements.

Solution¶

On note \((a_1, a_2, \ldots, a_n) \to (a'_1, a'_2, \ldots, a'_n)\) la propriété suivante : si des tas consécutifs contiennent \(a_1, \ldots, a_n\) pièces, alors on peut effectuer plusieurs mouvements autorisés de sorte que ces tas contiennent \(a'_1, \ldots, a'_n\) pièces respectivement, le contenu des autres tas restant inchangé.

Soit \(A = 2010^{2010}\) ou \(A = 2010^{2010^{2010}}\) respectivement. Notre but est de montrer que

\[(1, 1, 1, 1, 1, 1) \to (0, 0, 0, 0, 0, A).\]

Prouvons d'abord deux observations auxiliaires.

Lemme 1. \((a, 0, 0) \to (0, 2^a, 0)\) pour tout \(a \geq 1\).

Preuve. Montrons par récurrence que \((a, 0, 0) \to (a - k, 2^k, 0)\) pour tout \(1 \leq k \leq a\). Pour \(k = 1\), on applique le mouvement 1 au premier tas :

\[(a, 0, 0) \to (a - 1, 2, 0) = (a - 1, 2^1, 0).\]

Supposons maintenant \(k < a\) et l'énoncé vrai pour ce \(k\). En partant de \((a - k, 2^k, 0)\), appliquons \(2^k\) fois le mouvement 1 au tas du milieu, jusqu'à le vider. Appliquons ensuite le mouvement 2 au premier tas :

\[(a - k, 2^k, 0) \to (a - k, 2^k - 1, 2) \to \cdots \to (a - k, 0, 2^{k+1}) \to (a - k - 1, 2^{k+1}, 0).\]

Donc

\[(a, 0, 0) \to (a - k, 2^k, 0) \to (a - k - 1, 2^{k+1}, 0). \qquad \square\]

Lemme 2. Pour tout entier \(n > 0\), posons \(P_n = \underbrace{2^{2^{\cdot^{\cdot^{2}}}}}_{n}\) (par exemple \(P_3 = 2^{2^2} = 16\)). Alors \((a, 0, 0, 0) \to (0, P_a, 0, 0)\) pour tout \(a \geq 1\).

Preuve. Comme pour le lemme 1, montrons que \((a, 0, 0, 0) \to (a - k, P_k, 0, 0)\) pour tout \(1 \leq k \leq a\). Pour \(k = 1\), on applique le mouvement 1 au premier tas :

\[(a, 0, 0, 0) \to (a - 1, 2, 0, 0) = (a - 1, P_1, 0, 0).\]

Supposons maintenant le lemme vrai pour un \(k < a\). En partant de \((a - k, P_k, 0, 0)\), appliquons le lemme 1, puis le mouvement 2 au premier tas :

\[(a - k, P_k, 0, 0) \to (a - k, 0, 2^{P_k}, 0) = (a - k, 0, P_{k+1}, 0) \to (a - k - 1, P_{k+1}, 0, 0).\]

Donc

\[(a, 0, 0, 0) \to (a - k, P_k, 0, 0) \to (a - k - 1, P_{k+1}, 0, 0). \qquad \square\]

Prouvons maintenant l'énoncé du problème. Appliquons d'abord le mouvement 1 au tas \(5\), puis le mouvement 2 aux tas \(S_4\), \(S_3\), \(S_2\) et \(S_1\) dans cet ordre. Appliquons ensuite deux fois le lemme 2 :

\[\begin{aligned} (1, 1, 1, 1, 1, 1) &\to (1, 1, 1, 1, 0, 3) \to (1, 1, 1, 0, 3, 0) \to (1, 1, 0, 3, 0, 0) \to (1, 0, 3, 0, 0, 0) \\ &\to (0, 3, 0, 0, 0, 0) \to (0, 0, P_3, 0, 0, 0) = (0, 0, 16, 0, 0, 0) \to (0, 0, 0, P_{16}, 0, 0). \end{aligned}\]

On a déjà plus de \(A\) pièces dans le tas \(S_4\), puisque

\[A \leq 2010^{2010^{2010}} < (2^{11})^{2010^{2010}} = 2^{11 \cdot 2010^{2010}} < 2^{2010^{2011}} < 2^{(2^{11})^{2011}} = 2^{2^{11 \cdot 2011}} < 2^{2^{2^{15}}} < P_{16}.\]

Pour diminuer le nombre de pièces du tas \(S_4\), appliquons-lui le mouvement 2 de façon répétée jusqu'à ce que sa taille soit \(A/4\). (À chaque étape, on retire une pièce de \(S_4\) et l'on échange les tas vides \(S_5\) et \(S_6\).)

\[(0, 0, 0, P_{16}, 0, 0) \to (0, 0, 0, P_{16} - 1, 0, 0) \to (0, 0, 0, P_{16} - 2, 0, 0) \to \cdots \to (0, 0, 0, A/4, 0, 0).\]

Enfin, appliquons le mouvement 1 de façon répétée pour vider les tas \(S_4\) et \(S_5\) :

\[(0, 0, 0, A/4, 0, 0) \to \cdots \to (0, 0, 0, 0, A/2, 0) \to \cdots \to (0, 0, 0, 0, 0, A). \qquad \blacksquare\]

Remarques¶

Remarque 1. En partant de seulement \(4\) tas, on vérifie sans difficulté à la main qu'on peut obtenir au plus \(28\) pièces dans la dernière position. Mais autour de \(5\) et \(6\) tas, le nombre maximal de pièces explose. Avec \(5\) tas, on peut obtenir plus de \(2^{2^{14}}\) pièces. Avec \(6\) tas, le maximum est supérieur à \(P_{P_{2^{14}}}\).

On montre sans difficulté que les nombres \(2010^{2010}\) et \(2010^{2010^{2010}}\) de l'énoncé peuvent être remplacés par n'importe quel entier positif ou nul inférieur ou égal à \(P_{P_{2^{14}}}\).

Remarque 2. La variante plus simple C4' du problème peut se résoudre sans le lemme 2 :

\[\begin{aligned} (1, 1, 1, 1, 1, 1) &\to (0, 3, 1, 1, 1, 1) \to (0, 1, 5, 1, 1, 1) \to (0, 1, 1, 9, 1, 1) \\ &\to (0, 1, 1, 1, 17, 1) \to (0, 1, 1, 1, 0, 35) \to (0, 1, 1, 0, 35, 0) \to (0, 1, 0, 35, 0, 0) \\ &\to (0, 0, 35, 0, 0, 0) \to (0, 0, 1, 2^{34}, 0, 0) \to (0, 0, 1, 0, 2^{2^{34}}, 0) \to (0, 0, 0, 2^{2^{34}}, 0, 0) \\ &\to (0, 0, 0, 2^{2^{34}} - 1, 0, 0) \to \cdots \to (0, 0, 0, A/4, 0, 0) \to (0, 0, 0, 0, A/2, 0) \to (0, 0, 0, 0, 0, A). \end{aligned}\]

C'est pourquoi le comité de sélection suggère de considérer aussi le problème C4. Le problème C4 demande plus d'invention et de soin technique. D'autre part, l'énoncé de C4' cache le fait que le nombre de pièces obtenu peut être incroyablement grand, et laisse cette découverte aux élèves.