A permutation of the integers $1901,1902\dots 2000$ is a sequence in which each of those integers appears exactly once. Given such a permutation, we form the sequence of partial sums
$$s_1 = a_1,\;\;s_2 = a_1 + a_2,\;\;s_3 = a_1 + a_2 + a_3, \; \ldots\;, \; s_{100} = a_1 + a_2 + \cdots + a_{100}. $$ How many of these permutations will have no terms of the sequence divisible by three?
This problem is taken from the 2000 Canada National Olympiad.
Ignoring numbers divisible by $3$, in modulo $3$ the sequence must follow one of the following two patterns in order to skip all threes:
- $1,1,2,1,2,\ldots$
- $2,2,1,2,1,\ldots$
Doing a count of the various residues modulo $3$ in the set $\{1901,1902,1903,\ldots,2000\}$, we have:
$$N(0)=N(1)=33;N(2)=34$$
Hence, our sequence of non-zero residues must be $$2,2,1,\ldots,2,1 \tag{1}$$ There must be no numbers divisible by $3$ to the left of the first term in (1).
The number of independent ways of permuting the numbers in all residue classes is given by $$33!\,33!\,34!$$ but I am unsure of how to count the number of distinct patterns given by (1) once residue $0$ terms are admitted.