3
$\begingroup$

I want to prove that if you choose $101$ numbers from the set $\{1,2,3,4,\dots ,200\}$, there are always two numbers such that one divides the other with no remainder. The prove should involve the "pigeonhole principle".

I am not sure how to define the pigeonholes and how to define the pigeons. Any assistance with the proof will be most appreciated.

Thank you.

$\endgroup$
  • $\begingroup$ Write numbers in form $2^kq$ where q is odd, then the result should follow easily $\endgroup$ – arberavdullahu May 8 '17 at 9:05
  • 1
    $\begingroup$ Do you mean like this: 1=(2^0)*1, 2=2*1, 3=(2^0)*3,...what are the holes and what are the pigeons? Not sure I am following you, $\endgroup$ – user3275222 May 8 '17 at 9:18
  • 2
    $\begingroup$ Well then the holes are odd number 1,3,5,..,199, then from 101 numbers there will be two with same q. $\endgroup$ – arberavdullahu May 8 '17 at 9:23
  • 1
    $\begingroup$ Got it, thanks ! $\endgroup$ – user3275222 May 8 '17 at 9:36
4
$\begingroup$

Write each of the $101$ numbers as $2^kq$ for some odd $q$. There are $100$ choices for $q$. Hence there must be at least two of the $101$ numbers, $2^{k_1}p$ and $2^{k_2}p$, such that the odd number is the same and so one divides the other.

$\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.