Here is a problem I am trying to do ..

Show that it is possible to arrange the numbers 1, 2, . . . , n
in a row so that the average of any two of these numbers
never appears between them.

Here is my attempt. The base case will consist of first two numbers.

Base Case: $\displaystyle n=2$

The arrangment 1,2 doesn't have average of 1 and 2 between them.
So this proves $\displaystyle P(2)$

Induction case: Let $\displaystyle n\geqslant 2$ be arbitrary.
Suppose $\displaystyle P(n)$. To prove $\displaystyle P(n+1)$,
consider numbers $\displaystyle 1,2,\cdots,n,n+1$

Now I am negating the goal and seeking the contradiction.
So assume that with any configuration of these $\displaystyle n+1$
numbers, there always is at least a pair of numbers such that
their average is between them. Now due to the inductive hypothesis,
we know that for first $\displaystyle n$ numbers, there is a configuration
such that for any pair of numbers, their average is not between them.
So lets put these $\displaystyle n$ numbers in that particular
configuration. And now put $\displaystyle n+1$ at the end of this
list. But due to our assumption, for the list of all these
numbers (including $\displaystyle n+1$), there is no desired
configuration possible. So there must exist a number
$\displaystyle 1\leqslant i < n $ such that the average of $\displaystyle i$
and $\displaystyle n+1$ is between these two numbers. That average

$\displaystyle \frac{n+1+i}{2}$

Now after this point I don't know how to seek the contradiction.
Any hints will be helpful. There is one hint given in the problem.

Hint: Show that it suffices to prove this fact when n
is a power of 2. Then use mathematical induction to
prove the result when n is a power of 2.

But I dont know how to use it, so I started with another approach.