Answer : All moves except for taking the empty card.

To each card $X$ assign a vector $v\in\mathbb{Z}_2^{10}$ where the $i$-th entry is $1$ if the $i$-th digit appears in $X$ and $0$ othwerwise. Let now $10=n\geq 3$, we solve the problem in the general case. Given cards $X=(x_1, \ldots, x_n)$ and $Y=(y_1, \ldots, y_n)$, we define $X\oplus Y=(x_1+y_1, \ldots, x_n+y_n)$ where sum is done modulo $2$. Note that $\mathbb{Z}_2^n$ with the operation $\oplus$ is a vector space over $\mathbb{Z}_2$; if we denote by $0$ the empty card, we have $X\oplus Y=0$ if and only if $X=Y$. Moreover, a player wins the game if and only if at the end the sum of his cards is also one of his cards. Call the first and second player $\mathcal{A}$ and $\mathcal{B}$, respectively. Claim 1: The game can't end in a draw. Proof: Let $A_1, \ldots, A_{2^{n-1}}$ and $B_1, \ldots, B_{2^{n-1}}$ be the final sets of cards of player $\mathcal{A}$ and player $\mathcal{B}$, respectively. Then $(A_1\oplus\cdots\oplus A_{2^{n-1}})\oplus(B_1\oplus\cdots\oplus B_{2^{n-1}})$ is equal to the sum of all cards, which is $0$ since each entry is $1$ in exactly $2^{n-1}$ cards and $2^{n-1}$ is even. Therefore, $A_1\oplus\cdots\oplus A_{2^{n-1}}=B_1\oplus\cdots\oplus B_{2^{n-1}}$, and one of the players has this card, winning the game. $\square$ Claim 2: Player $\mathcal{A}$ has a winning strategy (provided that he can take any card on his first move). Proof: Assume otherwise, then claim 1 implies that player $\mathcal{B}$ has a winning strategy. We will then devise a winning strategy for player $\mathcal{A}$. At first he shall "pretend" that player $\mathcal{B}$ has taken card $0$ on his first move, and then act accordiing to his winning strategy. If player $\mathcal{B}$ doesn't take the empty card until his last move, the game is obviously unchanged, therefore the winning strategy works for player $\mathcal{A}$. Otherwise, when player $\mathcal{B}$ takes card $0$, player $\mathcal{A}$ takes a random card from the deck and stores it on a separate box. Whenever he should take that card from the deck according to the winning strategy, he takes it from the box and takes another random card from the deck, which he stores on the box. This process continues until the end of the game; after player $\mathcal{B}$'s last move, player $\mathcal{A}$ takes the card that is in the box. From the point of view of player $\mathcal{A}$, cards in the box are regarded in the same way as cards still on the deck; only player $\mathcal{B}$'s possibilities are reduced. Therefore player $\mathcal{A}$ has a winning strategy. This is the desired contradiction. $\square$ Claim 3: Assume there is a card $X\neq 0$ such that player $\mathcal{A}$ has a winning strategy if he takes $X$ on his first move. Then the same holds for any other card $Y\neq 0$. Proof: Take a base of the vector space containing $X$ and a base of the vector space containing $Y$. There is an automorphism $\varphi:\mathbb{Z}_2^n\rightarrow\mathbb{Z}_2^n$ that maps the first base to the second one, and, in particular, maps $X$ to $Y$. Since $\varphi$ is an automorphism, it preserves operation $\oplus$, thus the game with arbitary card $T$ replaced by card $\varphi(T)$ is isomorphic to the original one. This implies the desired claim. $\square$ Claim 4: Assume player $\mathcal{A}$ takes card $0$ on his first move. Then player $\mathcal{B}$ has a winning strategy. Proof: We will explicitly construct such a strategy. Let player $\mathcal{B}$ take an arbitary card $S$ on his first move. Now let $T$ be the card taken by player $\mathcal{A}$ on his second move; player $\mathcal{B}$ shall now take card $S\oplus T$. Partition $\mathbb{Z}_2^n$ into pairs of the form $\{X, Y\}$ such that $X\oplus Y=T$. Note that $S$ and $S\oplus T$ form a pair, as well as $0$ and $T$. Now, whenever player $\mathcal{A}$ takes an element of such a pair, player $\mathcal{B}$ shall take the other one. Call a subset of $\mathbb{Z}_2^n$ nice if it contains one element from each of the pairs above mentioned. Assuming without loss of generality that the first entry of $T$ is $1$ (recall that $T\neq 0$), the set of the cards with first entry equal to $0$ is clearly nice. Since for each $i\geq 2$ the $i$-th entry is $1$ in exactly $2^{n-2}$ cards of this set, and $2^{n-2}$ is even, the sum of the cards in this set is $0$. Now every nice set can be obtained from this one by replacing some cards $X$ by $X\oplus T$ (note that $X\oplus (X\oplus T)=T$). Whenever we do so, we "add" a vector of the form $T\oplus\cdots\oplus T$ to the original sum; since this can only be equal to $0$ or $T$, the sum of the cards in any nice set is $0$ or $T$. At the end of the game, the set of cards held by player $\mathcal{B}$ is a nice set from which we remove $T$ and add $S$. Therefore the sum of player $\mathcal{B}$'s cards is either $S$ or $S\oplus T$. Since player $\mathcal{B}$ has both cards, he wins the game. $\square$ Now Claim 2 implies that there is a card $X$ such that when player $\mathcal{A}$ starts by taking $X$ he has a winning strategy. Claim 4 implies that $X\neq 0$; therefore Claim 3 implies that whenever player $\mathcal{A}$ starts by taking any non-zero card he has a winning strategy. Then the possibilities for the first card are precisely the non-empty ones.

