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 , from left to right, of the fifty-two cards at the beginning of the game. Whenever Aws removes two adjacent cards, we subtract 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 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, is an invariant under Aws' operations. Hence, if at the beginning, , Aws can never remove all his cards.
Now assume that 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 , there is at least one red card with even position and one red card with odd position . Assume, without loss of generality, that .
Consider , where is the set of odd positions of red cards with . Number exists since . Consider , where is the set of even positions of red cards with . Number exists since . If , then there are two adjacent red cards that Aws can remove. If then and the positions between and are all occupied by adjacent black cards. In this case, Aws can remove adjacent black cards. This proves that if , Aws can keep removing cards until he removes all cards.
Hence, Aws can win if and only if . In this situation, there must be red cards with even positions and red cards with odd positions. There are precisely possible such starting positions and the probability for Aws to win is