Question 139
Let $n$ be an integer greater than or equal to $3$. For a permutation $p = (x_1, x_2, \dots, x_n)$ of $(1, 2, \dots, n)$, we say that $x_j$ lies in between $x_i$ and $x_k$ if $i \lt j \lt k$. (For example, in the permutation $(1, 3, 2, 4)$, $3$ lies in between $1$ and $4$, and $4$ does not lie in between $1$ and $2$.) Set $S = \{p_1, p_2, \dots, p_m\}$ consists of (distinct) permutations $p_i$ of $(1, 2, \dots, n)$. Suppose that among every three distinct numbers in $\{1, 2, \dots, n\}$, one of these numbers does not lie in between the other two numbers in every permutation $p_i \in S$. Determine the maximum value of $m$.