Proof by induction that you can order natural numbers where the average isn't between any pair of numbers Consider a list of natural numbers like 
$$1, 2, 3, \dots, n$$
Prove using strong induction that you can order the list for any Natural n, in a way where if you pick any pair of numbers, the average of the numbers you choosed isn't between the numbers you choosed, consider the example
$$1, 3, 2$$
Where $1, 2, 3$ is not an acceptable list since the average of $1$ and $3$ is $2$, who is between $1$ and $3$.
Until now I have found that first you may separate the odd numbers, let them in the beginning or the end of the list, then separate from the sublist of odd numbers, the numbers who has odd index, and then make that again recursively with the sublist you create, this because the average of an odd with odd index with an odd with pair index is pair, and pairs are in the list of pairs you separated at the beginng

The method you mentioned is for all intents and purposes a complete solution. Here is way to write it as a proof by strong induction.
The base case $n=1$ is obvious.
For any $n>1$, $d=\lceil n/2\rceil$ and let $e=\lfloor n/2\rfloor$. Note $d,e<n$. Also, $d$ is the number of odd numbers in $\{1,2,\dots,n\}$, while $e$ is the number of even numbers.
By induction, the sets $\{1,2,\dots,d\}$ and $\{1,2,\dots,e\}$ can be ordered so no two numbers surround their average. Let these orderings be $(a_i)_{i=1}^{d}$ and $(b_i)_{i=1}^{e}$. Now, consider the list
$$
(2a_1-1,2a_2-1,\dots,2a_{d}-1,2b_1,2b_2,\dots,2b_{e})
$$
You can show that this contains every number in $\{1,2,\dots,n\}$ exactly once, and the average property still holds.
