I have a question that I found in a maths olympiad paper:
Question: You have the set of all natural numbers from $1$ to $3n+1$, where $n$ is a positive integer. You randomly select numbers from your set (without replacement), and at each stage you compute the sum of all the numbers you have selected up until that point. If the sum is divisible by $3$, you stop. What is the probability of you selecting all $3n+1$ number in the set?
Attempt: The way I was thinking of solving this was by viewing all numbers in terms of modulo $3$. In this view, you have $n+1$ ones and $n$ zeros and twos. With this, you must first print a number that equals $1$ mod $3$ (I think!), and then I get stuck. Can anyone help?
Initially, you have $n$ numbers $\equiv 0\pmod 3$, $n+1 $ numbers $\equiv 1\pmod 3$, and $n$ numbers $\equiv -1\pmod 3$ and our running sum is $\equiv 0\pmod 3$. Let us ignore those $\equiv 0\pmod 3$ - we can sprinkle them between the others afterwards, just not at the beginning. Then (apart from the first round) the next number must always be taken from the pool of numbers congruent to the running sum, and thereby flip the running sum to the other case. So the first two numbers must be of the same congruence class and from then on we always flip. It follows that the only valid pattern is $$+1,+1,-1,+1,-1,+1,-1,\ldots, +1,-1,+1,-1. $$ After that we have ${3n\choose n}$ ways of adding $0$'s between these but not at the first position. There are $(n+1)!$ ways to fill the $+1$ positions with numbers $\equiv +1\pmod 3$, $n!$ ways to fill the $-1$ positions with numbers $\equiv -1\pmod 3$, and $n!$ ways to fill the $0$ positions. So in total, we have $$ {3n\choose n}\cdot(n+1)!\cdot n!^2$$ good orders out of $(3n+1)!$ possible orders. The probability of success is therefore $$\frac{{3n\choose n}\cdot(n+1)!\cdot n!^2}{(3n+1)!} =\frac{(3n)!(n+1)!n!}{(2n)!(3n+1)!}=\frac{(n+1)}{(3n+1){2n\choose n}} $$