Arrangement of Numbers

How can we prove that it is posible to arrange numbers $1,2,3,4,\ldots, n$ in a row so that the average of any two of these numbers never appears between them?

Assume the inductive hypothesis that it is true for lists smaller than $n$. To reorder $1 \ldots n$ this way as well, split it into evens and odds, and apply the function $\left \lceil{(x+1)/2}\right \rceil $ to these sets to create two half-problems of the same type which by the hypothesis can be solved. Now unapply the transformation to each half-solution using the function $2x$ to recover the evens and the function $2x-1$ to recover the odds. These functions are linear so the condition is still satisfied. Now concatenate these two lists together to form the solution. This concatenation always works because the average of an even and an odd is not an integer.