The discussion centers on proving that among 20 pairwise distinct positive integers, each less than 70, there are at least four equal pairwise differences. The total number of pairwise differences is calculated as 190, while the maximum distinct values for these differences is limited to 68. By assuming that there are at most three equal differences and deriving a contradiction, the conclusion is reached that at least four differences must be equal.
PREREQUISITESMathematicians, students studying combinatorics, and anyone interested in problem-solving techniques related to number theory and inequalities.
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.
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...
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?
Let the $20$ numbers be ordered as $a_1 < a_2 < \ldots < a_{20}$.Alexmahone said:If no one replied, you could do that. But since I've posted an attempt, you could just give me a hint. :)
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$
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.