# Permutations where no partial sum is divisible by 3 (contest 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?

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.

• Does noticing that $|N(2)| = |N(1)| + 1$ help? This excludes some cases for you. – miradulo Aug 13 '15 at 23:33
• Wait, are the numbers all from the set $\{1901,1902\dots 2000\}$? – Jorge Fernández-Hidalgo Aug 13 '15 at 23:40
• Yes. Each integer appears as exactly one $a_i$ in the permutation, as your solution assumes. – Marconius Aug 13 '15 at 23:45
• Yeah, thanks. Although in the first version I had assumed the numbers where $1,2,3\dots 100$. – Jorge Fernández-Hidalgo Aug 13 '15 at 23:46
• @dREaM - My apologies. I don't know how the $1901,1902,\ldots,2000$ was lost. It was certainly in the original document I pasted from. – Marconius Aug 13 '15 at 23:53

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.

• This is incorrect, well, sort of. At least based on the start of his solution's assumption :P – miradulo Aug 13 '15 at 23:41
• yeah, He hadn't said the numbers are $1901,1902\dots 2000$. I took them to be $1,2\dots 100$. I changed it accordingly. Or did you mean something else is wrong? – Jorge Fernández-Hidalgo Aug 13 '15 at 23:43
• Thanks. Of course, there are 99 positions in which the 33 multiples can be placed. – Marconius Aug 13 '15 at 23:45
• @dREaM Nope! Looks good to me :) – miradulo Aug 14 '15 at 0:07