Mathematical induction problem

[pc2-brazil]

Homework Statement

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. [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.]

Homework Equations

The Attempt at a Solution

I'm using the following scheme to arrange the numbers: everytime a new number (n) is added to the list, I first put it at the end of the list. Then, I look for a previous number (m) to see whether (n+m)/2 is between n and m; if it is, then I put n before (n+m)/2.

For n = 2:
1, 2
For n = 3:
(3 + 1)/2 = 2; therefore, I put 3 before 2:
1, 3, 2
For n = 4:
4 can be put in the end of the list.
1, 3, 2, 4
For n = 5:
(5 + 1)/2 = 3; therefore, I put 5 before 3.
1, 5, 3, 2, 4
For n = 6: 1, 5, 3, 2, 6, 4
For n = 7: 1, 5, 3, 2, 7, 6, 4
For n = 8: 1, 5, 3, 2, 7, 6, 4, 8
For n = 9: 1, 9, 5, 3, 2, 7, 6, 4, 8
For n = 10: 1, 9, 5, 3, 2, 7, 10, 6, 4, 8
And so on.

I don't see any useful patterns here. I'm not sure why it only has to be proven when n is a power of two. The only pattern I see here is that the greatest power of two can always be put at the end of the list (in this case, until n = 3, 2 is at the end of the list; from n = 4 to n = 7, 4 is at the end of the list; starting from n = 8, 8 remains at the end of the list; and so on), but I don't know if this is helpful.
Any ideas?

Thank you in advance.

 

[Dick]

If you have n numbers then there is a k such that 2^k is greater then n. Remove the numbers you don't need from the list of 2^k numbers. And I do see a trend in your lists, the odd numbers and the even numbers are tending to fall into two different groups. Can you think of a way to order the evens and odds separately to do the induction?