1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Does noticing that $|N(2)| = |N(1)| + 1$ help? This excludes some cases for you. $\endgroup$ – miradulo Aug 13 '15 at 23:33
  • $\begingroup$ Wait, are the numbers all from the set $\{1901,1902\dots 2000\}$? $\endgroup$ – Jorge Fernández-Hidalgo Aug 13 '15 at 23:40
  • $\begingroup$ Yes. Each integer appears as exactly one $a_i$ in the permutation, as your solution assumes. $\endgroup$ – Marconius Aug 13 '15 at 23:45
  • $\begingroup$ Yeah, thanks. Although in the first version I had assumed the numbers where $1,2,3\dots 100$. $\endgroup$ – Jorge Fernández-Hidalgo Aug 13 '15 at 23:46
  • $\begingroup$ @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. $\endgroup$ – Marconius Aug 13 '15 at 23:53
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is incorrect, well, sort of. At least based on the start of his solution's assumption :P $\endgroup$ – miradulo Aug 13 '15 at 23:41
  • $\begingroup$ 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? $\endgroup$ – Jorge Fernández-Hidalgo Aug 13 '15 at 23:43
  • 1
    $\begingroup$ Thanks. Of course, there are 99 positions in which the 33 multiples can be placed. $\endgroup$ – Marconius Aug 13 '15 at 23:45
  • 1
    $\begingroup$ @dREaM Nope! Looks good to me :) $\endgroup$ – miradulo Aug 14 '15 at 0:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.