- Use strong induction.
- Go from $m$ to $2m$ and $m,m+1$ to $2m+1$.
- An odd and an even integer do not have an integer average.
We will prove this using strong induction.
Let the permutation of $\{1,2,3,...,n\}$ for which the condition is satisfied be $h_n$
Base case:
$h_1 = \{1\}$
$h_2 = \{1,2\}$
Inductive step:
Given that $h_k$ exists for all $k<n$, prove that $h_n$ also exists.
Case 1:
$n$ is even. Let $n=2m$
Now, if $h_m = \{a_1,a_2,a_3,...,a_m\}$, then we construct $h_n$ as:
$h_n =\{b_1,b_2,b_3,...,b_n\}= \{2a_1,2a_2,2a_3,...,2a_m,2a_1-1,2a_2-1,...,2a_m-1\}$
To show that this works, we can use contradiction.
Clearly all numbers from 1 to $n$ is in $h_n$ because all numbers from 1 to $m$ is in $h_m$ and $h_n$ is a result of $h_m$.
Now, the average of $b_i,b_j$ is not an integer if $i,j$ are in different halves.
The first half is a scaled version of $h_m$. So, if $b_k$ is the average of $b_i,b_j$, then $a_k$ is the average of $a_i,a_j$ and so, $k$ is not between $i,j$.
The second half is just a shifted version of the first half. So, for $b_{m+i},b_{m+j}$ in the second half, their average is $b_{m+k}$ with $k$ not between $i,j$.
Case 2:
$n$ is odd. Let $n=2m+1$
Now, if $h_m = \{a_1,a_2,a_3,...,a_m\}$ and $h_{m+1}=\{c_1,c_2,c_3,...c_{m+1}\}$, then we construct $h_n$ as:
$h_n =\{b_1,b_2,b_3,...,b_n\}= \{2a_1,2a_2,...,2a_m,2c_1-1,2c_2-1,...,2c_m-1,2c_{m+1}-1\}$
There are 2 steps to prove that this construction works.
As before, clearly all numbers from 1 to $n$ is in $h_n$ because all numbers from 1 to $m$ is in $h_m$ (same for $h_{m+1}$) and $h_n$ is a result of $h_m, h_{m+1}$.
Now, the average of $b_i,b_j$ is not an integer if $i,j$ are in different halves.
The first half is a scaled version of $h_m$. So, if $b_k$ is the average of $b_i,b_j$, then $a_k$ is the average of $a_i,a_j$ and so, $k$ is not between $i,j$.
The second half is just a shifted version of the scaled version of $h_{m+1}$. So, for $b_{m+i},b_{m+j}$ in the second half, their average is $b_{m+k}$ with $k$ not between $i,j$.