4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – André Nicolas Jan 6 '15 at 0:55
5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – DHH Jan 6 '15 at 1:18
  • $\begingroup$ Yup exactly. Most Pigeon hole problems have these kind of tricks. Once you discover that it becomes easy .:) $\endgroup$ – arindam mitra Jan 6 '15 at 1:26

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.