An odd integer $ n \ge 3$ is said to be nice if and only if there is at least one permutation $ a_{1}, \cdots, a_{n}$ of $ 1, \cdots, n$ such that the $ n$ sums $ a_{1} - a_{2} + a_{3} - \cdots - a_{n - 1} + a_{n}$, $ a_{2} - a_{3} + a_{3} - \cdots - a_{n} + a_{1}$, $ a_{3} - a_{4} + a_{5} - \cdots - a_{1} + a_{2}$, $ \cdots$, $ a_{n} - a_{1} + a_{2} - \cdots - a_{n - 2} + a_{n - 1}$ are all positive. Determine the set of all `nice' integers.
Problem
Source:
Tags: modular arithmetic, IMO Shortlist
07.06.2009 02:07
I think there is a small typo and $ a_{2} - a_{3} + a_{3} - \cdots - a_{n} + a_{1}$ is really meant to be $ a_{2} - a_{3} + a_{4} - \cdots - a_{n} + a_{1}$. Suppose that $ n$ is nice and let $ A = (a_1, \ldots, a_n)$ be a witness to the niceness of $ n$. Any cyclic permutation of $ A$ is a witness, as well, so we may assume that $ a_1 = 1$. Then we have that $ a_1 - a_2 + a_3 - \ldots - a_{n - 1} + a_n = 1 + (a_3 + a_5 + \ldots) - (a_2 + a_4 + \ldots)$ and $ a_2 - a_3 + a_4 - \ldots - a_n + a_1 = 1 + (a_2 + a_4 + \ldots) - (a_3 - a_5 - \ldots)$ are both positive, so in fact $ a_2 + a_4 + \ldots = a_3 + a_5 + \ldots$. This implies that $ 1 + 2 + \ldots + a_n = 1 + a_2 + a_3 + a_4 + a_5 + \ldots + a_n = 1 + 2(a_2 + a_4 + \ldots)$ is odd and so $ n \equiv 1 \pmod 4$. To finish the problem, it suffices to construct a permutation of the desired sort for these $ n$, but unfortunately I haven't managed to do this yet .
07.06.2009 07:31
Construction:$ (a_1,...a_n) = (1,3,5,...,4k + 1,4k,4k - 2,...,2)$ Easily to check this permutation verify all of conditions