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?

  • 3
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Feb 10 '13 at 1:32
  • 1
    $\begingroup$ Possible duplicate: math.stackexchange.com/questions/1193584/… $\endgroup$ – VividD Apr 20 '15 at 19:50

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.