32nd CanMO 2000 Problem 2 How many permutations of 1901, 1902, 1903, ... , 2000 are such that none of the sums of the first n permuted numbers is divisible by 3 (for n = 1, 2, 3, ... , 2000)?
There are 34 numbers equal to 2 mod 3, and 33 each equal to 0 and 1 mod 3. The multiples of 3 do not affect the values mod 3, so consider the sequence of the other terms. Call terms equal to 1 mod 3, 1- terms and terms equal to 2 mod 3, 2-terms. If we start with a 1-term, then the next term must be a 1- term. The sum is then 2 mod 3, so the next term must be a 2-term, the sum is then 1 mod 3 and so the next term must be a 1-term, and so on. So after the first two terms, we must alternate between 1-terms and 2-terms. Similarly, if we start with a 2-term, the next term must be a 2-term, but then we must alternate. But there are more 2-terms than 1-terms, so we cannot start with a 1-term. Thus (ignoring the terms divisible by 3), the sequence must be 2-term, 2-term, 1-term, 2-term, 1-term, ... , 2-term, 1-term. Thus we may start by placing the terms divisible by 3 in any positions except the first. That gives 99!/66! possibilities. The pattern of 2-terms and 1-terms is then determined and so in each case there are 34! 33! ways or arranging the 2-terms and 1-terms. Thus there are (99! 34! 33!)/66! possibilities in all. 32nd CanMO 2000 © John Scholes jscholes@kalva.demon.co.uk 15 June 2002