MHB If $k$ is large, the expression above is approximately $\frac{1}{3}$.

[Ackbach]

Here is this week's POTW:

-----

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

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Congratulations to castor28 for his correct solution to this week's POTW, which was Problem A-3 in the 2007 Putnam Archive. His solution follows:

[sp]
We consider the sequence modulo 3, and look at the conditions required to have a good sequence. We may ignore the positions of the 0's, which contribute nothing to the running total (except for the fact that the first number must not be one of them).

The other numbers constitute a sequence of 1's and 2's, of length $2k+1$, in which each number after the first is uniquely determined by the numbers before it. This gives two possible sequences: $11212121\ldots$ and $22121212\ldots$. Because we have $k+1$ numbers in class 1 and $k$ numbers in class 2, only the first sequence is allowed.

The number of sequences of $(k+1)$ 1's and $(k)$ 2's is the number of ways to choose the $k$ 2's in a set of $2k+1$ numbers, i.e., $\binom{2k+1}{k}$. If we factor in the fact that the first number must not be a multiple of 3 ($2k+1$ choices out of $3k+1$), we get the probability:
$$ \frac{2k+1}{3k+1}\times\frac{1}{\binom{2k+1}{k}}=\frac{k!\,(k+1)!}{(2k)!\,(3k+1)}$$
[/sp]