Do $p,q$ exist such $|p-q|+|a_{p}-a_{q}|=2014$

Let $\{a_1,a_2,\ldots,a_{2016}\}=\{1,2,3,\ldots,2016\}=A$ be such $$\dfrac{a_i-a_j}{i-j}\neq 1,\forall i,j\in A\text{ with } i\neq j.$$ Show that there exists $p,q\in A$ such that $$|p-q|+|a_p-a_q|=2014.$$

My approach is the following:

Put $x_i=a_i-i$, then we have $$\sum_{i=1}^{2016} x_i=\sum_{i=1}^{2016} a_i-\sum_{i=1}^{2016} i=0,|x_j|\le 2016,j=1,2,\cdots,2016$$ and $$\dfrac{a_i-a_j}{i-j}\neq 1,\Longleftrightarrow x_i\neq x_j\forall i,j\in A\text{ with }i\neq j$$I'm stuck here and I don't know how to proceed. Thanks.

Solution 1:

The problem is false as stated. Here is a counterexample that works for any $n=4k$:

$$\vec a = (\color{red}{4k-1}, \color{blue}{2k-1}, \color{red}{4k-3}, \color{blue}{2k-3}, \ldots, \color{red}{2k+3}, \color{blue}{3}, \color{red}{2k+1}, \color{blue}{1}; \color{green}{4k}, \color{brown}{2k}, \color{green}{4k-2}, \color{brown}{2k-2}, \ldots, \color{green}{2k+2}, \color{brown}{2}).$$

In formulaic terms this is: $$a_i = \begin{cases} \color{red}{4k-i},& \text{if $i\le2k$ and $i$ is odd};\\ \color{blue}{2k+1-i},& \text{if $i\le2k$ and $i$ is even};\\ \color{green}{6k+1-i},& \text{if $i>2k$ and $i$ is odd};\\ \color{brown}{4k+2-i},& \text{if $i>2k$ and $i$ is even}. \end{cases}$$

I leave it as an exercise to verify this is a permutation (notice that all the odd values of $a$ occur in the first half, and all the even values occur in the second).

We next verify that $\vec a$ satisfies the slope condition. Clearly the values of $a_i-i$ are distinct within each clause, since locally $a_i$ is a line of slope $-1$, not $+1$. But the following chart shows why no distinct clauses can overlap:

$$\text{$a_i-i$ is } \begin{cases} \text{even and $>0$},& \text{if $i\le2k$ and $i$ is odd};\\ \text{$\equiv 1 \pmod 4$},& \text{if $i\le2k$ and $i$ is even};\\ \text{$\equiv 3 \pmod 4$},& \text{if $i>2k$ and $i$ is odd};\\ \text{even and $<0$},& \text{if $i>2k$ and $i$ is even}. \end{cases}.$$

Finally, it remains to show that $|p-q|+|a_p-a_q| \ne 4k-2$. Again, within each clause this is trivial as $|p-q|+|a_p-a_q| = 2|p-q| < 4k$ if $p,q$ are from the same clause.

Suppose that $p,q$ are from different clauses (WLOG $p<q$) and that $|p-q|+|a_p-a_q| = 4k-2$. Since $(p-q)-(a_p-a_q)$ is even, $a_p-p$ and $a_q-q$ must have the same parity. Referring back to the previous chart, we see there are only two cases left to consider.

Case 1. $p\le 2k$, $p$ odd, $q>2k$, $q$ even.

Then $a_p = 4k-p > 2k \ge 4k+2-q = a_q$, so $|p-q|+|a_p-a_q| = (q-p) + (a_p-a_q) = 2(q-p-1) \equiv 0 \pmod 4$, which can't be $4k-2$.

Case 2. $p\le 2k$, $p$ even, $q>2k$, $q$ odd.

Then $a_p = 2k+1-p < 2k \le 6k+1-q = a_q$, so $|p-q|+|a_p-a_q| = (q-p) + (a_q-a_p) = 4k \ne 4k-2$.