Permutations where no partial sum is divisible by 3 (contest question)

Question

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.

Answer 1

First choose the positions for the multiples of $3$, the multiples of $3$ can be placed anywhere we want and they do not affect anything else, all that matters is the first position is not occupied by a multiple of $3$.

So we select the $\binom{99}{33}$ multiples of $3$ and permute them in $33!$ ways.

After this the real problem starts.

We have $34$ numbers that are $2\bmod 3$ and $33$ numbers that are $1\bmod 3$ and we must place them in a line (we can forget about the multiples of $3$).

We start by placing a $1$ or a $2$ (two options).

If we place a $1$ the next must be a $1$, and then a $2$ and then a $1$ and then a $2$ and so on... we get the sequence $1,1,2,1,2,1,2\dots$. This sequence always has more ones than $2$, so when we reach the $67$'th term we will have $34$ ones and $33$ twos, this is impossible.

If we start with a $2$ however, the next must be $2$, then $1$, then $2$ and so on.. so the sequence is $2,2,1,2,1,2\dots$. We must place $33$ ones and $34$ twos, this one is possible.

Hence there is only one way to select the places for the numbers $\bmod 3$.

So the only thing we can choose is how we permute the $1$'s and $2$'s internally. There are $33!\cdot 34!$ ways to do so.

Hence there are $\binom{99}{33}\cdot33!\cdot34!\cdot 33!$ ways in total.