2
$\begingroup$

Choose any 38 different natural numbers less than 1000.

Prove that among the selected numbers there exists at least two whose difference is at most 26.

I think I need to use pigeon hole principle, not sure where to even begin.

$\endgroup$
  • $\begingroup$ You can choose? $\endgroup$ – Git Gud Mar 6 '13 at 20:03
  • 1
    $\begingroup$ I feel like i'm misunderstanding what's going on. Can we not just suppose that all differences are larger then $x_1 -x_2 > 26$ but if $x_2 - x_1>26 $ then $0>52$ $\endgroup$ – Ben Mar 6 '13 at 20:19
  • $\begingroup$ @Ben: The question would be clearer if "difference" is replaced by "distance". $\endgroup$ – azimut Mar 6 '13 at 20:27
  • $\begingroup$ @azimut I figured eventually thanks :-) $\endgroup$ – Ben Mar 6 '13 at 20:38
2
$\begingroup$

Pigeonhole-principle is a good idea.

Hint: Think about partitioning $\{1,2,\ldots,999\}$ into subsets $\{1,2,\ldots,27\}$, $\{28,29,\ldots, 53\}$, $\{54,55,\ldots,80\}$, ... of size $27$ each.

$\endgroup$
  • $\begingroup$ Would that be 37 subsets then? By making them size 27 then if I choose 1 number from each subset, 37 total, then this would mean that by Pigeon hole principle two of my 38 numbers will be from 1 subset, and thus their difference would be at most 26. Is this right in any way? $\endgroup$ – Dexter Mar 6 '13 at 20:24
  • $\begingroup$ Thanks for spotting this. I did a small mistake: The number 1000 is not in the range. I've modified my answer accordingly. $\endgroup$ – azimut Mar 6 '13 at 20:27
  • $\begingroup$ Just wondering is my answer okay though? Does it make sense? $\endgroup$ – Dexter Mar 6 '13 at 20:27
  • $\begingroup$ @Dexter: Yes, it makes perfect sense. You got it! $\endgroup$ – azimut Mar 6 '13 at 20:28
  • $\begingroup$ @Dexter: Yes, that is correct. I am sure that was the intended answer as well. $\endgroup$ – Ross Millikan Mar 6 '13 at 20:30
3
$\begingroup$

Pigeonhole principle is not necessary.

Hint: Suppose the statement is false. Then $\exists x_1,x_2,\dots,x_38$ each less than $1000$. Suppose without loss of generality that $x_1<x_2<\dots<x_{38}$. Then it must be true that $x_2 \geq x_1 + 27$. Similarly $x_3 \geq x_2+27\geq x_1 + 27\times2$. What is the lower bound on $x_{38}$?

$\endgroup$
  • $\begingroup$ Beaten to it :-( +1 ;-) $\endgroup$ – Ben Mar 6 '13 at 20:39
  • $\begingroup$ @Ben Sorry about that, couldn't leave it unsaid! $\endgroup$ – Tom Oldfield Mar 6 '13 at 20:42
3
$\begingroup$

Reasoning by contradiction, so suppose that we can choose 38 natural numbers $$0< a_1<a_2<\cdots<a_{38}<1000$$ such that the difference of any two numbers is at least 27. We can see easily that $$a_{n}\geq a_1+27(n-1),\forall n=1,\ldots,38, $$ so $$a_{38}\geq a_1+27\times37\geq1+27\times37=1000.$$ Contradiction. We conclude.

$\endgroup$

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.