Writeup: Putnam 2007 A3

19 Jul, 2025

Problem Statement

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

My Solution.

Note that if we work instead by removing numbers one by one from the end of this sequence, satisfying the indivisibility by $3$ condition is equivalent to satisfying the condition if we do it forwards.

Now note that the sum $mod 3$ of all the numbers at the end of our process is trivially $1$ . So we can't write a number that is $1 mod 3$ at the end, otherwise we would have written a number divisible by $3$ during the process. So we have to write erase a number that is either $0$ or $2 mod 3$ at the end. We must eventually write that is $2 mod 3$ . After we write this, our running sum is now $2 mod 3$ , and we must erase a number that is either $0$ or $1 mod 3$ at the end.

It's apparent from this that our sequence (writing backwards) must be of the form

- 1, 1, - 1, 1, - 1, \dots 1 mod 3

with some $0 mod 3$ sprinkled throughout.

Note that we have $k + 1$ things that are $1 mod 3$ , $k$ things that are $2 mod 3$ , and $k$ things that are $0 mod 3$ .

If we use stars and bars, we note that there are $2 k + 1$ dividers and $2 k + 1$ gaps in between the $1$ 's and $- 1$ 's (we can't put the $0^{'} s a t t h e v e r y b e g i n n i n g$ .

So there are $(\binom{3 k}{k})$ ways to disperse the $3$ 's among the sequence. Then, there are $(k + 1)!$ ways to permute the $1$ 's and $k!$ ways to permute the $- 1$ 's and $0$ 's

So the total number of sequences satisfying the condition are

\frac{(3 k)! (k + 1)! (k!)^{2}}{k! (2 k)!} = \frac{(3 k)! (k + 1)! k!}{(2 k)!} .

Divide this by $(3 k + 1)!$ sequences to get our probability,

\frac{(k + 1)! k!}{(2 k)! (3 k + 1)} .