Putnam 1993

Problem B2

A deck of 2n cards numbered from 1 to 2n is shuffled and n cards are dealt to A and B. A and B alternately discard a card face up, starting with A. The game when the sum of the discards is first divisible by 2n + 1, and the last person to discard wins. What is the probability that A wins if neither player makes a mistake?

Solution

Fairly easy.

B always wins irrespective of the deal. The stuff about random shuffling and probabilities is a red herring. Note first that both players have perfect information (because each can see his own cards and the discards and hence deduce the other player's hand).

A cannot win on his first play. Now suppose it is B's turn. Each card B might play will give a different total and so requires a different card for A to win on the following move. But B has one more card than A, so he can choose a card which does not allow A to win on the next move. Thus B can always play so that A does not win on the following move. But one player must win after 2n plays or less, so it must be B.