# A subset of size $101$ from $1, 2, 3, \ldots, 200$ must contain one element which divides another

Let $A$ be a subset of size 101 from the set $\{$1, 2, 3, . . . , 200$\}$ (of size 200). Show that $A$ contains an $x$ and a $y$ such that $x$ divides $y$.

This seems like it has something to do with the pigeon hole principle since we are choosing more than half of the elements from $A$. For instance, there has to be at least one $x \in A$ such that $x<100$, but I'm not quite sure how to proceed from here. I guess another way to state this problem is to say there exists an $r$ such that $rA \cap A$ is nonempty.

• A golden oldie. If $x$ and $y$ are pigeons (numbers between $1$ and $200$) then $x$ and $y$ belong in the same pigeonhole if $x\le y$ and $\frac{y}{x}$ is a power of $2$. – André Nicolas Jan 6 '15 at 0:55

Represent numbers from the set in this format, $x=2^pq$. Where $q$ is an odd integer and $1\le q \le 200$ and $p \ge 0$.
How many choices of $q$ are there? How many numbers are you selecting? Can you apply pigeon hole principle now?
• Ah! I see now. There are only 100 such $q's$ but $A$ has 101 numbers in it. So there must be $x, y \in A$ such that $x = 2^p q$ and $y = 2^r q$, and hence WLOG x divides y. Thanks! Clever trick. Need to remember any number can be written as a power of 2 times an odd number. When you say it like that, I guess it is pretty obvious! – DHH Jan 6 '15 at 1:18