Maximize the minimum absolute value of the differences of three permutation sequences I have been plagued by this problem for a long time:
there are three permutation sequences with the same length N, denoted as x1, x2, and x3. For example, if N=5, x1, x2, x3 can be [1 2 3 4 5], [5 3 1 2 4] and [3 2 1 4 5].
We calculate the absolute values of differences between any two sequences, that is min{|x1-x2|}=1, min{|x1-x3|}=0, min{|x2-x3|}=0. Therefore, the minimum absolute value of the differences of the three permutation sequences is 0. However, when we change the orders of numbers in x1, x2 and x3 as [1 2 3 4 5], [3 4 5 1 2] and [5 1 2 3 4], the minimum absolute value of the differences of three permutation sequences will be 1.
Now, We want to find some x1, x2, and x3, to make the minimum absolute value of the differences maximize. It is so difficult to make an exhaustive search. Does anyone have any ideas about this issue?
 A: It seems to me that [1,2,3, ... , N] with two cyclic permutations would always retrieve the maximal minimum absolute value (MAV) of $\left \lfloor{\frac{N}{3}}\right \rfloor$ (the result of rounding N/3 down). I'll give a short sketch for how I would prove this.

First, we want to prove that there is no set of three permutations which would result in a MAV greater than $\bf k = \left \lfloor{\frac{N}{3}}\right \rfloor$. Without loss of generality, assume the first permuation is $[1,2,3, ... , N]$. Let $[x_1,x_2,x_3, ... , x_N]$ and $[y_1,y_2,y_3, ... , y_N]$ be the two other permutations. Consider the MAV for just the $k$ and $k+1$ elements of this set of three permutations.
$$
\begin{bmatrix} 1 \\ 2 \\ 3 \\ \vdots \\ k \\ k+1 \\ \vdots \\ N \end{bmatrix} \quad \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_k \\ x_{k+1} \\ \vdots \\ x_N \end{bmatrix} \quad \begin{bmatrix} y_1 \\ y_2 \\ y_3 \\ \vdots \\ y_k \\ y_{k+1} \\ \vdots \\ y_N \end{bmatrix}
$$
This is two "rows" of the permutations. The MAV for this set of three permutations must be less than or equal to the MAV of just these two rows. However, $x_k, x_{k+1}, y_k, y_{k+1} \in \{1,2,3, ..., N\}$ so (and there is some hand-waving here) the MAV of these two rows is $k$, corresponding to $[k,2k,3k]$ (for $N=3k$ or $N=3k+1$) or $[k+1,2k+1,3k+2]$ (for $N=3k+2$).
Because the MAV of these two rows is $k$, the MAV of this set of three permutations must be less than or equal to $k$. The choice of $[1,2,3, ... , N]$ for the first permutation was arbitrary (we can apply any permutation to each of the three permutations) so this is a general result. Thus, the maximal MAV must be less than or equal to $k$.

Second, we need to prove that the maximal MAV is greater than or equal to $k$. We can simply give one example of a set of three permutations that has an MAV equal to $k$. I will only give an example for $N=3k+2$:
$$
\begin{bmatrix} 1 \\ \vdots \\ k \\ k+1 \\ \vdots \\ 2k \\ 2k+1 \\ \vdots \\ 3k \\ 3k+1 \\ 3k+2 \end{bmatrix} \quad \begin{bmatrix} 2k+3 \\ \vdots \\ 3k+2 \\ 1 \\ \vdots \\ k \\ k+1 \\ \vdots \\ 2k \\ 2k+1 \\ 2k+2 \end{bmatrix} \quad \begin{bmatrix} k+3 \\ \vdots \\ 2k+2 \\ 2k+3 \\ \vdots \\ 3k+2 \\ 1 \\ \vdots \\ k \\ k+1 \\ k+2 \end{bmatrix}
$$
In each row, pairs have a difference of either $k$ or $k+2$. Thus, each row has a MAV of at least $k$. The last row will always have an MAV of $k$ and so the MAV of this set of three permutations is $k$.

By showing that the maximal MAV $\leq k$ and also that the maximal MAV $\geq k$, we prove that the maximal MAV $= k$.
