Show that at least two numbers that are equal among $a_1,a_2, \cdots, a_{2n}$.

Question

Let $n\ge2$ and Let $a_1,a_2, \cdots, a_{2n}$ be $2n$ positive integers satisfying

$$a_k+a_{2n-k+1}=2n-k+2,\,\, k=1,2, \cdots, n$$

Then show at least two numbers that are equal among $a_1,a_2, \cdots, a_{2n}$.

Having solved the problem, I still - very surprisingly - have no feeling as what exactly forces the presence of two equal numbers. The premises seemed sufficiently soft not to impose the conclusion. So I tried a little modification: instead I assume $$a_k+a_{2n-k+1}=2n-k+r,\,\, k=1,2, \cdots, n$$ for some integer $r$.

Find the largest $r$ that forces at least two among $a_1,a_2, \cdots, a_{2n}$. to be equal.

Answer 1

For $r= 3$, $n=2$ doesn't work.

$$a_1+a_4= 6\\ a_2+a_3=5$$ has the slution $$a_1=1, a_2=2, a_3=3, a_4=5$$

More generally, for $r \geq 3, n=2$ $$a_1+a_4= 3+r\\ a_2+a_3=2+r$$ has the slution $$a_1=1, a_2=2, a_3=r, a_4=2+r$$

Edit So $r=2$ is the largest which works. Not solving it yet, the problem screams pigeonhole principle to me, and if this is the case, increasing $r$ by one typically increases the number of holes by 1 and makes the problem not work anymore (otherwise, the same solution works and the problem would have been stated with $r+1$ in the first place).

Answer 2

It is indeed a pigeonhole sort of problem. Take the $m$-th sum to be $a_m + a_{2n-m+1}$. The maximum such sum occurs when $m=1$ and is $$ 2n-1+2=2n+1 $$ This forces all terms to be smaller, since if one was greater than or equal to $2n+1$, its sum would be bigger than the maximal one. For this case ($r=2$) this means that if all the terms are to be unique then the sequence would have to be some permutation of all the natural numbers up to $2n$, because there are $2n$ terms and the same number of possible places they can take.

For any sum $m$ there would have to be one term in the sequence less than or equal to $\Bigl\lfloor\dfrac{m}{2}\Bigr\rfloor$. In particular, there would have to be $n-1$ numbers less than or equal to $\Bigl\lfloor\dfrac{2n+1}{2}\Bigr\rfloor=n$ after the first $n-1$ sums so only one place would be left free among $(1\ldots n)$. Then, for the $n$-th sum, we need, as before, two numbers less than $2n-n+1=n+1$ or two free places among that same $(1\ldots n)$ which is impossible since there is only one. So there would have to be a repeat. $\square$

For $r$'s $>2$ there is literally "more space" since the maximum sum is bigger, of the form $2n+(r-1)$, leaving more space for the terms that all have to fit under $\Bigl\lfloor\dfrac{2n+(r-1)}{2}\Bigr\rfloor$. Since we were only short of one place in our case, the proof does not hold for $r>2$.

I'm still not sure how to prove that $r=2$ is the only case so I'll just post some thoughts in that direction here.

If we write valid sequences in the form $A|B$ where $A$ and $B$ are the two subsequences of length $n$, a valid sequence for $r=3$ that has unique terms would be: $$ 2,3,1|5,4,6 $$ For any $r>3$, the sequence $$ 2,3,1|5+(r-3),4+(r-3),6+(r-3) $$ would also be valid. So we have the case $n=3$ and any $r$. Extending this to all $n$ seems a bit harder.