Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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 1:32
Possible duplicate:… – 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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