3
$\begingroup$

Here is the complete question:

**

Consider $2n$ distinct positive numbers (with $n>2$) such that each of them is less than or equal to $n^{2}$. Prove that three differences $a_{i}-a_{j}$ are the same

**

I have difficulty to get an idea that lead me to the solution from the work I have done so far. Here is what I have.

It is clear that we have ${2n}\choose{2}$ or $2n^2-n$ ways of arranging the $2n$ numbers in pairs, from each pair we can obtain a difference (I am asumming the difference must be positive). On the other hand, there are $n^2-1$ possible numbers that can be the difference between any pair of numbers. Since $2n^2-n>n^2-1$, we conclude that there is at least 2 pairs of numbers that have the same difference. Now if we can assign a distinct number from the set of possible differences to a pair then we are left with $n^2-n+1$ pairs that must repeat a number from the possible differences.

Now I want to show that somehow you must repeat a third time a difference. Some thoughts about it:

From the $n^2-n+1$ pairs that repeated a difference we can take one of them and the other pair that lead to the same difference and interchange two of their numbers, like this, say we have $a_{1}-a_{2}=a_{3}-a_{4}$ then do the change so that $a_{1}-a_{3}=a_{2}-a_{4}$ (we can always do this since are each $a_{i}$ are natural numbers, hence there is an order). Thus, it seems that each couple of pairs (like the ones above) can be associated with another couple, but if we try to associate them with a different couple we get a situation in which there is a couple who cannot associate with any other couple, because $n^2-n+1$ is odd.

But here is where I am stuck, I can't see an observation that lead me to the solution.Perhaps the whole idea is complicated and I should require another direction. Hope you can help, and thanks if you read this.

$\endgroup$
2
$\begingroup$

Let $a_j$ be the given numbers in increasing order: $$ 1 \le a_1 < a_2 < \dots < a_{2n} \le n^2 $$ and let $d_j$ be the difference of consecutive numbers: $$ d_j = a_{j+1} - a_j \quad \text{for $j = 1, \ldots, 2n-1$} \, . $$ Then all $d_j$ are positive and $$ d_1 + d_2 + \ldots + d_{2n-1} = a_{2n} - a_1 \le n^2 - 1 \, . $$

On the other hand, if the claim is false, then

  • at most two of the $d_j$ can be equal to $1$,
  • at most two of the $d_j$ can be equal to $2$,
  • ...
  • at most two of the $d_j$ can be equal to $n-1$

and it follows that $$ d_1 + d_2 + \ldots + d_{2n-1} \ge 2 \cdot 1 + 2 \cdot 2 + \dots 2 \cdot (n-1) + n \\ = 2(1 + 2 + \ldots (n-1)) + n = n^2 \, . $$

Remark: The statement (and the above proof) holds for $n=1$ and $n=2$ as well. For $n=1$ it is a "vacuous truth" because there are no distinct numbers $(a_1, a_2)$ satisfying $1 \le a_j \le n^2 =1$. For $n=2$, the only valid choice of $(a_1, a_2, a_3, a_4)$ is a permutation of $(1, 2, 3, 4)$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

After some thought I think I finally found my observation. Resuming the argument, we have $n^2-n+1$ pairs of integers that have to repeat a difference from the possible ones(except $n^2-1$) but as $n^2-n+1$ is odd there is a couple of pairs that we can't associate to another one, hence there is a pair of integers that can't have its designated difference. So if we try to assign to it another difference from the $n-3$ which do not repeated, we are left with the same situation, because the number of couples of pairs remains odd. Therefore, the difference that this pair must have is one of the repeated $n^2-n$ differences.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.