37
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You can use the pigeonhole principle to conclude that there are $x_p$ and $x_q$ with $p\neq q$ and $x_p = x_q \pmod{2014}$. I wrote an incorrect solution but decided to delete it since there are two many problems. 1) $x_p - x_q = \pm 2014$ does not lead to the desired equality, 2) $x_p - x_q = \pm 4028$ is also possible, which leads nowhere. $\endgroup$ – zhoraster Sep 9 '15 at 6:17
  • $\begingroup$ Thank you,so I think this problem is interesting,I think this right constan $2014$ can change any other postive intergers, $\endgroup$ – user225250 Sep 10 '15 at 11:55
  • 7
    $\begingroup$ Some numeric results: If we generalize this to permutations of $[1,n]$ with $a_i-a_j\ne i-j$ and look for $|p-q|+|a_p-a_q|=n-2$, there are $2,0,2,10$ permutations without such $p$, $q$ for $n=4,6,8,10$, respectively; so the solution may have to make use of some specific features of $2016$, perhaps being divisible by $3$. $\endgroup$ – joriki Sep 15 '15 at 23:01
  • 6
    $\begingroup$ Here are the solutions without such $p$, $q$ for $n=4,8,10$ -- perhaps they contain a clue to a proof: $n = 4$: [2, 4, 1, 3] [3, 1, 4, 2]; $n = 8$: [4, 8, 2, 6, 3, 7, 1, 5] [7, 3, 5, 1, 8, 4, 6, 2]; $n = 10$: [2, 6, 9, 4, 7, 1, 10, 5, 8, 3] [4, 8, 2, 6, 9, 3, 7, 1, 10, 5] [5, 10, 8, 2, 4, 7, 9, 3, 1, 6] [5, 10, 9, 3, 8, 7, 4, 2, 1, 6] [5, 10, 9, 7, 4, 3, 8, 2, 1, 6] [6, 1, 10, 4, 8, 2, 5, 9, 3, 7] [8, 3, 6, 1, 10, 4, 7, 2, 5, 9] [9, 4, 8, 5, 1, 10, 6, 3, 7, 2] [9, 8, 4, 7, 1, 10, 6, 5, 3, 2] [9, 8, 6, 5, 1, 10, 4, 7, 3, 2] $\endgroup$ – joriki Sep 16 '15 at 7:01
  • $\begingroup$ @san: I'm afraid I don't see the problem. What rule does that violate? $\endgroup$ – joriki Sep 30 '15 at 6:39
4
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy