2

Twenty distinct integers are chosen from $\{1,2,...,69\}$. Prove that amongst their pairwise differences there are at least four which are identical.

I understand that the set $\{1...69\}$ is arbitrary. I'm having a hard time proving it. Should I prove through induction or use the pigeon hole principle?

user61646
  • 403
  • 3
    You can't do it in the simplest way. There are $\frac 12 \cdot 20 \cdot 19=190$ pairs and the differences can range from $1$ to $68$, so in theory you could have three each of $63$ different numbers and one of something else. Even recognizing that there is only one way to get $68$ and two ways to get $67$ doesn't exclude enough to get you there, as you would have $187$ pairs distributed over $66$ differences. – Ross Millikan Feb 10 '13 at 01:32
  • 1
    Possible duplicate: http://math.stackexchange.com/questions/1193584/problem-with-20-integers-less-than-70 – VividD Apr 20 '15 at 19:50

1 Answers1

7

Let the integers be $a_1\lt a_2\lt\cdots\lt a_{20}$, and let $b_1,b_2,\dots,b_{19}$ be given by $b_i=a_{i+1}-a_i$. Then $\sum_1^{19}b_i\le68$. But if you have $19$ positive integers, no one integer more than three times, then their sum must be at least $(1+1+1)+(2+2+2)+\cdots+(6+6+6)+7=70$. So some difference occurs at least $4$ times.

Gerry Myerson
  • 179,216