Putnam 2017, Problem A-5

Each of the integers from \( 1 \) to \( n \) is written on a separate card, and then the cards are combined into a deck and shuffled. Three players, \( A \), \( B \), and \( C \), take turns in the order \( A, B, C, A, \ldots \) choosing one card at random from the deck. (Each card in the deck is equally likely to be chosen.) After a card is chosen, that card and all higher-numbered cards are removed from the deck, and the remaining cards are reshuffled before the next turn. Play continues until one of the three players wins the game by drawing the card numbered \( 1 \).  
Show that for each of the three players, there are arbitrarily large values of \( n \) for which that player has the highest probability among the three players of winning the game.

Solution:
### First solution
Let \( a_n, b_n, c_n \) be the probabilities that players \( A, B, C \), respectively, will win the game. We compute these by induction on \( n \), starting with the values  
\[
a_1 = 1, \quad b_1 = 0, \quad c_1 = 0.
\]  

If player \( A \) draws card \( k \), then the resulting game state is that of a deck of \( k - 1 \) cards with the players taking turns in the order \( B, C, A, B, \ldots \). In this state, the probabilities that players \( A, B, C \) will win are \( c_{k-1}, a_{k-1}, b_{k-1} \) provided that we adopt the convention that  
\[
a_0 = 0, \quad b_0 = 0, \quad c_0 = 1.
\]  

We thus have  
\[
a_n = \frac{1}{n} \sum_{k=1}^n c_{k-1}, \quad b_n = \frac{1}{n} \sum_{k=1}^n a_{k-1}, \quad c_n = \frac{1}{n} \sum_{k=1}^n b_{k-1}.
\]  

Put  
\[
x_n = a_n - b_n, \quad y_n = b_n - c_n, \quad z_n = c_n - a_n;
\]  
we then have  
\[
x_{n+1} = \frac{n}{n+1} x_n + \frac{1}{n+1} z_n, \quad y_{n+1} = \frac{n}{n+1} y_n + \frac{1}{n+1} x_n, \quad z_{n+1} = \frac{n}{n+1} z_n + \frac{1}{n+1} y_n.
\]  

Note that if \( a_{n+1} = b_{n+1} = c_{n+1} = 0 \), then  
\[
x_n = -n z_n = n^2 y_n = -n^3 x_n = n^4 z_n
\]  
and so \( x_n = z_n = 0 \), or in other words \( a_n = b_n = c_n \). By induction on \( n \), we deduce that \( a_n, b_n, c_n \) cannot all be equal. That is, the quantities \( x_n, y_n, z_n \) add up to zero and at most one of them vanishes; consequently, the quantity \( r_n = \sqrt{x_n^2 + y_n^2 + z_n^2} \) is always positive and the quantities  
\[
x_n' = \frac{x_n}{r_n}, \quad y_n' = \frac{y_n}{r_n}, \quad z_n' = \frac{z_n}{r_n}
\]  
form the coordinates of a point \( P_n \) on a fixed circle \( C \) in \( \mathbb{R}^3 \).  

Let \( P_n' \) be the point \( (z_n, x_n, y_n) \) obtained from \( P_n \) by a clockwise rotation of angle \( \frac{2\pi}{3} \). The point \( P_{n+1} \) then lies on the ray through the origin passing through the point dividing the chord from \( P_n \) to \( P_n' \) in the ratio \( 1 : n \). The (clockwise) arc from \( P_n \) to \( P_{n+1} \) therefore has a measure of  
\[
\arctan \frac{\sqrt{3}}{2n - 1} = \frac{\sqrt{3}}{2n - 1} + O(n^{-3});
\]  
these measures form a null sequence whose sum diverges. It follows that any arc of \( C \) contains infinitely many of the \( P_n \); taking a suitably short arc around the point \( (\frac{\sqrt{2}}{2}, 0, -\frac{\sqrt{2}}{2}) \), we deduce that for infinitely many \( n \), \( A \) has the highest winning probability, and similarly for \( B \) and \( C \).  

### Remark
From the previous analysis, we also deduce that  
\[
\frac{r_{n+1}}{r_n} = \frac{\sqrt{n^2 - n + 1}}{n + 1} = 1 - \frac{3}{2(n + 1)} + O(n^{-2}),
\]  
from which it follows that \( r_n \sim c n^{-3/2} \) for some \( c > 0 \).  

