Pigeonhole Principle - numbers between $1$ and $100$ [duplicate]

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.

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

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$?
• 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? – Giiovanna Oct 24 '13 at 12:49
• @user2768645: Yes, that’s right. And you’re choosing $51$ numbers, so ... ? – Brian M. Scott Oct 24 '13 at 12:50
• 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$ – Giiovanna Oct 24 '13 at 12:54
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.