Putnam 1995, Problem A-6

Suppose that each of \( n \) people writes down the numbers 1,2,3 in random order in one column of a \( 3 \times n \) matrix, with all orders equally likely and with the orders for different columns independent of each other. Let the row sums \( a,b,c \) of the resulting matrix be rearranged (if necessary) so that \( a \leq b \leq c \). Show that for some \( n \geq 1995 \), it is at least four times as likely that both \( b = a+1 \) and \( c = a+2 \) as that \( a = b = c \).

Solution:
View this as a random walk/Markov process with states \( (i, j, k) \) the triples of integers with sum 0, corresponding to the difference between the first, second and third rows with their average (twice the number of columns). Adding a new column adds on a random permutation of the vector \( (1, 0, -1) \). I prefer to identify the triple \( (i, j, k) \) with the point \( (i - j) + (j - k) \omega + (k - i) \omega^2 \) in the plane, where \( \omega \) is a cube root of unity. Then adding a new column corresponds to moving to one of the six neighbors of the current position in a triangular lattice.  
What we'd like to argue is that for large enough \( n \), the ratio of the probabilities of being in any two particular states goes to 1. Then in fact, we'll see that eventually, about six times as many matrices have \( a = b - 1, b = c - 1 \) than \( a = b = c \). This is a pain to prove, though, and in fact is way more than we actually need.  
Let \( C_n \) and \( A_n \) be the probability that we are at the origin, or at a particular point adjacent to the origin, respectively. Then \( C_{n+1} = A_n \). (In fact, \( C_{n+1} \) is 1/6 times the sum of the probabilities of being at each neighbor of the origin at time \( n \), but these are all \( A_n \).) So the desired result, which is that \( C_n / A_n \geq 2/3 \) for some large \( n \), is equivalent to \( A_{n+1} / A_n \geq 2/3 \).  
Suppose on the contrary that this is not the case; then \( A_n < c(2/3)^n \) for some constant \( n \). However, if \( n = 6m \), the probability that we chose each of the six types of moves \( m \) times is already \( (6m)! / [m!^6 6^{6m}] \), which by Stirling's approximation is asymptotic to a constant times \( m^{-5/2} \). This term alone is bigger than \( c(2/3)^n \), so we must have \( A_{n+1} / A_n \geq 2/3 \) for some \( n \). (In fact, we must have \( A_{n+1} / A_n \geq 1 - \epsilon \) for any \( \epsilon > 0 \).)