Shortlist 2020, C8¶
Domaine : Combinatoire · Difficulté : ★★★★★ · Proposé par : Austria
Concepts : Jeux et stratégies gagnantes · Invariants et monovariants · Valuations p-adiques et lemme LTE
Solution officielle : Shortlist officielle 2020 (avec solutions), p. 44 (page 46 du PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Players \(A\) and \(B\) play a game on a blackboard that initially contains \(2020\) copies of the number \(1\). In every round, player \(A\) erases two numbers \(x\) and \(y\) from the blackboard, and then player \(B\) writes one of the numbers \(x + y\) and \(|x - y|\) on the blackboard. The game terminates as soon as, at the end of some round, one of the following holds:
(1) one of the numbers on the blackboard is larger than the sum of all other numbers;
(2) there are only zeros on the blackboard.
Player \(B\) must then give as many cookies to player \(A\) as there are numbers on the blackboard. Player \(A\) wants to get as many cookies as possible, whereas player \(B\) wants to give as few as possible. Determine the number of cookies that \(A\) receives if both players play optimally.
Indices : les idées clés
- Jeux et stratégies gagnantes : exhiber une stratégie pour \(A\) garantissant \(S_2(n)\) biscuits et une stratégie pour \(B\) n'en cédant jamais plus.
- Invariants et monovariants : pour \(A\), les « portées » restent des puissances de \(2\) de somme \(n\) ; pour \(B\), il maintient la propriété « \(2^{s+1}\) ne divise pas le nombre de combinaisons de signes équilibrées ».
- Valuations p-adiques et lemme LTE : la formule de Legendre \(\nu_2(n!) = n - S_2(n)\) donne \(\nu_2\binom{n}{n/2} = S_2(n)\).
- Somme des chiffres binaires : \(S_2(a+b) \leq S_2(a) + S_2(b)\), donc \(n\) n'est pas somme de moins de \(S_2(n)\) puissances de \(2\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2020 (une solution et trois remarques).
Réponse : \(7\).
Solution¶
Pour un entier \(n \geq 1\), notons \(S_2(n)\) la somme des chiffres de son écriture en base \(2\). Nous montrons plus généralement que si le tableau contient initialement un nombre pair \(n > 1\) de \(1\), alors \(A\) peut s'assurer \(S_2(n)\) biscuits, mais pas davantage. Comme \(2020 = 11111100100_2\), on a \(S_2(2020) = 7\), d'où la réponse.
Une stratégie pour \(A\). À chaque tour, tant que c'est possible, \(A\) choisit deux nombres non nuls égaux. \(A\) peut suivre cette stratégie tant que le jeu n'est pas terminé. (Le livret affirme aussi que le jeu ne s'arrête pas tant que \(A\) peut choisir deux nombres égaux ; ce n'est pas toujours vrai, par exemple pour \(n = 6\) la position \(4, 1, 1\) est terminale, mais seul compte le fait que \(A\) peut toujours jouer ainsi.) En effet, si \(A\) choisit toujours deux nombres égaux, chaque nombre écrit au tableau est \(0\) ou une puissance de \(2\) d'exposant entier positif ou nul (récurrence immédiate sur le nombre de tours : \(2^j + 2^j = 2^{j+1}\), \(2^j - 2^j = 0\)). Au moment où \(A\) ne peut plus suivre la stratégie, les nombres non nuls du tableau sont des puissances de \(2\) distinctes. S'il y en a au moins une, la plus grande est strictement supérieure à la somme des autres ; sinon il n'y a que des zéros. Dans les deux cas, le jeu est terminé.
Pour chaque nombre du tableau, définissons sa portée comme le nombre de \(1\) initiaux à partir desquels il a été obtenu. Par récurrence sur le nombre de tours, tout nombre non nul \(k\) écrit par \(B\) a pour portée \(k\), et tout zéro écrit par \(B\) a pour portée une puissance de \(2\). Ainsi, à la fin de chaque tour, toutes les portées sont des puissances de \(2\), de somme \(n\). Comme \(S_2(a + b) \leq S_2(a) + S_2(b)\) pour tous entiers positifs \(a, b\), l'entier \(n\) ne peut pas s'écrire comme somme de moins de \(S_2(n)\) puissances de \(2\). Donc, tant que \(A\) suit cette stratégie, le tableau contient à la fin de chaque tour au moins \(S_2(n)\) nombres : \(A\) est assuré d'obtenir au moins \(S_2(n)\) biscuits.
Une stratégie pour \(B\). Notons \(s = S_2(n)\).
Soient \(x_1, \ldots, x_k\) les nombres du tableau à un moment du jeu (après un coup de \(B\), ou au début). Une famille de \(k\) signes \(\varepsilon_1, \ldots, \varepsilon_k \in \{+1, -1\}\) est dite équilibrée si
La situation est dite bonne si \(2^{s+1}\) ne divise pas le nombre de familles équilibrées. La stratégie de \(B\) : jouer de façon que la situation reste bonne, tant que c'est possible. Montrons qu'alors \(B\) ne cède pas plus de \(s\) biscuits.
Pour un entier \(k \geq 1\), notons \(\nu_2(k)\) l'exposant de la plus grande puissance de \(2\) divisant \(k\). Rappelons la formule de Legendre : \(\nu_2(n!) = n - S_2(n)\) pour tout entier \(n \geq 1\).
Lemme 1. La situation initiale est bonne.
Preuve. Au départ, une famille est équilibrée si et seulement si elle contient exactement \(n/2\) signes \(+\) ; il y en a \(\binom{n}{n/2}\). Or, comme \(S_2(n/2) = S_2(n)\),
Donc \(2^{s+1}\) ne divise pas le nombre de familles équilibrées. \(\square\)
Lemme 2. \(B\) peut jouer de sorte qu'après chaque tour, la situation reste bonne.
Preuve. Supposons la situation \((x_1, \ldots, x_k)\) bonne avant un tour, et que \(A\) efface \(x_p\) et \(x_q\). Soient \(N\) le nombre de familles équilibrées, \(N_+\) le nombre de celles qui vérifient \(\varepsilon_p = \varepsilon_q\), et \(N_-\) le nombre des autres ; \(N = N_+ + N_-\). Si \(B\) remplace \(x_p, x_q\) par \(x_p + x_q\), le nombre de familles équilibrées devient \(N_+\) ; s'il les remplace par \(|x_p - x_q|\), il devient \(N_-\). Comme \(2^{s+1}\) ne divise pas \(N\), il ne divise pas l'un des deux termes \(N_+\), \(N_-\) : \(B\) peut donc obtenir une bonne situation à l'issue du tour. \(\square\)
Lemme 3. Si le jeu se termine sur une bonne situation, le tableau contient au plus \(s\) nombres.
Preuve. Si l'un des nombres est strictement supérieur à la somme des autres, il n'y a aucune famille équilibrée ; or \(0\) est divisible par \(2^{s+1}\), donc la situation n'est pas bonne. Le jeu s'est donc terminé avec uniquement des zéros. S'il y en a \(k\), le nombre de familles équilibrées est \(2^k\) ; la situation étant bonne, \(k \leq s\). \(\square\)
D'après les lemmes 1 et 2, \(B\) peut maintenir la situation bonne ; d'après le lemme 3, à la fin du jeu le tableau contient au plus \(s\) nombres. Avec la stratégie de \(A\), on conclut que \(A\) reçoit exactement \(S_2(2020) = 7\) biscuits. \(\blacksquare\)
Remarques¶
Remarque 1 (autre preuve pour la stratégie de \(A\)). On peut aussi noter \(\Sigma\) la somme des nombres du tableau et \(z\) le nombre de zéros. Le tableau contient au moins \(S_2(\Sigma) + z\) nombres ; or, au cours du jeu (avec la stratégie de \(A\)), la quantité \(S_2(\Sigma) + z\) ne diminue pas, et sa valeur initiale est \(S_2(n)\).
Remarque 2 (cas \(n\) impair). Si le tableau contenait au départ un nombre impair \(n > 1\) de \(1\), le joueur \(A\) obtiendrait encore \(S_2(n)\) biscuits en jeu optimal. La preuve est analogue, avec les modifications suivantes. Une famille de signes est dite positive si \(\sum_{i=1}^{k} \varepsilon_i x_i > 0\). Pour chaque \(i\), on note \(N_i\) le nombre de familles positives telles que \(\varepsilon_i = 1\). La situation est bonne si \(2^{s-1}\) ne divise pas au moins l'un des \(N_i\). La stratégie de \(B\) consiste encore à garder la situation bonne.
Remarque 3 (une stratégie plus simple pour \(B\), non optimale en général). Pour \(n\) pair, \(B\) peut céder au plus \(d = \lfloor \log_2(n+2) \rfloor - 1\) biscuits ; si l'écriture binaire de \(n\) contient au plus deux zéros, \(d = S_2(n)\) et cette stratégie est optimale. On peut supposer que \(A\) n'efface jamais de zéro (sinon on ignore ces zéros, ce qui ne fait qu'augmenter le gain de \(A\)). Une situation est jolie si les nombres du tableau peuvent être partagés en deux groupes de même somme ; si elle est jolie avant un tour, \(B\) peut la garder jolie. Stratégie de \(B\) : toujours jouer vers une situation jolie, et, si les deux coups y mènent, écrire la somme. Le jeu se termine alors avec uniquement des zéros.
Supposons qu'à la fin il y ait \(m \geq d + 1 = \lfloor \log_2(n+2) \rfloor\) zéros ; alors \(2^m - 1 > n/2\). Numérotons les zéros par ordre d'apparition : le \(i\)-ème est apparu en soustrayant \(n_i\) de \(n_i\). La somme des nombres ne croissant jamais, \(2n_1 + \cdots + 2n_m \leq n\), donc \(n_1 + \cdots + n_m \leq n/2 < 2^m - 1\). Les \(2^m\) sous-ensembles \(I \subseteq \{1, \ldots, m\}\) donnent des sommes \(f(I) = \sum_{i \in I} n_i\) prenant moins de \(2^m\) valeurs : il existe \(I \neq J\) avec \(f(I) = f(J)\), que l'on peut supposer disjoints (remplacer par \(I \setminus J\) et \(J \setminus I\)). Soit \(i_0\) le plus petit élément de \(I \cup J\), disons \(i_0 \in I\). Juste avant le tour où le \(i_0\)-ème zéro est apparu, on suit chaque nombre non nul du tableau jusqu'à ce qu'il entre dans l'un des \(n_i\) (\(i \geq i_0\)) ; on note \(X_i\), \(Y_i\) les nombres qui entrent dans la première et la seconde copie de \(n_i\). Ces ensembles sont disjoints, \(X_{i_0}\) et \(Y_{i_0}\) sont des singletons, et en signant convenablement les éléments de \(X_i \cup Y_i\) on obtient \(-2n_i\), \(0\) ou \(2n_i\). On choisit \(2n_i\) pour \(i \in I\), \(-2n_j\) pour \(j \in J\) et \(0\) sinon : la somme signée totale vaut \(\sum_{I} 2n_i - \sum_{J} 2n_j = 0\), et les deux nombres de \(X_{i_0}\), \(Y_{i_0}\) ont le même signe. Donc, à ce tour, \(B\) pouvait additionner les deux copies de \(n_{i_0}\) en restant dans une situation jolie ; sa stratégie lui imposait de le faire, contradiction. Donc \(m \leq d\).