Solved with Rg230403, MathPassionForever, biomathematics, Dr_Vex, DragonEye, Arwen713 We claim that A has a winning strategy iff he plays a non zero card on his first chance . Consider the cards as vectors in $\mathbb {F}_2^{10}$ . Note that A having a winning strategy is equivalent to him having the sum of all his cards . (Here addition of cards is carried out as normal vector addition in $\mathbb {F}_2$) The idea is to consider pairs of the form $(X,X+Y)$ for a suitable $Y$ and construct a winning strategy for A , by choosing a suitable $Y$. Claim : Consider $512$ cards where exactly one card from each of the pairs $(X,X+Y)$ has been chosen . We claim that the sum $\mathcal S$ of these cards is either $0$ or $Y$ . Proof : We begin with some easy observations. Note that for any $x \notin X$ , $x$ either occurs in both members of a pair of it occurs in none . Any element $y \in Y$ appears in exactly one member of each card . So every element $x \notin X$ appears exactly $256$ times in $\mathcal S$ and hence it doesnt occur in the some (we are working in $\mathbb F_2$) . Now for a fixed element $y \in Y$ , consider a element $y \neq y' \in Y $ . For each pair , let $A_i$ be the card containing $y$ and let $B_i$ be the card not containing it . Hence $\{B_i\}_{i=1}^{512}$ are exactly those $512$ cards not containing $y$.Note that $y'$ occurs in exactly $256$ of all the $B_i$'s . So $\sum_{i} B_i =0$ . Now if one of the $B_i$'s is swapped out for a $A_i$ ,then the sum increases by $Y$ as every element of $Y$ is in either $A_i$ or a $B_i$ . So the claim holds . $\blacksquare$ Now we construct a winning strategy for the first player if he picks a nine zero card on his first chance . Let the first player begin by choosing $A$ and let the second player reply with a $B$ . Assume for now $B \neq 0$ . Next the first player plays $A+B$.It is at this moment that the second player is doomed to hell . The first player now imagines pairing up the cards $\{X,X+B\}$ . Note that at any instant when the second player is about to play , there is exactly one card such that a member of its pair has been taken . If the second player chooses a card from a "complete" pair then the first player replies with the other member of that pair . If the second player chooses the "odd one out", then the first player chooses a arbitrary card $C$ , so that $C+B$ becomes the odd one out . Note that if this strategy is followed, then at the end , the sum of all cards of the first player is either $A$ or $A+B$ . But he has both, so he wins. If $B =0$ ,then the first player picks $A+C$ for a random card $C$ on his second move and continues in the same way . Next we construct a winning strategy for the second player in case the first player starts with $0$ . The first player starts with $0$ .Suppose the second player plays $B$ on his first move . Then the first player plays $A$ . Then the second player plays $A+B$ and mimics the strategy described above . Hence having exhausted all the cases , we are done . $\blacksquare$

