Probability problem that involves number theory Let $k \in Z^+$. Assume integers 1, 2, 3, . . . , 3k+ 1 are written down randomly. Calculate the probability that at no time during this process, the sum of the integers is a positive integer divisible by 3?
Attempt: I am trying to approach this by finding the complement of what's being asked which is the number times the sum of the integers is divisible by 3. The sample space I think is $\prod_{i = 0}^{3k+1}(3(i)+1)!$ since that's I think the number of trees we can generate by doing this process. 
I think my sample space is off. The right way is to
 figure out how many sequences can we have at some time i where $1 \leq i \leq 3k+1$ during the process. This is:
$(3k+1) +(3K+1)(3k) + (3k+1)(3k)(3k-1)+ ... + (3k+1)!$ 
I also have the feeling that this is done by using states. There are just three state where the sum can be at any time and these are: 0mod3, 1mod3 and 2mod3. We have to find all the possible ways we can reach the state 0mod3 somehow.
 A: For the problem where repitition is not allowed, i.e. we are looking at permutations of the numbers $1,2,3,\dots,3k+1$
Looking at the numbers modulo3 for now, every arrangement will be of the form $$1.1.2.1.2.1.2.1.\dots2.$$
where those numbers which are multiples of three will be placed somewhere where the dots are (not the first number of the sequence)
The reason should be clear: if the first non-multiple of three is $1$mod3, the next non-multiple of three cannot be a $2$, else we will have a sub-sum that is a multiple of three.  Therefore, the second must be a $1$ as well.  Similarly, the next must be a $2$mod3 to avoid a sub-sum being a multiple of three again, and so on.  Alternatively, if the first non-multiple of three is $2$mod3, we will have it begin $221212121\dots$, but this would require one or two more numbers which are $2mod3$ than numbers which are $1$mod3, an impossibility.  Finally, it cannot start with a multiple of three for obvious reasons.
There are $\binom{3k}{k-1}$ ways to insert the $k$ copies of $0$ into the sequence above by using stars and bars as there are $k$ 0's to place into $2k+1$ available spots.
Now, replacing the $1$'s with an arrangement of all of the numbers which are $1$mod3, replacing all of the $2$'s with an arrangement of the numbers which are $2$mod3, and similarly for the $0$'s, we have a sequence of the numbers $1,2,3,\dots,3k+1$ satisfying your conditions.
There are $(k+1)!,k!,$ and $k!$ ways to do this respectively.
There are then $(k+1)!k!k!\binom{3k}{k-1}$ ways you can arrange the numbers satisfying your desired conditions.  This is out of the $(3k+1)!$ equally likely arrangements, making the probability:
$$\frac{(k+1)!k!k!\binom{3k}{k-1}}{(3k+1)!}$$
A: JMoravitz gives nice comments above that lead to a great solution to the permutation-based problem.  The repetition-based problem is also interesting and I give some details on that: 
Suppose every step $t \in \{1, 2, 3, ...\}$ we independently pick a number uniform over $\{1, ..., M\}$, where $M \geq 3$ is a positive integer. What is the probability that the sum process is never a multiple of 3 during $t \in \{1, ..., T\}$? 
Case 1:  If $M$ is a multiple of 3, the answer is $(2/3)^T$ since we are equally likely to pick a number that is 0, 1, or 2 (mod 3). 
Case 2: If $M$ is not a multiple of 3, then we can define $p_i$ as the probability of picking a number that is $i$ (mod 3). So we can easily find $p_0, p_1, p_2$.  Then we can model the problem as a 3-state Markov chain with states $0, 1, 2$ being the current mod-3 sum. 
