Let $n \in \mathbb{N}$ and $A = \{ x \in \mathbb{N} : 1 \leq x \leq 2n \} $. Prove: If $X$ is a subset of $A$ with more than $n$ elements, then there exist, $a, b\in X $ such that $a \mid b$ or $b \mid a$. (Hint: If $a \in A$, then $a = 2^jm $ with $m$ odd and $ m \in A$.)
My prof said this was a classic pigeonhole principle type of proof. However, I am not seeing the pigeonhole principle type of proof here, nor do I know how to approach it to prove it.
If someone could give me some hints as to how to start this I can keep trying and update this post to reflect my attempts. Thanks!
In $A$ you have $n$ odd numbers. Every number can be written as $2^jm$ with $m$ odd and $j\geq 0$. So if you have at least $n+1$ numbers in $X$ it means you have decompositions $2^{j_s}m_s, s=1,\ldots,n+1$. Here at least one odd number has to come twice since there are only $n$ odd numbers to go around. So let $a=2^{j_a}m$ and $b=2^{j_b}m$ be such a pair. Then either $j_a\geq j_b$ or $j_b\geq j_a$ which is equivalent to $a|b$ or $b|a$.