Pigeonhole Principle - numbers between $1$ and $100$

Question

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!

Answer 1

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$?

Answer 2

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.