Why Can't They Be All Different?


Why Can't They Be All Different?

Solution 1

Adding up all $n$ given identities gives

$\displaystyle\begin{align}\sum_{k=1}^{2n}a_k&=\sum_{k=1}^n(2n-k+2)=2n(n+1)-\sum_{k=1}^nk\\ &=\frac{3}{2}n(n+1). \end{align}$

Assume $a_1,a_2,\ldots,a_{2n}$ are all distinct. Let $b\ge 1$ be the least number among $a_1,a_2,\ldots,a_{2n}.$ Then

$\displaystyle\begin{align} \frac{3}{2}n(n+1)&=\sum_{k=1}^{2n}a_k\ge 2nb+\sum_{k=0}^{2n-1}k\\ &=2nb+\frac{(2n-1)2n}{2}\ge 2n+n(2n-1)=n(2n+1), \end{align}$

implying $\displaystyle\frac{3}{2}n(n+1)\ge n(2n+1),$ i.e., $1\ge n.$ A contradiction.

Further Thoughts

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 of $a_k+a_{2n-k+1}=2n-k+2,$ let's try $a_k+a_{2n-k+1}=2n-k+r,$ for some integer $r.$ Following the above solution, we then get

$\displaystyle\begin{align}\sum_{k=1}^{2n}a_k&=\sum_{k=1}^n(2n-k+r)=n(2n+r)-\sum_{k=1}^nk\\ &=\frac{3}{2}n^2+n\left(r-\frac{1}{2}\right).\end{align}$

Assuming the numbers distinct and $b$ as before gives

$\displaystyle \frac{3}{2}n^2+n\left(r-\frac{1}{2}\right)\ge n(2n+1),$

i.e., $2r-3\ge n.$ This would be a contradiction with $r\le 2.$ There is a link between the upper bound on $r$ and the lower bound on $n.$ This observation allows for a modification of the problem. For example,

$n\in\mathbb{N},n\ge 4.$ $2n$ positive integers $a_1,a_2,\ldots,a_{2n}$ satisfy


Prove that at least two of the numbers $a_1,a_2,\ldots,a_{2n}$ are equal.

Another possibility is to seek the bound on $r,$ given a bound on $n.$ E.g.,

$n\in\mathbb{N},n\ge 2.$ $2n$ positive integers $a_1,a_2,\ldots,a_{2n}$ satisfy


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

Still, a mystery.

Solution 2

Suppose all $a_i's$ are distinct positive integers. The smallest sum of the numbers is obtained when the numbers are $1,\ldots,2n$. The sum in this case is


If we choose any other set of $2n$ distinct positive integers, the sum will be greater than $s$.

From the constraints, the sum of the $a_i's$ is

$\displaystyle S=\sum_{k=1}^n (2n-k+2) =2n(n+1)-\frac{n(n+1)}{2}=\frac{3n(n+1)}{2}.$

$\displaystyle s-S=n(2n+1)-\frac{3n(n+1)}{2}=\frac{n(n-1)}{2}>0~(\text{for}~n\geq 2).$

Thus, the sum of the $a_i's$ is smaller than the sum of any $2n$ distinct positive integers. Thus all the $2n$ $a_i's$ cannot be distinct.


This is problem 793 from Kunihiko Chikaya's facebook group Enjoying Solving Mathematics. I use it with Kunihiko's kind permission.

Solution 2 is by Amit Itagi.


|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny