28th CanMO 1996 Problem 3 Let N be the number of permutations of 1, 2, 3, ... , 1996 in which 1 is fixed and each number differs from its neighbours by at most 2. Is N divisible by 3?
Let the number of permutations of 1, 2, ... , n with 1 fixed and each number differing from its neighbours by at most 2 be p(n). The first number must be 1, so the second number must be 2 or 3. If the second number is 2, then the number of permutations of 2, 3, ... , n with 2 fixed and each number differing from its neighbours by at most 2 is p(n-1). If the second number is 3, then the third number is 2, 4 or 5. If it is 2, then the fourth number must be 4. In that case, the number of permutations of 4, 5, ... , n with 4 fixed etc is p(n-3). So suppose it is not 2. If we get two adjacent numbers (m m+1 or m m-1) then either all following numbers are greater or all following numbers are less. In the sequence 1, 3, ... we have missed out a smaller number, namely 2, so after the first even number we must go back to it. Hence after the first even number we cannot have any larger numbers. In other words, the only possibility for 1, 3, (not 2), ... is all the odd numbers in increasing sequence followed by all the even numbers in decreasing sequence, eg 1, 3, 5, 7, 9, 8, 6, 4, 2. Thus we have established that p(n) = p(n-1) + p(n-3) + 1. Checking the first few values, we find p(1) = 1, p(2) = 1, p(3) = 2, p(4) = 4, p(5) = 6, p(6) = 9. So mod 3, we have: n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 p(n) 1 1 2 1 0 0 2 0 1 1 2 1 0 0 2 0 1 So there is a cycle of length 8. 1996 = 4 mod 8, so p(1996) = p(4) = 1 mod 3. 28th CanMO 1996 © John Scholes jscholes@kalva.demon.co.uk 15 June 2002