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: n=2

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

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

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


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.