MHB Pairwise difference of 20 positive integers. At least four of em are equal.

AI Thread Summary
Given 20 distinct positive integers less than 70, there are 190 pairwise differences, but only 68 possible distinct values for these differences. By assuming that at most three differences can be equal, a contradiction arises when calculating the sum of the differences, leading to the conclusion that the largest integer must exceed 70. This contradiction implies that among the pairwise differences, there must be at least four equal numbers. Thus, the proof is established that at least four pairwise differences are equal.
caffeinemachine
Gold Member
MHB
Messages
799
Reaction score
15
Given $20$ pairwise distinct positive integers each less than $70$. Prove that among their pairwise differences there are at least four equal numbers.
 
Mathematics news on Phys.org
caffeinemachine said:
Given $20$ pairwise distinct positive integers each less than $70$. Prove that among their pairwise differences there are at least four equal numbers.

Total number of pairwise differences $\displaystyle =\binom{20}{2}=190$. Each difference must belong to the set $\{1,\ 2,\ \ldots,\ 68\}$: there are only 68 distinct values for each pairwise difference.

I don't know how to proceed...
 
Last edited:
Alexmahone said:
Total number of pairwise differences $\displaystyle =\binom{20}{2}=190$. Each difference must belong to the set $\{1,\ 2,\ \ldots,\ 68\}$: there are only 68 distinct values for each pairwise difference.

I don't know how to proceed...

How does "Challenging Puzzles.." forum work?
Am I supposed to post the solution(in case no one is able to solve it) within a day, a week or what?
 
caffeinemachine said:
How does "Challenging Puzzles.." forum work?
Am I supposed to post the solution(in case no one is able to solve it) within a day, a week or what?

If no one replied, you could do that. But since I've posted an attempt, you could just give me a hint. :)
 
Alexmahone said:
If no one replied, you could do that. But since I've posted an attempt, you could just give me a hint. :)
Let the $20$ numbers be ordered as $a_1 < a_2 < \ldots < a_{20}$.
Consider the differences:

$a_{20}-a_{19}, a_{19}-a_{18}, \ldots, a_2-a_1$
 
caffeinemachine said:
Let the $20$ numbers be ordered as $a_1 < a_2 < \ldots < a_{20}$.
Consider the differences:

$a_{20}-a_{19}, a_{19}-a_{18}, \ldots, a_2-a_1$

Assume, for the sake of argument, that among the pairwise differences there are at most 3 equal numbers.

$(a_{20}-a_{19})+(a_{19}-a_{18})+\ldots+(a_2-a_1)\ge 1+1+1+2+2+2+\ldots+6+6+6+7=3*6*7/2+7=70$

$a_{20}-a_1\ge 70$

$a_{20}\ge 70+a_1>70$ (contradiction)

So, among the pairwise differences there are at least 4 equal numbers.
 
Alexmahone said:
Assume, for the sake of argument, that among the pairwise differences there are at most 3 equal numbers.

$(a_{20}-a_{19})+(a_{19}-a_{18})+\ldots+(a_2-a_1)\ge 1+1+1+2+2+2+\ldots+6+6+6+7=3*6*7/2+7=70$

$a_{20}-a_1\ge 70$

$a_{20}\ge 70+a_1>70$ (contradiction)

So, among the pairwise differences there are at least 4 equal numbers.

Great!
 
Back
Top