Call a set of permutations good if it satisfies the condition. Let $a_n$ be the maximum possible value of a good set for ${1,2,...,n}$. We show by induction $a_n=2^{n-1}.$ The base case $n=3$ is trivial. Throughout we will treat a permutation as a sequence ${x_1,x_2,...,x_n}$. Now assume $a_n=2^{n-1}. $ Clearly then $a_{n+1}\ge 2a_n$, as we can just add ${n+1}$ to either at the front or the end to each permutation. Now assume for the sake of a contradiction that $a_{n+1}\ge 2a_n+1$; let such a good set be ${p_1,...,p_{2^n+1}}$ (even if $a_{n+1}> 2^{n}+1$, there will definitely be a good set with $2^n+1$ elements). Now look at each $p_i$ without ${n+1}$; clearly these restricted permutations form a good set for ${1,2,...,n}$, and thus by Pigeonhole, at least 3 of the $p_i$, wlog $p_1,p_2,p_3$ are mapped to the same restricted permutation of ${1,2,...,n}$. Since $p_1,p_2,p_3$ are distinct, the places of ${n+1}$ are different; wlog assume that the position of ${n+1}$ in $p_1$ is further left than that of $p_2$, which is further than that of $p_3$. Now suppose in $p_1$, $a$ is to the right of $n+1$, and in $p_2$, $b$ is. Obviously $a.b$ exist and are distinct. Now then look at the triple $n+1,a,b$; it is clear they violate the condition. Hence $a_{n+1}=2^n,$ and the induction is complete.

I cannot understand weather we seek a set of permutations p(i) so there must be a permutation for i E [1;m] so k1 is not between k2 and k3 for k1,k2,k3 E [1;n].Can anyone explain please?