Shortlist 2017, C3¶
Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : Thailand
Concepts : Récurrence et constructions récursives · Suites et récurrences · Invariants et monovariants · Bijections et dénombrement
Solution officielle : Shortlist officielle 2017 (avec solutions), p. 38 (page 40 du PDF)
Énoncé¶
Sir Alex plays the following game on a row of \(9\) cells. Initially, all cells are empty. In each move, Sir Alex is allowed to perform exactly one of the following two operations:
(1) Choose any number of the form \(2^j\), where \(j\) is a non-negative integer, and put it into an empty cell.
(2) Choose two (not necessarily adjacent) cells with the same number in them; denote that number by \(2^j\). Replace the number in one of the cells with \(2^{j+1}\) and erase the number in the other cell.
At the end of the game, one cell contains the number \(2^n\), where \(n\) is a given positive integer, while the other cells are empty. Determine the maximum number of moves that Sir Alex could have made, in terms of \(n\).
Indices : les idées clés
- Généraliser à une rangée de \(k\) cases et noter \(m(n, k)\) le nombre maximal de coups.
- Récurrence et constructions récursives (solution 1) : en coloriant en bleu et rouge les nombres selon la moitié \(2^{n-1}\) dont ils proviennent, on obtient \(m(n, k) = m(n-1, k) + m(n-1, k-1) + 1\), avec une construction qui atteint cette valeur.
- Suites et récurrences (solution 1) : on résout cette récurrence à deux indices par récurrence sur \(n\), grâce à la formule de Pascal.
- Invariants et monovariants (solution 2) : la somme \(S\) des nombres augmente à chaque insertion et ne change pas lors d'une fusion ; le nombre de cases occupées donne « insertions \(=\) fusions \(+ 1\) ».
- Dénombrement (solution 2) : le nombre d'entiers \(\leq 2^n\) ayant au plus \(k - 1\) chiffres \(1\) en base \(2\) vaut \(\sum_{j=0}^{k-1}\binom nj\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2017 (deux solutions et deux remarques).
Réponse. \(\displaystyle 2\sum_{j=0}^{8}\binom nj - 1\).
Solution 1¶
On résout un problème plus général, en remplaçant la rangée de \(9\) cases par une rangée de \(k\) cases, \(k\) entier positif. Notons \(m(n, k)\) le nombre maximal de coups que Sir Alex peut faire en partant d'une rangée de \(k\) cases vides et en terminant avec une case contenant \(2^n\) et les \(k - 1\) autres vides. On appelle une opération de type (1) une insertion et une opération de type (2) une fusion.
Un seul coup est possible quand \(k = 1\), donc \(m(n, 1) = 1\). On considère désormais \(k \geq 2\), et on peut supposer que le dernier coup est une fusion. Juste avant ce dernier coup, il y avait exactement deux cases contenant \(2^{n-1}\), les \(k - 2\) autres étant vides. Coloriez l'un de ces nombres \(2^{n-1}\) en bleu et l'autre en rouge. Remontons alors le temps en coloriant les nombres selon la règle : si \(a\) et \(b\) fusionnent en \(c\), on colorie \(a\) et \(b\) de la couleur de \(c\). Dans ce processus à rebours, de nouveaux nombres n'apparaissent qu'en défaisant des fusions, car défaire une insertion revient simplement à effacer un nombre. Tous les nombres apparus au cours de la partie reçoivent donc une des deux couleurs.
Le premier coup est une insertion ; sans perte de généralité, le premier nombre inséré est bleu. À partir de là et jusqu'au dernier coup, il y a toujours au moins une case contenant un nombre bleu.
À part le dernier coup, aucun coup ne fait intervenir à la fois un nombre bleu et un nombre rouge, car toutes les fusions concernent des nombres de même couleur et les insertions ne concernent qu'un nombre. On appelle coup bleu l'insertion d'un nombre bleu ou la fusion de deux nombres bleus, et on définit de même les coups rouges.
La suite des coups bleus pourrait être rejouée seule sur une autre rangée de \(k\) cases et produirait une case contenant \(2^{n-1}\), les autres étant vides ; il y a donc au plus \(m(n-1, k)\) coups bleus.
Passons aux coups rouges. Comme à chaque coup rouge au moins une case est occupée par un nombre bleu, la suite des coups rouges pourrait être rejouée sur une rangée de \(k - 1\) cases et produirait une case contenant \(2^{n-1}\), les autres étant vides ; il y a donc au plus \(m(n-1, k-1)\) coups rouges. Ceci prouve que
Réciproquement, on peut partir d'une rangée vide de \(k\) cases et faire \(m(n-1, k)\) coups pour obtenir une case contenant \(2^{n-1}\), les autres vides ; puis faire \(m(n-1, k-1)\) coups sur les \(k - 1\) cases vides pour obtenir \(2^{n-1}\) dans l'une d'elles, en laissant \(k - 2\) cases vides. Une fusion de plus donne une case avec \(2^n\) et les autres vides, d'où
Il s'ensuit que
pour \(n \geq 1\) et \(k \geq 2\).
Si \(k = 1\) ou \(n = 0\), on doit insérer \(2^n\) au premier coup et on obtient immédiatement la configuration finale ; donc \(m(0, k) = 1\) et \(m(n, 1) = 1\) pour \(n \geq 0\) et \(k \geq 1\). Ces valeurs initiales, avec la relation de récurrence (1), déterminent \(m(n, k)\) de façon unique.
Montrons enfin que
pour tous entiers \(n \geq 0\) et \(k \geq 1\). On raisonne par récurrence sur \(n\). Comme \(m(0, k) = 1\) pour \(k \geq 1\), (2) est vraie pour \(n = 0\). Supposons (2) vraie pour un entier \(n\) fixé et tout \(k \geq 1\). On a \(m(n+1, 1) = 1 = 2\binom{n+1}{0} - 1\), et pour \(k \geq 2\), la relation (1) et l'hypothèse de récurrence donnent
avec la convention \(\binom{n}{-1} = 0\) et la formule de Pascal, ce qui achève la preuve. Pour \(k = 9\), on obtient la réponse \(2\sum_{j=0}^{8}\binom nj - 1\). \(\blacksquare\)
Solution 2¶
On définit insertions et fusions comme dans la solution 1. Après chaque coup, on calcule le nombre \(N\) de cases occupées et la somme \(S\) de tous les nombres écrits dans les cases. Une insertion augmente toujours \(S\) d'une puissance de \(2\) et augmente \(N\) d'exactement \(1\). Une fusion ne change pas \(S\) et diminue \(N\) d'exactement \(1\). Comme \(N\) vaut \(0\) au départ et \(1\) à la fin, le nombre d'insertions dépasse exactement de \(1\) celui des fusions. Pour maximiser le nombre de coups, il faut donc maximiser le nombre d'insertions.
Le livret dit « le nombre \(N\) de cases vides » ; vu la suite (valeur initiale \(0\), valeur finale \(1\)), il faut lire « cases non vides ».
On travaille avec \(k\) cases. On aura besoin du lemme suivant.
Lemme. Si l'écriture binaire d'un entier \(A > 0\) a \(d\) chiffres non nuls, alors \(A\) ne peut pas s'écrire comme somme de moins de \(d\) puissances de \(2\). De plus, toute écriture de \(A\) comme somme de \(d\) puissances de \(2\) coïncide avec son écriture binaire.
Preuve. Soit \(s\) le nombre minimal de termes dans une écriture de \(A\) comme somme de puissances de \(2\). Supposons qu'une telle écriture à \(s\) termes contienne deux termes égaux. En les remplaçant par leur somme (une puissance de \(2\)), on obtient une écriture à moins de \(s\) termes, contradiction. Donc dans toute écriture à \(s\) termes les termes sont distincts, et une telle écriture coïncide avec l'unique écriture binaire de \(A\) ; ainsi \(s = d\). \(\square\)
Affirmation 1. Après chaque coup, \(S\) est la somme d'au plus \(k - 1\) puissances de \(2\) distinctes.
Preuve. Si \(S\) était la somme de \(k\) (ou plus) puissances de \(2\) distinctes, le lemme impliquerait que les \(k\) cases sont remplies par ces nombres. C'est impossible, car aucune fusion ni insertion ne pourrait plus être faite (et la partie doit se terminer avec une seule case occupée). \(\square\)
Notons \(A(n, k-1)\) l'ensemble des entiers strictement positifs inférieurs ou égaux à \(2^n\) ayant au plus \(k - 1\) chiffres non nuls en base \(2\). Comme chaque insertion augmente strictement \(S\) (monovariant), l'affirmation 1 montre que le nombre total d'insertions est au plus \(|A(n, k-1)|\). Montrons que ce nombre d'insertions peut être atteint.
Affirmation 2. Écrivons \(A(n, k-1) = \{a_1, a_2, \ldots, a_m\}\) avec \(a_1 < a_2 < \cdots < a_m\). Si, après certains coups, \(S = a_j\) avec \(j \in \{1, \ldots, m-1\}\), alors il existe une suite de coups à l'issue de laquelle \(S = a_{j+1}\) exactement.
Preuve. Supposons \(S = a_j\). En effectuant toutes les fusions possibles, on arrive à des puissances de \(2\) distinctes dans toutes les cases non vides. D'après l'affirmation 1, il reste alors au moins une case vide, dans laquelle on veut insérer \(a_{j+1} - a_j\). Il reste à montrer que \(a_{j+1} - a_j\) est une puissance de \(2\).
Si \(a_j\) a moins de \(k - 1\) chiffres non nuls en base \(2\), alors \(a_{j+1} = a_j + 1\). Sinon, \(a_j = 2^{b_{k-1}} + \cdots + 2^{b_2} + 2^{b_1}\) avec \(b_1 < b_2 < \cdots < b_{k-1}\). Ajouter à \(a_j\) un nombre strictement inférieur à \(2^{b_1}\) donne un nombre ayant plus de \(k - 1\) chiffres binaires non nuls. D'autre part, \(a_j + 2^{b_1}\) est une somme de \(k\) puissances de \(2\) non toutes distinctes, donc, d'après le lemme, une somme de moins de \(k\) puissances de \(2\) distinctes. Ainsi \(a_{j+1} - a_j = 2^{b_1}\). \(\square\)
Les affirmations 1 et 2 montrent que le nombre maximal d'insertions est \(|A(n, k-1)|\). Calculons ce nombre.
Affirmation 3. \(|A(n, k-1)| = \sum_{j=0}^{k-1}\binom nj\).
Preuve. Le nombre \(2^n\) est le seul élément de \(A(n, k-1)\) ayant \(n + 1\) chiffres binaires. Tout autre élément a au plus \(n\) chiffres binaires, dont au moins un et au plus \(k - 1\) sont non nuls (donc égaux à \(1\)). Pour chaque \(j \in \{1, \ldots, k-1\}\), il y a \(\binom nj\) tels éléments ayant exactement \(j\) chiffres égaux à \(1\) (dénombrement : on choisit les positions des \(1\)). Donc \(|A(n, k-1)| = 1 + \sum_{j=1}^{k-1}\binom nj = \sum_{j=0}^{k-1}\binom nj\). \(\square\)
Comme le nombre d'insertions dépasse de \(1\) celui des fusions, le nombre maximal de coups est \(2\sum_{j=0}^{k-1}\binom nj - 1\), soit \(2\sum_{j=0}^{8}\binom nj - 1\) pour \(k = 9\). \(\blacksquare\)
Remarques¶
Remarque 1 (homogénéiser). Après avoir obtenu la relation (1), il peut être commode de l'homogénéiser en posant \(h(n, k) = m(n, k) + 1\). On obtient
pour \(n \geq 1\) et \(k \geq 2\), avec les valeurs initiales \(h(0, k) = h(n, 1) = 2\) pour \(n \geq 0\) et \(k \geq 1\). Cela peut aider à deviner la réponse, et sert aussi pour l'approche suivante. Le livret écrit \(h(n-1, k) + h(n-1, k)\) ; il faut lire \(h(n-1, k) + h(n-1, k-1)\).
Remarque 2 (série génératrice). On peut trouver la réponse sans la deviner, à l'aide d'une série génératrice appliquée à (3). On pose \(h(n, 0) = 0\), de sorte que (3) est valable aussi pour \(k = 1\), et \(f(x, y) = \sum_{n, k \geq 0} h(n, k)x^ny^k\). En multipliant (3) par \(x^ny^k\) et en sommant sur \(n, k \geq 1\), puis en complétant les termes manquants, on obtient
Avec les valeurs initiales,
Le coefficient de \(x^n\) est \(2\sum_{j \geq 1} y^j(1+y)^n = 2\sum_{j \geq 1} y^j \sum_{i \geq 0}\binom ni y^i\), et celui de \(y^k\) dans cette expression donne \(h(n, k) = 2\sum_{j=0}^{k-1}\binom nj\), d'où \(m(n, k) = 2\sum_{j=0}^{k-1}\binom nj - 1\). La méthode marche aussi directement sur la relation non homogène (1), mais les calculs sont moins simples.