### Second solution
(by Noam Elkies) In this approach, we instead compute the probability \( p_n(m) \) that the game ends after exactly \( m \) turns (the winner being determined by the residue of \( m \mod 3 \)). We use the convention that \( p_0(0) = 1 \), \( p_0(m) = 0 \) for \( m > 0 \). Define the generating function \( P_n(X) = \sum_{m=0}^n p_n(m) X^m \). We will establish that  
\[
P_n(X) = \frac{X(X + 1) \cdots (X + n - 1)}{n!}
\]  
(which may be guessed by computing \( p_n(m) \) for small \( n \) by hand). There are several ways to do this; for instance, this follows from the recursion  
\[
P_n(X) = \frac{1}{n} X P_{n-1}(X) + \frac{n - 1}{n} P_{n-1}(X).
\]  

(In this recursion, the first term corresponds to conditional probabilities given that the first card drawn is \( n \), and the second term corresponds to the remaining cases.)  

Let \( \omega \) be a primitive cube root of \( 1 \). With notation as in the first solution, we have  
\[
P_n(\omega) = a_n + b_n \omega + c_n \omega;
\]  
combining this with the explicit formula for \( P_n(X) \) and the observation that  
\[
\arg(w + n) = \arctan \frac{\sqrt{3}}{2n - 1}
\]  
recovers the geometric description of \( a_n, b_n, c_n \) given in the first solution (as well as the remark following the first solution).  

### Third solution
For this argument, we use the auxiliary quantities  
\[
a_n' = a_n - \frac{1}{3}, \quad b_n' = b_n - \frac{1}{3}, \quad c_n' = c_n - \frac{1}{3};
\]  
these satisfy the relations  
\[
a_n' = \frac{1}{n} \sum_{k=1}^n c_{k-1}', \quad b_n' = \frac{1}{n} \sum_{k=1}^n a_{k-1}', \quad c_n' = \frac{1}{n} \sum_{k=1}^n b_{k-1}'
\]  
as well as  
\[
a_{n+1}' = a_n' + \frac{1}{n+1} (c_n' - a_n'), \quad b_{n+1}' = b_n' + \frac{1}{n+1} (a_n' - b_n'), \quad c_{n+1}' = c_n' + \frac{1}{n+1} (b_n' - c_n').
\]  

