Putnam 2007, Problem A-3

Let $k$ be a positive integer. Suppose that the integers $1,2,3,\ldots,3k+1$ are written down in random order. What is the probability that at no time during this process, the sum of the integers that have been written up to that time is a positive integer divisible by $3$? Your answer should be in closed form, but may include factorials.

Solution:
Assume that we have an ordering of $1, 2, \ldots, 3k+1$ such that no initial subsequence sums to 0 mod 3. If we omit the multiples of 3 from this ordering, then the remaining sequence mod 3 must look like $1, 1, -1, 1, -1, \ldots$ or $-1, -1, 1, -1, 1, \ldots$. Since there is one more integer in the ordering congruent to 1 mod 3 than to $-1$, the sequence mod 3 must look like $1, 1, -1, 1, -1, \ldots$.

It follows that the ordering satisfies the given condition if and only if the following two conditions hold: the first element in the ordering is not divisible by 3, and the sequence mod 3 (ignoring zeroes) is of the form $1, 1, -1, 1, -1, \ldots$. The two conditions are independent, and the probability of the first is $(2k+1)/(3k+1)$ while the probability of the second is $1/\binom{2k+1}{k}$, since there are $\binom{2k+1}{k}$ ways to order $(k+1)$ 1's and $k$ $-1$'s. Hence the desired probability is the product of these two, or
$$\frac{k!(k+1)!}{(3k+1)(2k)!}.$$