China Girls' Mathematical Olympiad

The answer is $2^{n-1}$.

We first show that $m\le 2^{n-1}$. We induct on $n$. The base case $n=3$ is trivial. (Indeed, say $3$ does not lie in between $1$ and $2$, then we can have $S=\{(1,2,3),(3,1,2),(2,1,3),(3,2,1)\}$.) Assume that the statement is true for $n=k$ (where $k\ge 3$). Now consider $n=k+1$ and a set $S_{k+1}$ satisfies the conditions of the problem. Note that if the element $k+1$ is deleted from each permutation $p_i$ in $S_{k+1}$, the resulting permutations $q_i$ form a set $S_k$ that satisfies the conditions of the problem (for $n=k$). It suffices to show the following claim: there are at most two distinct permutations $p$ and $q$ in $S_{k+1}$ that can map to the same permutation $r$ in $S_k$ (by deleting the element $k+1$ in the permutations $p$ and $q$).

Indeed, assume that for $$p_1=(x_1,x_2,\dots ,x_{k+1}),p_2=(y_1,y_2,\dots ,y_{k+1}),p_3=(z_1,z_2,\dots ,z_{k+1})$$ in $S_{k+1}$, $q_1=q_2=q_3=q$. By symmetry, we may assume that $q=(1,2,\dots ,k)$. Assume that $x_a=y_b=z_c=k+1$. Again by symmetry, we may assume that $1\le a<b<c\le k+1$. (Note that because $q_1=q_2=q_3=q$, $a,b,c$ are distinct.) We consider three numbers $a,b,k+1$. We have $p_1=(\dots ,k+1,a,\dots ,b,\dots )$ (in particular, $a$ lies in between $k+1$ and $b$), $p_2=(\dots ,a,\dots ,k+1,b,\dots )$ (in particular, $k+1$ lies in between $a$ and $b$), and $p_3=(\dots ,a,\dots ,b,\dots ,k+1,\dots )$ (in particular, $b$ lies in between $a$ and $k+1$). Hence each one of the numbers $a,b,k+1$ lie in between the other two numbers in some permutations in $S_k$, violating the conditions of $S_k$. Thus our assumption was wrong and at most two elements in $S_{k+1}$ can be mapped to an element in $S_k$, establishing our claim.

It remains to be shown that $m=2^{n-1}$ is achievable. We construct permutation $p$ inductively: (1) place $1$; (2) after numbers $1,2,\dots ,l$ are placed, we place $l+1$ either to the left or the right of all the numbers placed so far. Because there are two possible places for each of the numbers $2,3,\dots ,n$, we can construct $2^{n-1}$ such permutations. For any three numbers $1\le a<b<c\le n$, $c$ does not lie in between $a$ and $b$. Hence, this set of $2^{n-1}$ permutations satisfies the conditions of the problem, completing our proof. $\square$