Shortlist 2009, C1¶
Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : New Zealand
Concepts : Jeux et stratégies gagnantes · Invariants et monovariants
Solution officielle : Shortlist officielle 2009 (avec solutions), p. 26 (page 28 du PDF)
Énoncé¶
On considère \(2009\) cartes, chacune ayant une face dorée et une face noire, posées côte à côte sur une longue table. Au départ, toutes les cartes montrent leur face dorée. Deux joueurs, placés du même côté de la table, jouent à tour de rôle. Un coup consiste à choisir un bloc de \(50\) cartes consécutives dont la plus à gauche montre sa face dorée, et à toutes les retourner : celles qui montraient leur face dorée montrent alors leur face noire, et réciproquement. Le dernier joueur qui peut jouer un coup autorisé gagne.
(a) La partie se termine-t-elle forcément ?
(b) Le premier joueur a-t-il une stratégie gagnante ?
Énoncé original (anglais)
Consider \(2009\) cards, each having one gold side and one black side, lying in parallel on a long table. Initially all cards show their gold sides. Two players, standing by the same long side of the table, play a game with alternating moves. Each move consists of choosing a block of \(50\) consecutive cards, the leftmost of which is showing gold, and turning them all over, so those which showed gold now show black and vice versa. The last player who can make a legal move wins.
(a) Does the game necessarily end?
(b) Does there exist a winning strategy for the starting player?
Indices : les idées clés
- Monovariant : en lisant les cartes comme les chiffres binaires d'un entier (or \(= 1\), noir \(= 0\)), chaque coup fait diminuer cet entier.
- Cartes témoins : les cartes d'étiquettes \(50i\) (\(i = 1, \ldots, 40\), numérotées de droite à gauche) ; chaque coup en retourne exactement une.
- Parité : le nombre de témoins dorés part de \(40\) et change de \(1\) à chaque coup, donc après un nombre impair de coups il est impair, et le second joueur peut toujours jouer.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2009 (une solution).
Réponse : (a) oui, le jeu se termine forcément ; (b) non, le premier joueur n'a pas de stratégie gagnante.
Solution¶
(a) Interprétons une carte noire comme le chiffre \(0\) et une carte dorée comme le chiffre \(1\). Chaque position des \(2009\) cartes, lue de gauche à droite, correspond alors bijectivement à un entier positif ou nul écrit en binaire avec \(2009\) chiffres (les zéros en tête étant autorisés). Chaque coup fait diminuer cet entier (le chiffre le plus à gauche du bloc passe de \(1\) à \(0\)), donc le jeu doit se terminer.
(b) Montrons que le premier joueur n'a pas de stratégie gagnante. Numérotons les cartes de droite à gauche par \(1, \ldots, 2009\) et considérons l'ensemble \(S\) des cartes d'étiquettes \(50i\), \(i = 1, 2, \ldots, 40\). Soit \(g_n\) le nombre de cartes de \(S\) montrant leur côté doré après \(n\) coups. Évidemment \(g_0 = 40\). De plus, \(\lvert g_n - g_{n+1} \rvert = 1\) tant que la partie continue (un bloc de \(50\) cartes consécutives contient exactement une carte de \(S\)). Ainsi, après un nombre impair de coups, \(g_n\) est impair, donc non nul : le second joueur trouve une carte de \(S\) montrant son côté doré et peut donc jouer (en retournant le bloc dont cette carte est la plus à gauche). Par conséquent, ce joueur gagne toujours. \(\blacksquare\)
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2023 C5 ★★★☆☆ : Elisa ajoute des gemmes, une fée verrouille des coffres : Elisa garde les coffres équilibrés à une constante près.
- 2017 C5 ★★★☆☆ · OIM P3 : Un chasseur suit un lapin invisible avec un pisteur imprécis : peut-il rester à moins de \(100\) après \(10^9\) tours ?
- 2012 C4 ★★★☆☆ : \(B\) déplace une pièce de chaque boîte, \(A\) corrige : combien de pièces faut-il à \(A\) pour ne jamais laisser de boîte vide ?
- 2009 C5 ★★★☆☆ : La belle-mère verse un litre par tour dans cinq seaux en pentagone, Cendrillon vide deux seaux voisins : un seau peut-il déborder ?