Number Theory – Choosing 101 Numbers from {1, 2, …, 200}

number theorypigeonhole-principle

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 proof 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.

Best 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.

Related Question