Shortlist 2014, C8

Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : Russia

Concepts : Jeux et stratégies gagnantes · Bijections et dénombrement · Invariants et monovariants

Solution officielle : Shortlist officielle 2014 (avec solutions), p. 42 (page 43 du PDF)

Énoncé

A card deck consists of \(1024\) cards. On each card, a set of distinct decimal digits is written in such a way that no two of these sets coincide (thus, one of the cards is empty). Two players alternately take cards from the deck, one card per turn. After the deck is empty, each player checks if he can throw out one of his cards so that each of the ten digits occurs on an even number of his remaining cards. If one player can do this but the other one cannot, the one who can is the winner; otherwise a draw is declared.

Determine all possible first moves of the first player after which he has a winning strategy.

Indices : les idées clés

• Différence symétrique : on « additionne » les cartes avec \(\triangle\) ; la somme de toutes les cartes est \(\varnothing\), donc les deux joueurs finissent avec la même somme \(C\), et celui qui possède la carte \(C\) gagne : il n'y a jamais de match nul.
• Appariement : pour \(B \neq \varnothing\), les cartes se groupent en \(512\) paires \((X, X \triangle B)\), et une carte choisie dans chaque paire donne toujours une somme égale à \(\varnothing\) ou à \(B\).
• Stratégie miroir : en répondant à chaque carte par sa partenaire, le joueur qui possède à la fois \(A\) et \(A \triangle B\) est sûr d'avoir la carte gagnante.

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2014 (une solution et trois remarques).

Réponse : tous les premiers coups sauf prendre la carte vide.

Solution

Identifions chaque carte à l'ensemble des chiffres qui y sont écrits. Pour des cartes \(C_1, C_2, \ldots, C_k\), on appelle leur somme l'ensemble \(C_1 \triangle C_2 \triangle \cdots \triangle C_k\) formé des éléments qui appartiennent à un nombre impair de \(C_i\). Notons \(F\) le premier joueur et \(S\) le second.

Chaque chiffre est écrit sur exactement \(512\) cartes, donc la somme de toutes les cartes est \(\varnothing\). Ainsi, à la fin de la partie, la somme des cartes de \(F\) est égale à celle des cartes de \(S\) ; notons-la \(C\). Le joueur qui a pris la carte \(C\) peut la jeter et obtenir la situation voulue, tandis que l'autre ne le peut pas. Donc le joueur qui possède la carte \(C\) gagne, et le match nul est impossible.

Étant donnée une carte non vide \(B\), on voit facilement que toutes les cartes se répartissent en \(512\) paires de la forme \((X, X \triangle B)\), car \((X \triangle B) \triangle B = X\). Le lemme suivant donne une propriété importante de cette partition.

Lemme. Soit \(B \neq \varnothing\) une carte. Choisissons \(512\) cartes, exactement une dans chaque paire \((X, X \triangle B)\). Alors la somme des cartes choisies est \(\varnothing\) ou \(B\).

Preuve. Soit \(b\) un élément de \(B\). Numérotons les paires ; soit \(X_i\) la carte de la \(i\)-ème paire qui ne contient pas \(b\), et \(Y_i\) l'autre. Les \(X_i\) sont exactement tous les ensembles qui ne contiennent pas \(b\) ; chaque chiffre \(a \neq b\) est donc écrit sur exactement \(256\) d'entre eux, et \(X_1 \triangle X_2 \triangle \cdots \triangle X_{512} = \varnothing\). Si l'on remplace certains termes de cette somme par l'autre élément de leur paire, on ajoute simplement \(B\) plusieurs fois à la somme ; celle-ci reste donc inchangée ou change de \(B\), comme annoncé. \(\square\)

On distingue maintenant deux cas.

Cas 1 : \(F\) prend la carte \(\varnothing\) au premier coup. On donne une stratégie gagnante pour \(S\).

\(S\) prend une carte quelconque \(A\). Supposons qu'ensuite \(F\) prenne la carte \(B\) ; alors \(S\) prend \(A \triangle B\). Répartissons les \(1024\) cartes en \(512\) paires de la forme \((X, X \triangle B)\) ; on dit que les deux cartes d'une paire sont partenaires. Les quatre cartes prises jusqu'ici forment deux paires, \((\varnothing, B)\) appartenant à \(F\) et \((A, A \triangle B)\) appartenant à \(S\). À chacun des coups suivants, quand \(F\) prend une carte, \(S\) répond en prenant sa partenaire.

Considérons la situation à la fin de la partie. Remplaçons un instant la carte \(A\) de \(S\) par \(\varnothing\) : \(S\) aurait alors une carte de chaque paire, et par le lemme, la somme de ses cartes serait \(\varnothing\) ou \(B\). En remettant \(A\) à la place de \(\varnothing\), on voit que la somme réelle des cartes de \(S\) est \(A\) ou \(A \triangle B\), et il possède ces deux cartes. Donc \(S\) gagne.

