Given 20 distinct positive integers, not greater than 70. Show that among their pairwise differences, at least four are equal.

Question

Problem: Given 20 distinct positive integers, not greater than 70. Show that among their pairwise differences, at least four are equal.

Solution given by the professor: We may assume that the numbers form an increasing sequence:$1 \leq a _ { 1 } < a _ { 2 } < \ldots < a_{20} \leq 70$. Clearly, $$a _ { 1 } + \left( a _ { 2 } - a _ { 1 } \right) + \left( a _ { 3 } - a _ { 2 } \right) + \left( a _ { 4 } - a _ { 3 } \right) + \ldots \left( a _ { 20 } - a _ { 19 } \right) = a _ { 20 } \leq 70$$ On the other hand, the 19 parentheses above are 19 differences. Suppose for a contradiction that no difference appears more than 3 times. Then the left hand side above is at least: $$1 + 3 \times 1 + 3 \times 2 + 3 \times 3 + 3 \times 4 + 3 \times 5 + 3 \times 6 + 1 \times 7 = 71$$ which is greater than 70, a contradiction.

My question: I don't understand the last step of the solution, where do the products comes from? Why are we observing products from 1 to 6? I read multiple posts on math stackexchange similar to these problems but I still don't get the last equality.

Answer 1

You want to minimize the telescopic sum for $a_{20}$:

• What is the minimal value for $a_1$? $1$!
• How do we minimize the $19$ differences under the given constraints? We take the difference $1$ three times, the difference $2$ three times, ... , the difference $6$ three times and the difference $7$ one time (as we have 19 differences in total)!

Answer 2

Let $n_i$ denote the number of differences that equal $i$.

Then

• $\sum_{i}n_i=19$
• $\sum_{i}i\cdot n_i=a_{20}-a_1\leq70-1=69$

Under assumption $n_i\leq3$ for every $i$ the summation $\sum_{i}i\cdot n_i$ is minimalized by taking $n_1=n_2=n_3=n_4=n_5=n_6=3$ and $n_7=1$.

This however results in $\sum_{i}i\cdot n_i=70>69$

So the assumption that $n_i\leq3$ for every $i$ must be rejected.

Answer 3

Consider $a_1=1$, then: $$71=1+(1)+(1)+(1)+\\ \qquad \qquad (2)+(2)+(2)+\\ \qquad \qquad(3)+(3)+(3)+\\ \qquad \qquad(4)+(4)+(4)+\\ \qquad \qquad(5)+(5)+(5)+\\ \qquad \qquad(6)+(6)+(6)+\\ (7)\le \qquad \qquad \ \ \ \\ a_1+(a_2-a_1)+(a_3-a_2)+(a_4-a_3)+\\ \qquad (a_5-a_4)+(a_6-a_5)+(a_7-a_6)+\\ \qquad (a_8-a_7)+(a_9-a_8)+(a_{10}-a_9)+\\ \qquad \qquad (a_{11}-a_{10})+(a_{12}-a_{11})+(a_{13}-a_{12})+\\ \qquad \qquad (a_{14}-a_{13})+(a_{15}-a_{14})+(a_{16}-a_{15})+\\ \qquad \qquad (a_{17}-a_{16})+(a_{18}-a_{17})+(a_{19}-a_{18})+\\ \qquad \qquad (a_{20}-a_{19})=a_{20} \not\le 70. \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad$$ If $a_1>1$, then $71<a_{20}\not\le 70$.

The contradiction implies the number of differences must be more than $3$.

Note: The differences above can be permuted.