4
$\begingroup$

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!

$\endgroup$

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.

6
$\begingroup$

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

$\endgroup$
  • $\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
1
$\begingroup$

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.

$\endgroup$

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