# Integer sequence, probability?

In celebration of my one year anniversary here at Answers, I thought I would put up my first question(s). This one comes from the 2007 Putnam competition (no cheating!). I had a pretty good idea where to start, but couldn't finish it up. One of the other test-takers from my university did manage to finish... show more In celebration of my one year anniversary here at Answers, I thought I would put up my first question(s). This one comes from the 2007 Putnam competition (no cheating!). I had a pretty good idea where to start, but couldn't finish it up. One of the other test-takers from my university did manage to finish it.

Suppose you write down the numbers 1, 2, ..., 3k+1. What is the probability that the sum of your partial list is never divisible by 3, at any time in the process? (That is, with each new number you write down, the sum of your list is never divisible by 3.)

Cheers!
Update: Unrelated, but my TC badge is back!
My avatar was lonely without it.
:)
Update 2: cheeser, you make things too easy :P Actually though, you have a slight mistake... And to mathsman, yes, I should have made it clear that we're not necessarily writing these in order. Having worked on the problem I have a tendency to make certain assumptions based on what I've done. However, I'll... show more cheeser, you make things too easy :P
Actually though, you have a slight mistake...

And to mathsman, yes, I should have made it clear that we're not necessarily writing these in order. Having worked on the problem I have a tendency to make certain assumptions based on what I've done. However, I'll mention (solely to make myself feel better) that the Putnam competition frequently has ambiguities itself (for instance, in this 2007 exam, question B1 makes an unstated assumption that the polynomial is non-constant).
Update 3: Okay, this question seems to have been more ambiguous than I had supposed. The idea is to randomly write down, one at a time, the numbers of {1, ..., 3k+1}. After each number I write down, I check to see if the sum of my partial list is divisible by 3. Then what is the probability that at no point during my... show more Okay, this question seems to have been more ambiguous than I had supposed. The idea is to randomly write down, one at a time, the numbers of {1, ..., 3k+1}. After each number I write down, I check to see if the sum of my partial list is divisible by 3. Then what is the probability that at no point during my writing process is the list divisible by 3.

For example, k=1: {1, 2, 3, 4}. There are 4!=24 possible listings of the numbers. The only ones that fit my criteria are
1, 3, 4, 2
1, 4, 2, 3
1, 4, 3, 2
4, 1, 2, 3
4, 1, 3, 2
4, 3, 1, 2
for a probability of 6/24=1/4.
Update 4: Hmm...do I choose the person who's seen the question before, solved it under pressure, and given a somewhat vague solution; or the person who hasn't seen the question, solved it under no particular pressure, but explained things more fully? I will mention that I feel that counting the ways of placing the... show more Hmm...do I choose the person who's seen the question before, solved it under pressure, and given a somewhat vague solution; or the person who hasn't seen the question, solved it under no particular pressure, but explained things more fully?

I will mention that I feel that counting the ways of placing the 0's seems perfectly fine, and was my natural instinct (as opposed to multiplying by the separate probability of not having a 0 at the beginning).

Anyway, I can't bring myself to decide, so I'll send it to a vote.