Of the set $A=${$1,2,...,100$}, we will choose $51$ numbers. Prove that, among the $51$ chosen numbers, there are two such that one is multiple of the other

My notes:

1) There are $25$ prime numbers between $1$ and $100$ ;

2) There are $26$ odd and non-prime numbers between $1$ and $100$

3) There are $49$ even and non-prime numbers between $1$ and $100$

4) $B=${$51,52,...,100$} do not have multiples on the set $A$, but if we choose a number in $A-B$ we can find a multiple of this number in $B$

I couldn't find a good way to organize the problem. Sometimes I think I am just getting a particular solution, I mean, I am choosing particular numbers to form my set of $51$ numbers. I thought the better situation is to choose all the primes and apply the pigeon hole principle to the rest of the chosen numbers.

Thanks for your help!


marked as duplicate by darij grinberg, Jendrik Stelzner, YuiTo Cheng, Adrian Keister, José Carlos Santos May 31 at 13:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


HINT: Every positive integer can be written uniquely in the form $2^km$, where $k\ge 0$ and $m$ is odd. How many choices for $m$ are there for numbers in $A$?

  • $\begingroup$ Thank you very much for your attention. Since all the numbers can be written as $2^k m$, if I choose an odd number $x$ in $A$, the only way to write it is using $k=0$ and $x=m$. Then, there are $50$ choices for m (since I will use the same values for my even numbers). Is that correct? $\endgroup$ – Giiovanna Oct 24 '13 at 12:49
  • $\begingroup$ @user2768645: Yes, that’s right. And you’re choosing $51$ numbers, so ... ? $\endgroup$ – Brian M. Scott Oct 24 '13 at 12:50
  • $\begingroup$ There are at least 2 "with the same $m$ ".Lets denote then for $x=m2^a$ and $y=m2^b$. Since $x \neq y$, then $a > b$ or $b > a$. Then, we will have that $x$ is multiple of $y$ or $y$ is multiple of $x$ $\endgroup$ – Giiovanna Oct 24 '13 at 12:54
  • $\begingroup$ @user2768645: Looks good to me! $\endgroup$ – Brian M. Scott Oct 24 '13 at 12:57
  • 1
    $\begingroup$ @user2768645: You’re welcome! Yes, every once in a while it comes in quite handy. $\endgroup$ – Brian M. Scott Oct 24 '13 at 13:00

By factoring out as many $2$'s as possible from our given set, we see that any integer can be written in the form $2^k\cdot a$, where $k\geq 0$ and $a$ is an odd integer. For the integers between $1$ and $100$, $a$ will be one of the $50$ integers $1,3,5,...,99$. Since we are choosing $51$ integers we see that there exists two integers with the same $a$ value. Thus we know that $2^m\cdot a = 2^n\cdot a$ where $m\geq0$ and $n\geq0$. So, $2^m=2^n$. If $m\lt n$, then the second number is divisible by the first. If $m\gt n$, then the first number is divisible by the second.


Not the answer you're looking for? Browse other questions tagged or ask your own question.