Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
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

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.