Probably faulty because this seems too simple to be true We proceed with induction. The base case $n=3$ can be achieved whenever $f(2)=\min(f(1),f(2),f(3))$. For the inductive step, re-interpret the problem as that we are to insert the greatest element $m$ of $S$ into a permutation $\{f_i\}$ of all $n-1$ elements of $S$ (that abides the problem's constraints) with $f(i)=f_i$. For each pair $(a,b)$ in the permutation such that $a+m=2b$, mark $b$ with an arrow pointing against $a$; we desire to find a location of $m$ such that $m$ is not swept through by any arrows. If there exist no arrows then we are done. If every arrow points in the same direction (WLOG let them all be pointing left), pick the rightmost spot and we are also done. If any two consecutive arrows point against each other ($\leftarrow \rightarrow$), insert m between them. Otherwise, if we only have a single (more such pairs would also require $\leftarrow \rightarrow$ pairs to exist) $\rightarrow \leftarrow$ pair, the leftmost arrow is pointing towards the right, and the rightmost arrow is pointing towards the left so we can insert m into either the leftmost or the rightmost position. @below I don't really know how arrows can overlap since the b's are distinct?

What do you mean by "consecutive arrows"? Arrows can overlap. I remember solving this by Cauchy induction (i.e., induction steps from $n$ to $2n$ and from $n$ to $n-1$) long ago. This was a BWM (German national math olympiad) problem back in my days (ca. 2000-2005). Not sure I can still find that thread... In its original(?) statement, it asks to prove that the numbers $1, 2, \ldots, n$ can be ordered in such a way that no two numbers have their average appear between them. [EDIT: Found it! https://artofproblemsolving.com/community/c6h14758p106702 ] Alternatively, you can order the integers $1, 2, \ldots, n$ by their reverse binary representation. The reverse binary representation of a positive integer $k$ is defined to be the binary (i.e., base-$2$) representation of $k$, written backwards (i.e., with the least bit first). (For example, the integer $19$ has binary representation $\left(1,0,0,1,1\right)$ and thus has reverse binary representation $\left(1,1,0,0,1\right)$.) Reverse binary representations are tuples and thus can be compared in the lexicographic order (where $\left(a_1, a_2, \ldots, a_k\right) < \left(a_1, a_2, \ldots, a_m\right)$ for $k < m$). Now, order the $n$ integers $1, 2, \ldots, n$ in the order of (lexicographically) increasing reverse binary representations. It is a fun exercise to show that this ordering satisfies your condition (i.e., that no two numbers have their average appear between them).