Maths Olympiad Prep

Library / /103 of 133

Combinatorics Difficulty 6.4 National olympiad Prove it Saudi Arabia

Aws plays a solitaire game on a fifty-two card deck: whenever two cards of the same color are adjacent, he can remove them. Aws wins the game if he removes all the cards. If Aws starts with the cards in a random order, what is the probability for him to win?

Solution

Let us consider the positions 1,2,,521,2, \ldots, 52, from left to right, of the fifty-two cards at the beginning of the game. Whenever Aws removes two adjacent cards, we subtract 22 from the positions of all the cards on the right of these adjacent removed cards.

We notice that, at each operation, if a card is not removed, even if its position changes, it will keep the same parity. We notice also that whenever two adjacent cards of the same color are removed, the positions of these two cards have different parity.

Define RR to be the number of red cards with even positions at the beginning subtracted from the number of red cards with odd positions at the beginning. Clearly, RR is an invariant under Aws' operations. Hence, if at the beginning, R0R \neq 0, Aws can never remove all his cards.

Now assume that R=0R=0 and that Aws has started playing. If there are no more red cards, then Aws is left with only black cards, so he can keep removing adjacent cards until he ends up with no card. If there is at least one red card, because R=0R=0, there is at least one red card with even position e1e_{1} and one red card with odd position o1o_{1}. Assume, without loss of generality, that e1<o1e_{1}<o_{1}.

Consider o=minOo=\min \mathcal{O}, where O\mathcal{O} is the set of odd positions oo' of red cards with o>e1o'>e_{1}. Number oo exists since o1Oo_{1} \in \mathcal{O}. Consider e=maxEe=\max \mathcal{E}, where E\mathcal{E} is the set of even positions ee' of red cards with o>eo>e'. Number ee exists since e1Ee_{1} \in \mathcal{E}. If o=e+1o=e+1, then there are two adjacent red cards that Aws can remove. If o>e+1o>e+1 then oe+3o \geq e+3 and the positions between ee and oo are all occupied by adjacent black cards. In this case, Aws can remove adjacent black cards. This proves that if R=0R=0, Aws can keep removing cards until he removes all cards.

Hence, Aws can win if and only if R=0R=0. In this situation, there must be 1313 red cards with even positions and 1313 red cards with odd positions. There are precisely (2613)226!2\binom{26}{13}^{2} \cdot 26!^{2} possible such starting positions and the probability for Aws to win is

(2613)2(5226). \frac{\binom{26}{13}^{2}}{\binom{52}{26}}.

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 and solution reproduced as published; topic and difficulty added by this site.