We now show that \( \sum_{n=1}^\infty a_n' \) cannot diverge to \( +\infty \) (and likewise for \( \sum_{n=1}^\infty b_n' \) and \( \sum_{n=1}^\infty c_n' \) by similar reasoning). Suppose the contrary; then there exists some \( \epsilon > 0 \) and some \( n_0 > 0 \) such that \( \sum_{k=1}^n a_k' \geq \epsilon \) for all \( n \geq n_0 \). For \( n > n_0 \), we have \( b_n' \geq \epsilon \); this in turn implies that \( \sum_{n=1}^\infty b_n' \) diverges to \( +\infty \). Continuing around the circle, we deduce that for \( n \) sufficiently large, all three of \( a_n', b_n', c_n' \) are positive; but this contradicts the identity  
\[
a_n' + b_n' + c_n' = 0.
\]  

We thus conclude that \( \sum_{n=1}^\infty a_n' \) does not diverge to \( +\infty \); in particular, \( \liminf_{n \to \infty} a_n' \leq 0 \). By the same token, we may see that \( \sum_{n=1}^\infty a_n' \) cannot converge to a positive limit \( L \) (and likewise for \( \sum_{n=1}^\infty b_n' \) and \( \sum_{n=1}^\infty c_n' \) by similar reasoning). Namely, this would imply that \( b_n' \geq L/2 \) for \( n \) sufficiently large, contradicting the previous argument.  

By similar reasoning, \( \sum_{n=1}^\infty a_n' \) cannot diverge to \( -\infty \) or converge to a negative limit \( L \) (and likewise for \( \sum_{n=1}^\infty b_n' \) and \( \sum_{n=1}^\infty c_n' \) by similar reasoning).  

We next establish that there are infinitely many \( n \) for which \( a_n' > 0 \) (and likewise for \( b_n' \) and \( c_n' \) by similar reasoning). Suppose to the contrary that for \( n \) sufficiently large, we have \( a_n' \leq 0 \). By the previous arguments, the sum \( \sum_{n=1}^\infty a_n' \) cannot diverge to \( \infty \) or converge to a nonzero limit; it must therefore converge to \( 0 \). In particular, for \( n \) sufficiently large, we have \( b_n' = \sum_{k=1}^n a_k' \geq 0 \). Iterating the construction, we see that for \( n \) sufficiently large, we must have \( c_n' \leq 0, a_n' \geq 0, b_n' \leq 0, c_n' \geq 0 \). As a result, for \( n \) sufficiently large we must have \( a_n' = b_n' = c_n' = 0 \); but we may rule this out as in the original solution.  

By similar reasoning, we may deduce that there are infinitely many \( n \) for which \( a_n' < 0 \) (and likewise for \( b_n' \) and \( c_n' \) by similar reasoning). We now continue using a suggestion of Jon Atkins. Define the values of the sequence \( x_n \) according to the relative comparison of \( a_n', b_n', c_n' \) (using the fact that these cannot all be equal):  
\[
x_n = 1: \quad a_n' \leq b_n' < c_n', \quad x_n = 2: \quad b_n' \leq c_n' < a_n', \quad x_n = 3: \quad c_n' \leq a_n' < b_n',
\]  
\[
x_n = 4: \quad a_n' < c_n' \leq b_n', \quad x_n = 5: \quad b_n' < a_n' \leq c_n', \quad x_n = 6: \quad c_n' < b_n' \leq a_n'.
\]  

We consider these values as states and say that there is a transition from state \( i \) to state \( j \), and write \( i \Rightarrow j \), if for every \( n \geq 2 \) with \( x_n = i \) there exists \( n' > n \) with \( x_{n'} = j \). (In all cases when we use this notation, it will in fact be the case that the first value of \( n' > n \) for which \( x_{n'} \neq i \) satisfies \( x_{n'} = j \), but this is not logically necessary for our final conclusion.)  

Suppose that \( x_n = 1 \). By the earlier discussion, we must have \( a_n' > 0 \) for some \( n' > n \), and so we cannot have \( x_n' = 1 \) for all \( n' > n \). On the other hand, as long as \( x_n = 1 \), we have  
\[
c_{n+1}' - b_{n+1}' = c_n' - b_n' + \frac{1}{n+1} (2b_n' - a_n' - c_n') = \frac{n - 1}{n+1} (c_n' - b_n') + \frac{1}{n+1} (c_n' - a_n') > 0,
\]  
\[
c_{n+1}' - a_{n+1}' = c_n' - a_n' + \frac{1}{n+1} (a_n' + b_n' - 2c_n') = \frac{n - 1}{n+1} (c_n' - a_n') + \frac{1}{n+1} (b_n' - a_n') > 0.
\]  

Consequently, for \( n' \) the smallest value for which \( x_{n'} \neq x_n \), we must have \( x_{n'} = 2 \). By this and two similar arguments, we deduce that  
\[
1 \Rightarrow 5, \quad 2 \Rightarrow 6, \quad 3 \Rightarrow 4.
\]  

Suppose that \( x_n = 4 \). By the earlier discussion, we must have \( a_n' < 0 \) for some \( n' > n \), and so we cannot have \( x_n' = 4 \) for all \( n' > n \). On the other hand, as long as \( x_n = 4 \), we have  
\[
b_{n+1}' - a_{n+1}' = b_n' - a_n' + \frac{1}{n+1} (2a_n' - b_n' - c_n') = \frac{n - 1}{n+1} (b_n' - a_n') + \frac{1}{n+1} (b_n' - c_n') > 0,
\]  
\[
c_{n+1}' - a_{n+1}' = c_n' - a_n' + \frac{1}{n+1} (a_n' + b_n' - 2c_n') = \frac{n - 1}{n+1} (c_n' - a_n') + \frac{1}{n+1} (b_n' - c_n') > 0.
\]  

Consequently, for \( n' \) the smallest value for which \( x_{n'} \neq x_n \), we must have \( x_{n'} = 1 \). By this and two similar arguments, we deduce that  
\[
4 \Rightarrow 1, \quad 5 \Rightarrow 2, \quad 6 \Rightarrow 3.
\]  

Combining, we obtain  
\[
1 \Rightarrow 5 \Rightarrow 2 \Rightarrow 6 \Rightarrow 3 \Rightarrow 4 \Rightarrow 1
\]  
and hence the desired result.