Problem A3 from the Putnam

Here is problem A3 from the 2007 Putnam exam:

Let k be a positive integer. Suppose that the integers 1, 2, 3, ..., 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?

I'm going to give a solution that probably wouldn't get full credit on the Putnam (I'm leaving out some details) -- a lot gets lost in the details.

First, instead of considering these numbers, just consider everything modulo 3. In particular, we want to know what the probability is that if we arrange k+1 +1s, k -1s, and k 0s in random order, no partial sum will be divisible by 3. (The number of permutations of {1, ..., 3k+1} which map to a given sequence modulo 3 is the same for any such sequence, so this is legitimate.) The number of ways to arrange k+1 +1s, k -1s, and k 0s is, of course, .

Now we consider the simpler problem of arranging k+1 +1s and k -1s so that no partial sum is divisible by 3. Clearly the last partial sum (i. e. the full sum) is 1, and the sequence of partial sums moves upwards or downwards by 1 at each step. Such an arrangement must begin with a +1; if it began with a -1 then the first partial sum would be -1, the last partial sum would be 1, so some intermediate partial sum would have to be zero. This +1 must be followed with another +1 to avoid having the second partial sum be 0; then a -1 so that the third partial sum is not 3; and so on. Thus there is exactly one such arrangement, namely

+1, +1, -1, +1, -1, +1, -1, ..., +1, -1

where the partial sums are

1, 2, 1, 2, 1, 2, 1, ..., 2, 1.

The probability of obtaining an arrangement with no partial sums divisible by three if we pick at random from all arrangements of k+1 +1s and k -1s is thus .

Now, to obtain an arrangement of k+1 +1s, k -1s, and k 0s uniformly at random, we can first place the 0s at random, then the +1s and -1s. There are ways in which the 0s can be placed. Interspersing 0s among some arrangement of +1s and -1s doesn't change the set of partial sums which occur -- unless a 0 precedes all the +1s and -1s. So the probability of placing the 0s such that a "good" arrangement is still possible is . There is exactly one way to place the +1s and -1s once we've done this that actually gives a "good" arrangement. So the final probability is

For example, f(1) = 1/4 = 6/24; this corresponds to the six "good" arrangements of {1, 2, 3, 4}, namely 1342, 1432, 1423, 4312, 4132, 4123. The function f(k) is asymptotic to from Stirling's approximation. I like to interpret the 4 there as meaning that if we are building up such an arrangement of +1s, -1s, and 0s, we have a probability of roughly 1/4^1/3 of making an acceptable choice at each step; the "1/3" comes from the fact that we actually make 3k choices in building up such an arrangement. This constant is about 0.63, and seems about right; it should be around two-thirds, since at each step except the first, exactly two of {0, +1, -1} are valid ways to extend the sequence.

The simplicity of the problem seems to hinge on the fact that the partial sums have to fluctuate within a very narrow band, and only move by ± 1. If we instead required that no partial sums were divisible by, say, 4, so the partial sums could move around in {1, 2, 3}, this would be trickier. But I think the best way to work that problem would still be to work modulo 3, so each summand is either +1, -1, or 0; the crucial observation I made early on was that if the partial sum was -1 at some point and +1 later it had to go through zero, but you don't get this sort of "continuity" (the observation is a discrete analogue of the Intermediate Value Theorem) in any modulus other than 3.

(This is basically the same as the solution given at the UNL Putnam archive, but I came up with it independently.)