5

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!

1233dfv
  • 5,625
Giiovanna
  • 3,197

2 Answers2

6

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

Brian M. Scott
  • 616,228
  • 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
  • @user2768645: Looks good to me! – Brian M. Scott Oct 24 '13 at 12:57
  • Thank you! I didn't know this proposition, it looks very helpful – Giiovanna Oct 24 '13 at 12:58
  • 1
    @user2768645: You’re welcome! Yes, every once in a while it comes in quite handy. – Brian M. Scott Oct 24 '13 at 13:00
1

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.

1233dfv
  • 5,625