Cas 2 : \(F\) prend au premier coup une carte \(A \neq \varnothing\). On donne une stratégie gagnante pour \(F\).

Supposons que \(S\) prenne au premier coup une carte \(B \neq \varnothing\) ; alors \(F\) prend \(A \triangle B\). Répartissons à nouveau les cartes en paires de la forme \((X, X \triangle B)\) ; les cartes qui n'ont pas encore été prises forment alors plusieurs paires complètes et un élément isolé (la carte \(\varnothing\) n'a pas été prise, alors que sa partenaire \(B\) l'a été). Ensuite, à chaque coup, si \(S\) prend une carte d'une paire complète, \(F\) prend sa partenaire. Si \(S\) prend l'élément isolé, \(F\) prend une carte quelconque \(Y\), et la partenaire de \(Y\) devient le nouvel élément isolé.

Ainsi, à son dernier coup, \(S\) est forcé de prendre l'élément isolé. Après cela, \(F\) possède les cartes \(A\) et \(A \triangle B\), \(S\) possède les cartes \(B\) et \(\varnothing\), et \(F\) a exactement une carte de chacune des autres paires. La situation est la même que dans le cas précédent, les rôles étant échangés, et \(F\) gagne.

Enfin, si \(S\) prend \(\varnothing\) à son premier coup, \(F\) appelle \(B\) une carte quelconque non encore prise et prend \(A \triangle B\). La même stratégie que ci-dessus s'applique alors. \(\blacksquare\)

Remarques

Remarque 1. Pour éviter la question inhabituelle sur le premier coup, on peut changer l'énoncé ainsi (le problème devient un peu plus facile) :

Un jeu de cartes comprend \(1023\) cartes ; sur chacune est écrit un ensemble non vide de chiffres distincts, deux cartes ne portant jamais le même ensemble. Deux joueurs prennent tour à tour une carte du paquet. Quand le paquet est vide, chaque joueur regarde s'il peut jeter une de ses cartes de sorte que, pour chacun des dix chiffres, il lui reste un nombre pair de cartes portant ce chiffre. Si un joueur le peut et pas l'autre, celui qui le peut gagne ; sinon, la partie est nulle. Déterminer quel joueur (s'il y en a un) a une stratégie gagnante.

Dans cette version, c'est le premier joueur qui gagne. L'analyse des deux premiers paragraphes de la solution s'applique encore, sauf dans le cas \(C = \varnothing\), où la partie est nulle. La stratégie de \(S\) dans le cas 1 fonctionne alors pour \(F\) : la somme de toutes ses cartes à la fin est \(A\) ou \(A \triangle B\), donc non vide dans les deux cas.

Remarque 2. Les cartes forment un espace vectoriel sur \(\mathbb{F}_2\), l'addition étant \(\triangle\). Grâce aux automorphismes de cet espace, tous les premiers coups de \(F\) autres que \(\varnothing\) sont équivalents. Il en est de même de la réponse de \(S\) quand \(F\) prend la carte \(\varnothing\) au premier coup.

Remarque 3. Il n'est pas très difficile de montrer que, dans le jeu initial, \(F\) a un coup gagnant, par l'idée du vol de stratégie.

Supposons que \(S\) ait une stratégie gagnante. Prenons deux paquets de cartes et commençons deux parties, dans lesquelles \(S\) joue selon sa stratégie. Dans la première partie, \(F\) prend une carte quelconque \(A_1\) ; supposons que \(S\) réponde par \(B_1\). Alors \(F\) prend la carte \(B_1\) dans la seconde partie ; soit \(A_2\) la réponse de \(S\). Puis \(F\) prend \(A_2\) dans la première partie et reçoit la réponse \(B_2\), et ainsi de suite.

Ce processus s'arrête au moment où, dans la seconde partie, \(S\) prend \(A_i = A_1\). À ce moment, les joueurs ont les mêmes ensembles de cartes dans les deux parties, mais avec les rôles échangés. S'il reste des cartes dans les paquets, \(F\) prend une carte quelconque du premier paquet et commence un nouveau cycle du même type.

À la fin, les cartes de \(F\) dans la première partie sont exactement celles de \(S\) dans la seconde, et inversement. Donc \(F\) gagne l'une des deux parties, ce qui contredit l'hypothèse.

On peut remarquer que la stratégie du cas 2 est construite exactement de cette façon à partir de celle du cas 1. C'est possible parce que toute réponse de \(S\) est gagnante si \(F\) prend la carte \(\varnothing\) au premier coup.