Maths Olympiad Prep

Library / /343 of 383

Combinatorics Difficulty 9.0 IMO level Prove it IMO

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.

Solution

Let us identify each card with the set of digits written on it. For any collection of cards C1,C2,,CkC_{1}, C_{2}, \ldots, C_{k} denote by their sum the set C1C2CkC_{1} \triangle C_{2} \triangle \cdots \triangle C_{k} consisting of all elements belonging to an odd number of the CiC_{i}'s. Denote the first and the second player by F\mathcal{F} and S\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 F\mathcal{F} will be the same as that of S\mathcal{S}; denote this sum by CC. Then the player who took CC can throw it out and get the desired situation, while the other one cannot. Thus, the player getting card CC wins, and no draw is possible.

Now, given a nonempty card BB, one can easily see that all the cards can be split into 512 pairs of the form (XX, XBX \triangle B) because (XBX \triangle B) B=X\triangle B = X. The following lemma shows a property of such a partition that is important for the solution.

Lemma. Let BB \neq \varnothing be some card. Let us choose 512 cards so that exactly one card is chosen from every pair (X,XB)(X, X \triangle B). Then the sum of all chosen cards is either \varnothing or BB.

Proof. Let bb be some element of BB. Enumerate the pairs; let XiX_{i} be the card not containing bb in the ithi^{\text{th}} pair, and let YiY_{i} be the other card in this pair. Then the sets XiX_{i} are exactly all the sets not containing bb, therefore each digit aba \neq b is written on exactly 256 of these cards, so X1X2X512=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 BB several times to this sum, thus the sum will either remain unchanged or change by BB, as required. \square

Now we consider two cases.

Case 1. Assume that F\mathcal{F} takes the card \varnothing on his first move. In this case, we present a winning strategy for S\mathcal{S}.

Let S\mathcal{S} take an arbitrary card AA. Assume that F\mathcal{F} takes card BB after that; then S\mathcal{S} takes ABA \triangle B. Split all 1024 cards into 512 pairs of the form (X,XB)(X, X \triangle B); we call two cards in one pair partners. Then the four cards taken so far form two pairs (,B\varnothing, B) and (A,ABA, A \triangle B) belonging to F\mathcal{F} and S\mathcal{S}, respectively. On each of the subsequent moves, when F\mathcal{F} takes some card, S\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 AA belonging to S\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 BB. Now, replacing \varnothing back by AA we get that the actual sum of the cards of S\mathcal{S} is either AA or ABA \triangle B, and he has both these cards. Thus S\mathcal{S} wins.

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

Assume that S\mathcal{S} takes some card BB \neq \varnothing on his first move; then F\mathcal{F} takes ABA \triangle B. Again, let us split all the cards into pairs of the form (X,XB)(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 BB has). Now, on each of the subsequent moves, if S\mathcal{S} takes some element from a complete pair, then F\mathcal{F} takes its partner. If S\mathcal{S} takes the extra element, then F\mathcal{F} takes an arbitrary card YY, and the partner of YY becomes the new extra element.

Thus, on his last move S\mathcal{S} is forced to take the extra element. After that player F\mathcal{F} has cards AA and ABA \triangle B, player S\mathcal{S} has cards BB and \varnothing, and F\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 F\mathcal{F} wins.

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.