National Math Olympiad in Slovenia

Let us show that the statement is true for any $n \in \mathbb{N}$. We claim that the numbers $1, 2, \dots, n$ can be lined up so that for any pair their arithmetic mean does not lie somewhere in between.

First, we will show that this is true for $n = 2^m$ for all $m \in \mathbb{N}$. We will use induction on $m$.

In the base case $m = 1$ this is obvious.

Now, let us assume that for some $m$ the numbers $1, 2, \dots, 2^m$ can be arranged into the sequence
$(a_1, a_2, \dots, a_{2^m})$ so that for any pair their arithmetic mean does not lie in between the two numbers.

We notice that the sequence
$$(b_1, b_2, \dots, b_{2^{m+1}}) = (2a_1 - 1, 2a_2 - 1, \dots, 2a_{2^m} - 1, 2a_1, 2a_2, \dots, 2a_{2^m})$$
is a permutation of $1, 2, \dots, 2^{m+1}$ which satisfies the condition of the problem. Indeed, by the induction hypothesis the arithmetic mean of $b_i$ and $b_j$, where either $1 \le i < j \le 2^m$ or $2^m + 1 \le i < j \le 2^{m+1}$, does not lie in between them and if $1 \le i \le 2^m < j \le 2^{m+1}$, then the arithmetic mean of $b_i$ and $b_j$ is not an integer at all. We have thus proven the statement for $n = 2^m$.

Finally, if the positive integer $n$ is not a power of $2$, then there exists $m \in \mathbb{N}$ such that $n < 2^m$. In this case we can first arrange the numbers $1, 2, \dots, 2^m$ into the sequence that satisfies the condition and then simply remove any numbers greater than $n$. The new sequence obtained in this way will obviously still satisfy the condition.