32nd IMO shortlist 1991/24 solution

32nd IMO 1991 shortlist

Problem 24

Find all odd integers n > 1 for which there is at least one permutation a₁, a₂, ... , a_n of 1, 2, 3, ... , n such that the sums
a₁ - a₂ + a₃ - ... + a_n,
a₂ - a₃ + a₄ - ... - a_n + a₁,
a₃ - a₄ + ... + a_n - a₁ + a₂,
...
a_n - a₁ + a₂ - ... + a_n-1
are all positive.

Answer

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, 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