Integer sequence, probability?

Simple. Look at the elements of your list not divisible by 3 (since the rest do not change the running total mod 3). You get a pattern of 1s and -1s (better to write -1 than 2s) in terms of residues mod 3.

You'll need a pattern that alternates between 1s and -1s in order to maintain a nonzero running total (mod 3). Since there's an extra 1 (3k+1 gives us an extra 1), you start with two 1s:

1 1 -1 1 -1 1 -1 1

That's the pattern. Now you have to simply count the orderings. There are (2k+1)! possible ways (total) to order the 1s and -1s. The number of orderings of the 1s, the -1s that fit this pattern are:

1s: (k+1)!

-1s k!

Dividing that product by (2k+1)! gives:

(k+1)! k!

------------

(2k+1)!

There is no condition on the 0s except that they can't start the whole thing. There's basically a 2/3 chance that this works, but not quite. It's actually (2k+1)/(3k+1), which gives, upon multiplication with the other probability (they are independent):

(k+1)! k!

------------------

(3k+1) (2k)!

Edit: I made a typo, and have fixed it. Mistake and typo aren't the same thing. And my solution doesn't count things you don't need to count (counting slots for the multiples of 3 is highly unecessary).

This was a nice problem! Hope to see more questions from you in the future, Ben!

Let's first look at the case where k=1 to see if we can establish where the restrictions/complications arise. The successful sequences for k=1 are

1 4 3 2

1 3 4 2

1 4 2 3

4 1 3 2

4 3 1 2

4 1 2 3

We note that the sequence cannot start with a multiple of 3 otherwise it fails right away. Furthermore in this case the sequences never started with a 2. If we tried to construct a sequence beginning with a 2 we would find that eventually we would have to add a 1 or a 4 which would make the sum divisible by 3.

Now let's make some general observations. Looking at the terms modulo 3 and ignoring the multiples of 3 we note that the sequence cannot start (1 2) or (2 1). It must therefore start (1 1) or (2 2). Note that the number of terms congruent to 1 (mod 3) can never equal the number of terms congruent to 2 (mod 3) at any point in the list. As a result, after the sequence begins (1 1) or (2 2) it must alternate 1, 2, 1, 2, and so on. However, observe that a sequence beginning 2, 2, 1, 2, ... would run out of 2's since the sequence always has more 2's than 1's, but we have more 1's to place than 2's. Thus the sequence must have the form 1, 1, 2, 1, 2, 1, ... , 1, 2.

Now that we have determined the nature of the successful sequences we can count the successful lists. There are (k+1)! ways to order the 1's and there are k! ways to order the 2's. Now we can insert the multiples of 3. First we will count the number of slots (out of the 3k+1) in which they can be placed and then we will count the number of permutations of these multiples of 3 once the slots are determined. There are (3kCk) ways to pick the slots (the restriction here is that a multiple of 3 cannot go in the first slot). Then, there are k! ways to permute that multiples of 3. This brings our final count of successful sequences to

(k+1)! k! (3kCk) k!.

The total number of possible sequences is (3k+1)!. Our probability is

(k+1)! k! (3kCk) k! / (3k+1)!

= (k+1)! k! k! (3k)! / [(3k+1)! k! (2k)!]

= (k+1)! k! / [(3k+1) (2k)!].

At first I found the question somewhat confusing. I think that it means if you list the natural numbers1, 2, 3, . . . ,3k+1 what proportion of the partial sums would not be divisible by three.

If this is the case then we see that

P(0) = 1, P(1) = 2/4, P(2) = 3/7, P(4) = 4/10, etc

and the probability or proportion is just (k+1)/(3k+1).

Surely it's not that simple. What have I missed?

Edit. Ah! Do you mean that you do not write down the numbers in numerical order? Well, I don't think that the question made that clear at all. Well written questions should contain no possiblity of ambiguity.