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é

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\)