Permutation Distances

Consider parity. Since the parity of $|x-y|$ is the same as $x+y$ , it follows that $S$ must be odd. Since $|x-y| \leq \max(x,y)$ for non-negative numbers, it follows that $S \leq 402$ . Hence, 401 is the maximum number possible.

Then, we note that $||||n-(n-1)|-(n-2)|-(n-3)|$ =0. Thus we have $|||...||401-400|-399|-...-2|-1|-402| \\ =|||...|||0-397|-396|-395|-...-2|-1|-402|=...\\ =||0-1|-402|=401$ .

So 401 is attainable, and we are done.

Let $A_k=\{0,1,\dots ,k\}$ for any $k$ . Set some positive integer $n\equiv 2\pmod 4$ . Let $s_2=|x_1-x_2|$ and $s_{i+1}=|s_{i}-x_{i+1}|$ . Note that if $a,b\in A$ , then $|a-b|\in A$ . Thus $|x_1-x_2|\in A$ , $||x_1-x_2|-x_3|\in A$ ,... it follows by induction on the terms of $S=s_n$ that $S\in A$ . Thus $S\le n$ .

We prove $S\ne n$ . Suppose $S=n$ . Then $\{s_{n-1},x_n=\{0,n\}$ . But $s_{n-1}$ cannot be $n$ , otherwise $x_n=n$ and $\{x_1,x_2,\dots ,x_{n-1}\}=\{1,2,\dots ,n-1\}$ and thus $s_{n-1}\le n-1$ , absurd. Thus $s_{n-1}=0$ . Since $n-1\equiv 1\pmod 4$ , $A_{n-1}$ contains oddly many odd numbers.

Suppose $x_{n-1}$ is even. Then $\{x_1,\dots ,x_{n-2}\}$ contains oddly many odd numbers, and thus $s_{n-2}$ is odd. But $0=s_{n-1}=|s_{n-2}-x_{n-1}|$ and since $x_{n-1}$ is even, $0$ is odd, contradiction. The other case is analogous. Suppose $x_{n-1}$ is odd. Then $\{x_1,\dots ,x_{n-2}\}$ contains evenly many odd numbers, and thus $s_{n-2}$ is even. But $0=s_{n-1}=|s_{n-2}-x_{n-1}|$ and since $x_{n-1}$ is odd, $0$ is odd, contradiction again.

It follows that $S\le n-1$ . We prove that this is achievable. Consider $(x_1,x_2,\dots ,x_n)=(n-1,n-2,\dots ,3,2,1,n)$ . I claim it works. Note that $|||(k+4)-(k+3)|-(k+2)|-(k+1)|=0$ for all $k$ . It follows that in this case $s_{n-2}=0$ (recall $n\equiv 2\pmod 4$ ), which implies $s_{n-1}=1$ and $S=s_n=n-1$ . Since $402\equiv 2\pmod 4$ , we easily find the answer to be $401$ , as desired.

I use the notation $s_i$ for partial results, with $s_1$ = $x_1$ . $s_{i+1} = |s_i-x_{i+1}|$ , so S = $s_{402}$ .

$|y_1-y_2|$ is at least 0 and at most $max(y_1,y_2)$ , so all partial results in the evaluation of S are in [0,402]. The largest number we can possibly achieve is thus 402. This can happen if $|...|x_1 - x_2| - ... - x_{401}| = 0$ .

Consider odd and even numbers. If $y_2$ is even, the result of $|y_1-y_2|$ is odd or even according to whether $y_1$ is odd or even. If $y_2$ is odd, the result of $|y_1-y_2|$ is even or odd according to whether $y_1$ is odd or even. In other words, doing the operation of subtracting $y_2$ and taking the absolute value leaves the parity unchanged if $y_2$ is even and changes it if $y_2$ is odd. The odd numbers in the set are 1, 3, ... 401, which is 201 numbers. The final parity of S is therefore odd, and cannot be 402. It can be 401, however.

Let $x_{402} = 402$ , $x_1 = 1$ , and the other $x_i = 403-i$ . Then $|x_1-x_2| = |1-401| = 400$ . $|400-400| = 0$ . $|0-399| = 1$ . $|1-398| = 397$ . This pattern continues, so that $s_{4j+1} = 1$ for natural numbers j. $S = |s_{401} - 402|$ . 401 is expressible as $4j+1$ , so $s_{401} = 1$ , and therefore S = 401.

I claim that 401 is the largest. Clearly, this is less than or equal to 402, and integral. By a simple parity argument, we have that this is odd, so it must be <= 401. To attain this, we need $x_{402 }= 402$ and $|...|x_1-x_2|-x_3|-...-x_{401}| = 1$ . Lemma: There exists a permutation $x_i$ of {1,2, \cdots 4k+1 such that $|\cdots|x_1-x_2|-\cdots-x_{4k+1}| = 1$ . Proof: Induction. When k = 0, this is obvious. Inductive step. Assume this is true for k = i-1. Then we can just let $x_{4k-2} = 4k+1$ , $x_{4k-1} = 4k$ , $x_{4k} = 4k-1$ , and $x_{4k+1} = 4k-2$ , so $||||\cdots|x_1-x_2|-\cdots-x_{4k-2}|-x_{4k-1}|-x_{4k}|-x_{4k+1}|$ $= ||||1-(4k+1)|-4k|-(4k-1)|-(4k-2)$ $= |||4k-4k|-(4k-1)|-(4k-2)| = |4k-1-(4k-2)| = 1$ . Thus 1 is attainable. This implies that 401 is attainable for the original expression, so the maximum value is 401.

Group 2-401 as (2,3,4,5), (6,7,8,9), ……(398,399,400,401) to make 0, then |1-402|=401. By module 2 the answer is odd and is <=402.

Since $|x - y| \leq \max \{x,y\}$ , we get that $S \leq 402$ . Since $|x-y|$ has the same parity as $x + y$ , it follows that $S$ has the same parity as $1 + 2 + \ldots + 401 = \frac {1}{2} (402)(403)$ , so $S$ is odd. Thus $S \leq 401$ .

To show that this is possible, use the permutation

$x_i = \begin{cases} 4k + 2 & i = 4k+1, k < 100 \\ 4k + 4 & i = 4k+2, k < 100 \\ 4k + 5 & i = 4k+3, k < 100 \\ 4k + 3 & i = 4k+4, k < 100 \\ 402 & i=401\\ 1 & i = 402 \\ \end{cases}$

In this case, $S=401$ , hence that is the maximum value.