32nd IMO 1991 shortlist Problem 24 Find all odd integers n > 1 for which there is at least one permutation a 1 , a 2 , ... , a n of 1, 2, 3, ... , n such that the sums a 1 - a 2 + a 3 - ... + a n , a 2 - a 3 + a 4 - ... - a n + a 1 , a 3 - a 4 + ... + a n - a 1 + a 2 , ... a n - a 1 + a 2 - ... + a n-1 are all positive.
n = 1 mod 4. Solution As usual take cyclic indices, so that an index of n+1 means 1, an index of n+2 means 2 etc. Put b i = a i - a i+1 + a i+2 - a i+3 + ... + a i-1 . Then b i + b i+1 = 2a i . Suppose n = 4k+1. Then take the permutation 2, 4, 6, 8, ... , 4k, 4k+1, 4k-1, 4k-3, ... , 5, 3, 1. It is easy to check that the sums are 1, 3, 5, 7, ... , 4k+1, 4k+1, 4k-3, 4k-3, 4k-7, 4k-7, ... , 5, 5, 1. (Check the first one: (2 - 4) + (6 - 8) + (10 -12) + ... + (4k-2 - 4k) + (4k+1 - (4k-1)) + ... + (5 - 3) + 1 = 1. Then use the relation above.) So there is a permutation for n = 4k+1 Now suppose we have a permutation which works for n = 4k - 1.Then 1 + 2 + 3 + ... + n = 2k(4k - 1) is even. Hence each y i is even. So if all y i are positive, then all y i are at least 2. But for some i we must have y i + y i+1 = 1. Contradiction. So it is not possible for n = -1 mod 4. [Note that the permutation is not unique, because if a i works, then so does a cyclic permutation of a i . But even if we require a 1 = 1, the permutation is not unique. For example, for n = 5, we have 1, 2, 3, 5, 4 giving 1, 1, 3, 3, 7, and 1, 2, 4, 5, 3 giving 1, 1, 3, 5, 5.] 32nd IMO shortlist 1991 © John Scholes jscholes@kalva.demon.co.uk 2 Jan 2003 Last corrected/updated 2Jan 03