Welcome to our community

Be a part of something great, join today!

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

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
834
Given $20$ pairwise distinct positive integers each less than $70$. Prove that among their pairwise differences there are at least four equal numbers.
 

Alexmahone

Active member
Jan 26, 2012
268
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:

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
834
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?
 

Alexmahone

Active member
Jan 26, 2012
268
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. :)
 

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
834
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$
 

Alexmahone

Active member
Jan 26, 2012
268
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.
 

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
834
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!