Canadian Mathematics Olympiad

Solution:

Let $\{1901, 1902, \ldots, 2000\} = R_{0} \cup R_{1} \cup R_{2}$ where each integer in $R_{i}$ is congruent to $i$ modulo $3$. We note that $|R_{0}| = |R_{1}| = 33$ and $|R_{2}| = 34$. Each permutation $S = (a_{1}, a_{2}, \ldots, a_{100})$ can be uniquely specified by describing a sequence $S' = (a_{1}', a_{2}', \ldots, a_{100}')$ of residues modulo $3$ (containing exactly $33$ zeros, $33$ ones and $34$ twos), and three permutations (one each of $R_{0}, R_{1}$, and $R_{2}$). Note that the number of permutations of $R_{i}$ is exactly $|R_{i}|! = 1 \cdot 2 \cdots |R_{i}|$.

The condition on the partial sums of $S$ depends only on the sequence of residues $S'$. In order to avoid a partial sum divisible by three, the subsequence formed by the $67$ ones and twos in $S'$ must equal either $1, 1, 2, 1, 2, \ldots, 1, 2$ or $2, 2, 1, 2, 1, \ldots, 2, 1$. Since $|R_{2}| = |R_{1}| + 1$, only the second pattern is possible. The $33$ zero entries in $S'$ may appear anywhere among $a_{1}', a_{2}', \ldots, a_{100}'$ provided that $a_{1}' \neq 0$. There are $\binom{99}{33} = \frac{99!}{33!\,66!}$ ways to choose which entries in $S'$ equal zero. Thus there are exactly $\binom{99}{33}$ sequences $S'$ whose partial sums are not divisible by three. Therefore the total number of permutations $S$ satisfying this requirement is exactly
$$\binom{99}{33} \cdot 33! \cdot 33! \cdot 34! = \frac{99! \cdot 33! \cdot 34!}{66!}.$$
Incidentally, this number equals approximately $4.4 \times 10^{138}$.