IMO 1991 SL 24

Origin: IND

Problem

An odd integer n \geq3 is said to be “nice” if there is at least one permutation a1, a2, . . . , an of 1, 2, . . ., n such that the n sums a1 −a2 + a3 −\cdot \cdot \cdot −an−1 + an, a2 −a3 + a4 −\cdot \cdot \cdot −an + a1, a3 −a4 + a5 −\cdot \cdot \cdot −a1 + a2, . . . , an −a1 + a2 −\cdot \cdot \cdot −an−2 + an−1 are all positive. Determine the set of all “nice” integers.

Solution

Let yk = ak −ak+1 + ak+2 −\cdot \cdot \cdot + ak+n−1 for k = 1, 2, . . ., n, where we define xi+n = xi for 1 \leqi \leqn. We then have y1 + y2 = 2a1, y2 + y3 = 2a2, . . . , yn + y1 = 2an.

(i) Let n = 4k−1 for some integer k > 0. Then for each i = 1, 2, . . ., n we have that yi = (ai +ai+1+\cdot \cdot \cdot+ai−1)−2(ai+1+ai+3+\cdot \cdot \cdot+ai−2)=1+ 2 + \cdot \cdot \cdot + (4k −1) −2(ai+1 + ai+3 + \cdot \cdot \cdot + ai−2) is even. Suppose now that a1, . . . , an is a good permutation. Then each yi is positive and even, so yi \geq2. But for some t \in{1, . . . , n} we must have at = 1, and thus yt + yt+1 = 2at = 2 which is impossible. Hence the numbers n = 4k −1 are not good. (ii) Let n = 4k + 1 for some integer k > 0. Then 2, 4, . . ., 4k, 4k + 1, 4k − 1, . . . , 3, 1 is a permutation with the desired property. Indeed, in this case y1 = y4k+1 = 1, y2 = y4k = 3, . . . , y2k = y2k+2 = 4k −1, y2k+1 = 4k + 1. Therefore all nice numbers are given by 4k + 1, k \inN.