C8. 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.
Answer. All the moves except for taking the empty card.
Solution. Let us identify each card with the set of digits written on it. For any collection of cards $C_{1}, C_{2}, \ldots, C_{k}$ denote by their sum the set $C_{1} \triangle C_{2} \triangle \cdots \Delta C_{k}$ consisting of all elements belonging to an odd number of the $C_{i}$ 's. Denote the first and the second player by $\mathcal{F}$ and $\mathcal{S}$, respectively.

Since each digit is written on exactly 512 cards, the sum of all the cards is $\varnothing$. Therefore, at the end of the game the sum of all the cards of $\mathcal{F}$ will be the same as that of $\mathcal{S}$; denote this sum by $C$. Then the player who took $C$ can throw it out and get the desired situation, while the other one cannot. Thus, the player getting card $C$ wins, and no draw is possible.

Now, given a nonempty card $B$, one can easily see that all the cards can be split into 512 pairs of the form $(X, X \triangle B)$ because $(X \triangle B) \triangle B-X$. The following lemma shows a property of such a partition that is important for the solution.
Lemma. Let $B \neq \varnothing$ be some card. Let us choose 512 cards so that exactly one card is chosen from every pair $(X, X \triangle B$ ). Then the sum of all chosen cards is either $\varnothing$ or $B$.
Proof. Let $b$ be some element of $B$. Enumerate the pairs; let $X_{i}$ be the card not containing $b$ in the $i^{\text {th }}$ pair, and let $Y_{i}$ be the other card in this pair. Then the sets $X_{i}$ are exactly all the sets not containing $b$, therefore each digit $a \neq b$ is written on exactly 256 of these cards, so $X_{1} \triangle X_{2} \triangle \cdots \triangle X_{512}-\varnothing$. Now, if we replace some summands in this sum by the other elements from their pairs, we will simply add $B$ several times to this sum, thus the sum will either remain unchanged or change by $B$, as required.
Now we consider two cases.
Case 1. Assume that $\mathcal{F}$ takes the card $\varnothing$ on his first move. In this case, we present a winning strategy for $\mathcal{S}$.

Let $\mathcal{S}$ take an arbitrary card $A$. Assume that $\mathcal{F}$ takes card $B$ after that; then $\mathcal{S}$ takes $A \triangle B$. Split all 1024 cards into 512 pairs of the form $(X, X \triangle B)$; we call two cards in one pair partners. Then the four cards taken so far form two pairs $(\varnothing, B)$ and $(A, A \triangle B)$ belonging to $\mathcal{F}$ and $\mathcal{S}$, respectively. On each of the subsequent moves, when $\mathcal{F}$ takes some card, $\mathcal{S}$ should take the partner of this card in response.

Consider the situation at the end of the game. Let us for a moment replace card $A$ belonging to $\mathcal{S}$ by $\varnothing$. Then he would have one card from each pair; by our lemma, the sum of all these cards would be either $\varnothing$ or $B$. Now, replacing $\varnothing$ back by $A$ we get that the actual sum of the cards of $\mathcal{S}$ is either $A$ or $A \triangle B$, and he has both these cards. Thus $\mathcal{S}$ wins.

Case 2. Now assume that $\mathcal{F}$ takes some card $A \neq \varnothing$ on his first move. Let us present a winning strategy for $\mathcal{F}$ in this case.

Assume that $\mathcal{S}$ takes some card $B \neq \varnothing$ on his first move; then $\mathcal{F}$ takes $A \triangle B$. Again, let us split all the cards into pairs of the form $(X, X \triangle B)$; then the cards which have not been taken yet form several complete pairs and one extra element (card $\varnothing$ has not been taken while its partner $B$ has). Now, on each of the subsequent moves, if $\mathcal{S}$ takes some element from a complete pair, then $\mathcal{F}$ takes its partner. If $\mathcal{S}$ takes the extra element, then $\mathcal{F}$ takes an arbitrary card $Y$, and the partner of $Y$ becomes the new extra element.

Thus, on his last move $\mathcal{S}$ is forced to take the extra element. After that player $\mathcal{F}$ has cards $A$ and $A \triangle B$, player $\mathcal{S}$ has cards $B$ and $\varnothing$, and $\mathcal{F}$ has exactly one element from every other pair. Thus the situation is the same as in the previous case with roles reversed, and $\mathcal{F}$ wins.

Finally, if $\mathcal{S}$ takes $\varnothing$ on his first move then $\mathcal{F}$ denotes any card which has not been taken yet by $B$ and takes $A \triangle B$. After that, the same strategy as above is applicable.

Comment 1. If one wants to avoid the unusual question about the first move, one may change the formulation as follows. (The difficulty of the problem would decrease somewhat.)

A card deck consists of 1023 cards; on each card, a nonempty set of distinct decimal digits is written in such a way that no two of these sets coincide. Two players alternately take cards from the deck, one card per turn. When the deck is empty, each player checks if he can throw out one of his cards so that for each of the ten digits, he still holds an even number of cands with this digit. If one player can do this but the other one cannot, the one who can is the winner; otherwise a draw is declared.
Determine which of the players (if any) has a winning strateqy.
The winner in this version is the first player. The analysis of the game from the first two paragraphs of the previous solution applies to this version as well, except for the case $C=\varnothing$ in which the result is a draw. Then the strategy for $\mathcal{S}$ in Case 1 works for $\mathcal{F}$ in this version: the sum of all his cards at the end is either $A$ or $A \triangle B$, thus nonempty in both cases.

Comment 2. Notice that all the cards form a vector space over $F_{2}$, with $\triangle$ the operation of addition. Due to the automorphisms of this space, all possibilities for $\mathcal{F}$ 's first move except $\varnothing$ are equivalent. The same holds for the response by $\mathcal{S}$ if $\mathcal{F}$ takes the card $\varnothing$ on his first move.

Comment 3. It is not that hard to show that in the initial game, $\mathcal{F}$ has a winning move, by the idea of "strategy stealing".

Namely, assume that $\mathcal{S}$ has a winning strategy. Let us take two card decks and start two games, in which $\mathcal{S}$ will act by his strategy. In the first game, $\mathcal{F}$ takes an arbitrary card $A_{1}$; assume that $\mathcal{S}$ takes some $B_{1}$ in response. Then $\mathcal{F}$ takes the card $B_{1}$ at the second game; let the response by $\mathcal{S}$ be $A_{2}$. Then $\mathcal{F}$ takes $A_{2}$ in the first game and gets a response $B_{2}$, and so on.

This process stops at some moment when in the second game $S$ takes $A_{i}=A_{1}$. At this moment the players hold the same sets of cards in both games, but with roles reversed. Now, if some cards remain in the decks, $\mathcal{F}$ takes an arbitrary card from the first deck starting a similar cycle.

At the end of the game, player $\mathcal{F}$ 's cards in the first game are exactly player $\mathcal{S}$ 's cards in the second game, and vice versa. Thus in one of the games $\mathcal{F}$ will win, which is impossible by our assumption.
One may notice that the strategy in Case 2 is constructed exactly in this way from the strategy
in Case 1. This is possible since every response by $\mathcal{S}$ wins if $\mathcal{F}$ takes the card $\varnothing$ on his first move.