CGMO 2010 Problem 7

For given integer $n \geq 3$ , set $S =\{p_1, p_2, \cdots, p_m\}$ consists of permutations $p_i$ of $(1, 2, \cdots, n)$ . Suppose that among every three distinct numbers in $\{1, 2, \cdots, n\}$ , one of these number does not lie in between the other two numbers in every permutations $p_i$ ( $1 \leq i \leq m$ ). (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$ .) Determine the maximum value of $m$ .