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}), \quad 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, \ldots, 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, \ldots, 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. $□$