# Choosing $101$ numbers from $\{1, 2, \dots , 200\}$.

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.

• Write numbers in form $2^kq$ where q is odd, then the result should follow easily – arberavdullahu May 8 '17 at 9:05
• 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, – user3275222 May 8 '17 at 9:18
• Well then the holes are odd number 1,3,5,..,199, then from 101 numbers there will be two with same q. – arberavdullahu May 8 '17 at 9:23
• Got it, thanks ! – user3275222 May 8 '17 at 9:36

## 1 Answer

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.