We claim that $A$ can choose any card besides the empty set to win. For simplicity, denote cards as elements in $\mathbb{F}_2^{10}$. Note that $A$, $B$ end up with the same xor at the end, so they both need the same card to win. This card has to belong to someone, so exactly one person will win. Thus, to show $A$ loses it suffices to show $B$ wins. To show that the empty set loses, suppose $A$ chooses $\vec{0}$ first. Now, $B$ draws an arbitrary card, $b$. Let $A$'s second card be $k$. Then, $B$ will choose $b\oplus k$. For the remaining $1020$ cards, we can divide them into $510$ pairs of the form $(v,v\oplus k)$. Now, whenever $A$ chooses an element in a pair, $B$ chooses the other element. Now, we claim that, at the end, the xor of all of $A$'s cards (equivalently all of $B$'s cards) is either $b$ or $b\oplus k$. To see this, call the $512$ pairs (including the 2 pairs drawn at the start) $(v_1,v_1\oplus k), (v_2,v_2\oplus k), \ldots, (v_{512},v_{512}\oplus k)$. The final xor of $B$'s cards is $$v_1\oplus v_2\oplus v_3\oplus\ldots \oplus v_{512}\oplus b\oplus^r k$$where $k$ is xored $r$ times at the end. However, since the pairs cover the cards, we have $$(v_1\oplus\ldots\oplus v_{512})\oplus (v_1\oplus\ldots\oplus v_{512})\oplus^{512} k=(v_1\oplus\ldots \oplus v_{512})\oplus (v_1\oplus\ldots \oplus v_{512})=\vec{0}$$so $v_1\oplus\ldots\oplus v_{512}=0$, thus yielding that $B$ has xor $b\oplus^r k=b,b\oplus k$, as desired. However, $B$ has both of these cards so he wins. Now, we show that $A$ wins for any other choice of cards. In fact, he can use a very similar strategy. This time, $A$ starts with $a$, and we pair by $(v,v\oplus k)$ where $k\neq a$ is an arbitrary element of $\mathbb{F}_2^{10}$. Now, on $B$'s turn, he can either "complete" the pair with $a$ or start a new one. If he chooses the former, $A$ picks another arbitrary element not in $k$'s pair. If $B$ chooses the latter and the pair he chooses is not $(\vec{0},k)$, then $A$ will complete it. In this way, $A$ continues to put $B$ into the same situation of either completing or making a new pair, until he chooses either $\vec{0}$ or $k$. Now, once this occurs, $A$ still has an element $a'$ in an uncompleted pair. $A$ now chooses $a'\oplus k$. Then, he continues on with his strategy of forcing $B$ to complete a pair or start a new one. However, note that $B$ now also has the option to complete the pair with $k$. In fact, $A$ can force him to do this at some point since $B$'s last move is forced. So, $A$ can ensure that $B$ gets the pair $(\vec{0},k)$, he gets the pair $(a',a'\oplus k)$, and all other pairs are evenly distributed. Now, by similar logic to before, the resulting xor is either $a'$ or $a'\oplus k$, so $A$ wins.

Very nice problem, and quite approachable for a C8. I wanted to provide some motivation for how one would come up with the solutions listed above. Let's call the players Alice and Bob. There are basically two central ideas here: Key idea 1: Associate each set with a 10-dimensional 0-1 vector, whose $i$th entry is 1 iff the set contains digit $i$. This problem is really about addition of these vectors modulo 2; formally, we are working over $\mathbb{F}_{2}^{10}$. Let $S$ denote the set of these 1024 vectors. To win, Alice must ensure that the sum of her vectors is a vector that she has. Key idea 2: One of the most common ideas in symmetric games of this sort is to construct a pairing strategy. I discuss pairing strategies in depth in Chapter 5 of my book. To construct a pairing strategy for this problem, we have the following observation. Observation: For any partition of $S$ into 512 pairs, Alice can ensure that she picks exactly one vector from each pair. Now, how should we go about constructing such a partition? Well, we know the problem is about adding vectors in $\mathbb{F}_{2}^{10}$. So the simplest thing we can do is consider mappings of the form $f(x) = x + v$ for some fixed vector $v \neq 0$. Notice that this mapping is involutive, so any fixed $v$ thus gives a partition of $S$ into 512 pairs of the form $(x_{i}, x_i + v)$ for $1 \leq i \leq 512$. So suppose Alice picks $v \neq 0$ arbitrarily and executes this pairing strategy, picking exactly one of $x_i$ and $x_i + v$ for each $1 \leq i \leq 512$. At this point we ask what Alice's full sum at the end is, and are led to the lemma in the above (and official) solutions: namely, that Alice's sum is either 0 or $v$. Now we see the problem. In order to guarantee victory, we need Alice to have both 0 and $v$. But alas, Alice has exactly one of these by her pairing strategy! Is all hope lost? Fortunately, Alice has one more card up her sleeve$^\dagger$. Call the pairing strategy above the ``vanilla pairing strategy" or VPS. Notice that so far, we haven't actually exploited the fact that Alice goes first! Suppose Alice's first move is a vector $a \neq 0$ and Bob responds with $b \neq 0$. Alice now sets $v = b$. So, under VPS, where each player gets exactly one set from each pair $(x, x+b)$, this would mean Alice ends up taking the vector $b + b = 0$ and Bob ends up taking $a + b$. Alice turns this around: she takes $a + b$ in her second turn, and never takes 0, forcing Bob to take 0 at some point. Besides this single swap, Alice follows VPS exactly. Now, Alice's total sum at the end is $a + b$ "more" than what it would have been under VPS. So her final sum is either $0 + a + b$ or $b + a + b$, i.e. either $a + b$ or $a$. But she has both of these so she wins. Finally, it is not hard to see that: (i) This strategy breaks down if Alice's first move is $a = 0$, and moreover, Bob can actually execute a nearly identical strategy in this case to win. (ii) The case where Bob's first move is $b = 0$ can be handled. This completes the proof that Alice can win for all $a \neq 0$. $\square$ Remark 1: Another really nice application of these ideas is China TST 2011. Despite outward differences, both problems ``feel" very similar to me due to the nice exploitation of the fact that translation by a non-zero vector in $\mathbb{F}_{2}^{n}$ is involutive and has no fixed points, thereby creating a pairing. Remark 2: The structure of a simple "vanilla" algorithm modified with a small but clever twist occurs frequently in harder olympiad problems. Sadly, this structure is often obscured by unmotivated official solutions. $^\dagger$ Forgive the terrible pun

Quote: The numbers $0$ through $2^n-1$ are written on a card of decks, where $n\ge 3$. The players Alice and Bob take cards from the deck alternatively, with Alice going first. After the deck is empty, if someone can remove a card such that the XOR of every other card they have is $0$, then they win. Which numbers can Alice pick so that she has a winning strategy? I claim that the answer is everything but $0$. First, notice that the XOR of everything is $0$, so the XORs of the cards that each player has at the end are equal and the game must be decisive. Bob's winning strategy given Alice chooses $0$ is as follow: he draws an arbitrary number $x$. Then, if Alice chooses $y$ on her 2nd move, Bob chooses $x\oplus y$, and afterward whenever Alice picks a number, then Bob shall pick the XOR of $y$ and that number. We use the representation of binary numbers as vectors in $\mathbb{F}_{2}^{n}$. Consider a basis $B$ of $\mathbb{F}_2^{n}$ containing $\vec{y}$; Then, Alice has chosen $\vec{0}, \vec{y}$, and either $\vec{y}\oplus \vec{v}$ or $\vec{v}$ for all $v\in \text{Span}\{B\setminus \vec{y}\}\setminus \vec{x}$. It's not hard to see that the XOR of Alice's cards is either $\vec{x}$ or $\vec{x}+\vec{y}$, but she has neither. Now, if Alice chooses something other than $0$ on her first turn, she will replicate Bob's strategy above under the assumption that Bob already chose $0$ before the game. Bob will pick $0$ at some point, after which Alice can steal an arbitrary card from the table, hide it in her sleeves, and change her name to Calice. Now, whenever her strategy requires her to choose the hidden card, Calice replaces the hidden card with an arbitrary card from the deck, and otherwise she doesn't touch the hidden card. At the end, Calice will ceremonially restore her hidden card. Under this strategy, Calice can make identical choices as Bob in his winning strategy at each moment, while Bob gets nerfed, hence Calice wins. Remark: by taking an appropriate automorphism between two bases, one can immediately see that all nontrivial starters result in the same outcome for Alice, and moreover it's the opposite outcome compared to starting with zero via strategy stealing.

Beautiful strategy! Turns out the ability to biject to $\mathbb{F}_{1024}$ is a red herring . Biject to $\mathbb{Z}_2^{10}$ for ease of writing. Anyways, somebody must win obviously. Now suppose the first player starts with $0$. Then the first moves of the game are: First player: $0$ Second player: $a$ First player: $a+b$ Then next: Second player $b$ and the second player always chooses $a+b$ xor the first player's choice from here on. Notice $a, b$ are two elements of a basis, and the shifted subspaces generated by these always generate an overall xor of either $a$ or $b$, with the only exception being the subspace in the first four moves. Hence in the end, the global xor, by parity, is either $a$ or $b$, so the second player wins in either case. Hence choosing $0$ as your first move loses the game. Now as the first player, you have a special ability known as pretending you are the second player, where you pretend the second player is first and has already chosen $0$, and play accordingly. Since the second player will be forced to choose $0$ on the last turn, the illusion becomes reality, so as long as the first player chooses a nonzero number and uses the same strategy as before, they win. So the answer is all nonempty cards. Notice the same result is not true for $n = 1, 2$, but it starts to work starting from $n = 3$ since $\frac{2^n}{4} - 1$ is odd.

Answer. All the moves except for taking the empty card. Proof. Denote by $\varnothing$ the empty card. Define as a card-sum $A_1\oplus A_2\oplus \dots \oplus A_n$ as a card of deck, consisting exactly of all numbers belonging to and odd number of $A_i$. Since each digit is written on exactly $512$ cards, card-sums of sets, owned by players at the end of game, are the same card $B.$ Then the player owning $B$ is the unique winner. Lemma. Let $C\neq \varnothing$ be a card. If we pick $512$ cards with card-sum $S$ in such way that from every pair $(X,X\oplus C)$ was picked exactly one card, then $S\in\left \{ \varnothing, C \right \}$. Proof. Fix come digit $c$ from $C$. Taking from every pair $(X,X\oplus C)$ a card, which doesn't include $c$ we get the exactly list of all such sets, in particular their card sum is $\varnothing$. But we easily see, that with swap of taken number in pair this card-sum either remains the same, or changes by $C$ $\Box$ Assume first player takes $\varnothing$ at first move. Let second player takes any card $A,$ after what second player takes $B$. Then the strategy for the second player would firstly be in taking card $A\oplus B,$ and then responding to pick of first player some card from pair $(X,X\oplus B)$ by picking the other card. At the end of game imagine that $A$ is replaced with $\varnothing$, so by lemma card-sum of second player is either $\varnothing$ or $B$. Then in reality he has card-sum either $A$ or $A\oplus B,$ so done. Now assume that first player takes any card $A\neq \varnothing$ at first move. If second player takes $B\neq \varnothing$ at his first move, let first player takes $A\oplus B.$ All cards are now divided into pairs $(X,X\oplus B)$ and one extra card; if second player takes one card from pair, let first takes the other card, otherwise he takes arbitrary card and so makes new extra card. Thus at the end of game first and second players get roles reversed from previous case, implying the conclusion. If second player takes $\varnothing$ pick any card $B$, which haven't been taken yet. Let first player takes $A\oplus B$, and continue his strategy as above. Considering of this case finishes the whole proof $\blacksquare$

Let the first player be Ash and the second be Bash. The answer is that Ash has a winning strategy if and only if she picks a nonzero card for her first move. For each card $X$, assign a vector $\vec x \in \mathbb{Z}_2^{10}$ where the $i$th component of $\vec x$ is $1$ iff the digit $i$ is on $X$. We make the following preliminary observations: (Identity) For any card $X$, $X+0=0+X=X$. (Associativity) For cards $A$, $B$, and $C$, $A+(B+C)=(A+B)+C$. (Abelian) For cards $A$ and $B$, $A+B=B+A$. (Involution) For cards $A$ and $B$, $A+B=0$ if and only if $A=B$. The above properties are enough to solve the problem. Now split the cards into $512$ disjoint pairs of the form $(X, X+Y)$ for fixed nonzero $Y$, which creates a partition $\Gamma_Y$ of the cards. Thanks to the properties (especially property 4), the sum of any selection of exactly one card from each pair must be either $0$ or $Y$. We now do casework on Ash's first move. Suppose that Ash begins with $0$. Then Bash can draw some card $A$, and let Ash's second card be $B$. After Ash takes her second card, Bash will choose $A+B$. Henceforth, each time Ash chooses an element of some pair, Bash will choose the other element, eventually leading to Bash's win. (Classic counterplay in combinatorial games; consider a partition into pairs and then keep choosing the element not chosen from each one, leading to a win.) On the other hand, suppose that Ash starts with $A \neq 0$. Then Bash can start with $B \neq 0$. Ash then responds with $A+B$. Consider the partition $\Gamma_B$ of the cards. Then in each move by Ash henceforth, a single card from each pair is removed. Thus the sum of Ash's cards at the end is either $0+(A+B)=A+B$ or \[ B+(A+B)=(B+A)+B=(A+B)+B=A+(B+B)=A+0=A, \]so Ash never takes a $0$. However, Bash must eventually take a $0$, which finishes.