Shortlist 2013, C8¶
Domaine : Combinatoire · Difficulté : ★★★★★ · Proposé par : Austria
Concepts : Jeux et stratégies gagnantes · Invariants et monovariants · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2013 (avec solutions), p. 37 (page 37 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 paintful game on the real line. Player \(A\) has a pot of paint with four units of black ink. A quantity \(p\) of this ink suffices to blacken a (closed) real interval of length \(p\). In every round, player \(A\) picks some positive integer \(m\) and provides \(1/2^m\) units of ink from the pot. Player \(B\) then picks an integer \(k\) and blackens the interval from \(k/2^m\) to \((k+1)/2^m\) (some parts of this interval may have been blackened before). The goal of player \(A\) is to reach a situation where the pot is empty and the interval \([0, 1]\) is not completely blackened.
Decide whether there exists a strategy for player \(A\) to win in a finite number of moves.
Indices : les idées clés
- Stratégie pour \(B\) : avec \(x_r\) l'extrémité droite de la partie noircie \([0, x_r]\), \(B\) noircit l'intervalle dyadique qui suit celui contenant \(x_r\) s'il n'est pas déjà noir, et sinon celui qui contient \(x_r\).
- Invariants : (i) l'encre utilisée sur \([0, x_r]\) est au plus \(3x_r\) ; (ii) à droite de \(x_r\), \(B\) a noirci au plus un intervalle de chaque longueur \(\frac{1}{2^m}\).
- Bilan : à droite de \(x_r\), les longueurs sont des puissances de \(2\) distinctes, de total au plus \(2(1 - x_r)\) ; l'encre utilisée est au plus \(3x_r + 2(1 - x_r) < 3 < 4\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2013 (une solution et trois remarques).
Réponse : non, une telle stratégie pour \(A\) n'existe pas.
Solution¶
On présente une stratégie pour le joueur \(B\) qui garantit que l'intervalle \([0, 1]\) est entièrement noirci quand le pot est vide.
Au début du tour \(r\), notons \(x_r\) le plus grand réel tel que l'intervalle entre \(0\) et \(x_r\) soit déjà noirci ; on pose \(x_1 = 0\). Soit \(m\) l'entier choisi par \(A\) à ce tour ; on définit l'entier \(y_r\) par
L'intervalle \(I_0^r = [y_r/2^m, (y_r + 1)/2^m]\) est le plus à gauche des intervalles qu'on peut noircir à ce tour et qui contient encore un point non colorié.
Le joueur \(B\) regarde alors l'intervalle suivant \(I_1^r = [(y_r + 1)/2^m, (y_r + 2)/2^m]\). Si \(I_1^r\) contient encore un point non colorié, \(B\) noircit \(I_1^r\) ; sinon, il noircit \(I_0^r\). On convient qu'au début du jeu, l'intervalle \([1, 2]\) est déjà noirci ; ainsi, si \(y_r + 1 = 2^m\), \(B\) noircit \(I_0^r\).
On veut estimer la quantité d'encre utilisée après chaque tour. Montrons d'abord par récurrence que si, avant le \(r\)-ème tour, le segment \([0, 1]\) n'est pas entièrement colorié, alors, avant ce tour :
- (i) la quantité d'encre utilisée pour le segment \([0, x_r]\) est au plus \(3x_r\) ;
- (ii) pour tout \(m\), \(B\) a noirci au plus un intervalle de longueur \(\frac{1}{2^m}\) à droite de \(x_r\).
Ces conditions sont évidemment vérifiées au départ. Supposons-les vraies avant le \(r\)-ème tour, et considérons la situation après ce tour ; soit \(m\) le nombre choisi par \(A\) à ce tour.
Si \(B\) a noirci l'intervalle \(I_1^r\) à ce tour, alors \(x_{r+1} = x_r\), et (i) est vraie par hypothèse de récurrence. Ensuite, si \(B\) avait noirci avant le \(r\)-ème tour un intervalle de longueur \(\frac{1}{2^m}\) à droite de \(x_r\), cet intervalle coïnciderait nécessairement avec \(I_1^r\), ce qui est impossible d'après la stratégie. La condition (ii) reste donc vraie.
Supposons maintenant que \(B\) ait noirci l'intervalle \(I_0^r\) à ce tour, mais que l'intervalle \([0, 1]\) contienne encore des parties non coloriées (ce qui signifie que \(I_1^r\) est contenu dans \([0, 1]\)). La condition (ii) reste clairement vraie, et il suffit de vérifier (i). Dans ce cas, les intervalles \(I_0^r\) et \(I_1^r\) sont entièrement coloriés après le \(r\)-ème tour, donc \(x_{r+1}\) atteint l'extrémité droite de \(I_1^r\), ou va même plus loin. Ainsi \(x_{r+1} = x_r + \alpha\) avec \(\alpha > \frac{1}{2^m}\).
Ensuite, tout intervalle noirci par \(B\) avant le \(r\)-ème tour qui rencontre \((x_r, x_{r+1})\) est contenu dans \([x_r, x_{r+1}]\) ; par (ii), ces intervalles ont tous des longueurs différentes, au plus égales à \(\frac{1}{2^m}\), donc la quantité d'encre utilisée pour eux est inférieure à \(\frac{2}{2^m}\). La quantité d'encre utilisée pour le segment \([0, x_{r+1}]\) ne dépasse donc pas la somme de \(\frac{2}{2^m}\), de \(3x_r\) (pour \([0, x_r]\)) et de \(\frac{1}{2^m}\) (pour le segment \(I_0^r\)). Au total, cela fait au plus \(3\left(x_r + \frac{1}{2^m}\right) < 3(x_r + \alpha) = 3x_{r+1}\). La condition (i) est donc aussi vérifiée dans ce cas, ce qui prouve l'affirmation.
On peut maintenant faire l'estimation voulue. Considérons une situation quelconque du jeu, disons après le \((r - 1)\)-ème tour, et supposons que le segment \([0, 1]\) ne soit pas entièrement noir. Par (ii), dans le segment \([x_r, 1]\), le joueur \(B\) a colorié plusieurs segments de longueurs différentes ; toutes ces longueurs sont des puissances négatives de \(2\) au plus égales à \(1 - x_r\), donc la quantité totale d'encre utilisée pour cet intervalle est au plus \(2(1 - x_r)\). Avec (i), la quantité totale d'encre utilisée est au plus \(3x_r + 2(1 - x_r) < 3\). Le pot n'est donc pas vide, et \(A\) ne gagne jamais. \(\blacksquare\)
Remarques¶
Remarque 1. Cette stratégie fonctionne même si le pot ne contient initialement que \(3\) unités d'encre.
Remarque 2. Il existe d'autres stratégies permettant à \(B\) d'éviter que le pot se vide avant que tout l'intervalle soit colorié. Signalons en revanche une idée qui ne fonctionne pas. Le joueur \(B\) pourrait essayer une stratégie dans laquelle l'ensemble des points noircis à chaque tour est un intervalle de la forme \([0, x]\). Une telle stratégie ne peut pas marcher (même avec plus d'encre). En effet, en supposant que \(B\) utilise une telle stratégie, montrons par récurrence sur \(s\) l'énoncé suivant :
Pour tout entier \(s \geq 1\), le joueur \(A\) a une stratégie ne choisissant que des entiers \(m \leq s\) dans laquelle, si le joueur \(B\) peint un jour un point \(x \geq 1 - 1/2^s\), alors, après un certain coup, c'est exactement l'intervalle \([0, 1 - 1/2^s]\) qui est noirci, et la quantité d'encre utilisée jusque-là est au moins \(s/2\).
Pour \(s = 1\), le joueur \(A\) choisit simplement \(m = 1\) au premier tour. Si \(A\) a une telle stratégie pour un entier \(s\), alors pour \(s + 1\) il peut d'abord ramener sa stratégie à l'intervalle \([0, 1/2]\) (en donnant à chaque tour la moitié de l'encre que donnerait la stratégie d'origine). Après un certain tour, l'intervalle \([0, 1/2 - 1/2^{s+1}]\) est noirci, et la quantité d'encre utilisée est au moins \(s/4\). Le joueur \(A\) choisit alors \(m = 1\) (le livret écrit \(m = 1/2\) ; il faut lire \(m = 1\), ce qui donne \(\frac{1}{2}\) unité d'encre), et le joueur \(B\) dépense \(1/2\) unité d'encre pour noircir l'intervalle \([0, 1/2]\). Ensuite, \(A\) ramène à nouveau sa stratégie à l'intervalle \([1/2, 1]\), et le joueur \(B\) dépense au moins \(s/4\) unités d'encre pour noircir l'intervalle \([1/2, 1 - 1/2^{s+1}]\) ; il dépense donc au total au moins \(s/4 + 1/2 + s/4 = (s + 1)/2\) unités d'encre.
Remarque 3. Pour éviter les questions de finitude, on pourrait remplacer l'énoncé par le suivant :
Les joueurs \(A\) et \(B\) jouent sur la droite réelle. Le joueur \(A\) a un pot contenant quatre unités d'encre noire, une quantité \(p\) d'encre suffisant à noircir un intervalle fermé de longueur \(p\). Au début du jeu, le joueur \(A\) choisit (et annonce) un entier \(N \geq 1\). À chaque tour, \(A\) choisit un entier \(m\) avec \(1 \leq m \leq N\) et fournit \(1/2^m\) unité d'encre du pot. Le joueur \(B\) choisit un entier \(k\) et noircit l'intervalle de \(k/2^m\) à \((k + 1)/2^m\). Le but de \(A\) est d'atteindre une situation où le pot est vide et l'intervalle \([0, 1]\) n'est pas entièrement noirci. Existe-t-il une stratégie gagnante pour \(A\) ?
Le comité pense toutefois que cette version pourrait être plus difficile que l'originale.