Disclaimer: The solutions we've shared are just one exciting approach, and there are surely many other wonderful methods out there. We’d love to hear your alternative solutions in the community thread below, so let's keep the creativity flowing!

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$.