16
$\begingroup$

Prove that if 100 numbers are chosen from the first 200 natural numbers and include a number less than 16, then one of them is divisible by another.

How to prove this? many thanks....

  • 0
    I don't understand your question. Please, try to be more clear.2012-08-12
  • 2
    @Romeo: It seems clear enough: prove that if if $A\subseteq\{1,\dots,200\}$ is a set of $100$ integers, and if at least one member of $A$ is less than $16$, then $A$ must contain two distinct integers $a$ and $b$ such that $b\mid a$.2012-08-12
  • 0
    @BrianM.Scott yeah that's exactly what i mean, thanks for elaborate it! :)2012-08-12
  • 0
    @BrianM.Scott I hadn't understand that the sentence "one of them is less than 16" was an hypotesis. Now it's clear to me, thanks.2012-08-12
  • 0
    Hint: If more than half of the integers from $\{1, 2, ..., 200\}$ are selected, then some two of the selected integers have the property that one divides the other.2012-08-12
  • 0
    @SalechAlhasov if the "100" changes to "101", it would be quite easy.... but..2012-08-12
  • 0
    Using the "101" pigeonhole argument here, the numbers with their even parts removed must cover all odd numbers. An argument now with powers of 3 should work...2012-08-12
  • 0
    Is the pigeonhole principle specified as a method of solution? Note that 100 integers {101, 102 ... 200} can be chosen without the restriction that one should be less than 16. Then you could replace 200 with 200/2=100, 198 with 99 ... how small can you go, and what are the blockages?2012-08-12

2 Answers 2

10

Assign pigeonholes by considering that $a, b$ are in the same pigeonhole if $a/b$ is a power of two (including negative powers, in case $a). Now each pigeonhole has an odd number, plus that same odd number multiplied by each power of two. Since there are 100 odd numbers in $\{1,\ldots,200\}$, there are 100 pigeonholes. If two or more of the chosen numbers are in the same pigeonhole, then we're done. If not, then there must be one chosen number in each pigeonhole.

In the latter case, let $n$ be the chosen number that's less than 16. Consider these four cases.

  • If $n$ is an odd number, then it divides whatever number was chosen in the pigeonhole with $3n$.
  • If $n$ is twice an odd number, then EITHER it divides whatever number was chosen in the pigeonhole with $3n/2$, OR $3n/2$ itself was chosen, which divides whatever was chosen in the pigeonhole with $9n/2$.
  • If $n$ is 4 or 12, then consider what number might have been chosen in the pigeonhole with 9. If it's 36 or greater, we're done. If it's 9 or 18, then consider what number was chosen in the pigeonhole with 27. If it's 54 or higher, we're done. If it's 27, then it divides whatever number was chosen in the pigeonhole with 81.
  • If $n$ is 8, then consider what number might have been chosen in the pigeonhole with 3. If it's 24 or greater, we're done; but if it's 3, 6 or 12, then we've already covered this case in one of the earlier cases above.

So in all cases, there'll be a number in one pigeonhole that divides a number from another pigeonhole.

  • 0
    thanks! i think this is a quite clear explanation on how the numbers below 16 shall be examined. now i got it, thanks!2012-08-12
5

Here’s a slightly different approach.

Let $A$ be the set of $100$ numbers, and suppose that $A$ is a counterexample. Clearly $1\notin A$. If $2\in A$, the other $99$ members of $A$ must be the odd integers $3,5,\dots,199$, in which case $\{3,9\}\subseteq A$. Thus, we may assume that $1,2\notin A$.

Suppose that $n$ is odd and less than $16$. Then the other $99$ members of $A$ are not multiples of $n$. In particular, they must have odd parts that are not multiples of $n$. The $100$ possible odd parts include $3n$ and $5n$, so there are at most $98$ odd parts available for the other $99$ members of $A$. Thus, two of these numbers must have the same odd part, and the larger is then a multiple of the smaller. We may now assume that $1,2,3,5,7,9,11,13,15\notin A$.

If $6,10,12$, or $14$ is in $A$, the other $99$ members of $A$ must have odd parts different from $3,5,3$, or $7$, respectively, and it follows as in the previous paragraph that some member of $A$ is a multiple of another. We may now assume that $A\cap\{1,\dots,15\}\subseteq\{4,8\}$.

Suppose that $4\in A$ and $8\notin A$. $2\notin A$, so the $99$ other members of $A$ must have odd parts different from $1$. Thus, each odd part must be represented exactly once. But then $6\in A$ (since $A$ contains no proper multiple of $4$, and by hypothesis $3\notin A$), contradicting the assumption that $6\notin A$.

Finally, suppose that $8\in A$ and $4\notin A$. As in the previous case, each odd part must be represented once among the $99$ members of $A\setminus\{8\}$. But then one of $3,6$, and $12$ is in $A$, since $A\setminus\{8\}$ contains no multiple of $8$, contradicting the assumption that $A\cap\{1,\dots,15\}=\{8\}$.

Thus, there is no counterexample.

  • 0
    @brian-m-scott thanks! i see there're different ways of excluding the possibilities here....2012-08-13
  • 0
    @Brian M. Scott I did not understand in second paragraph you have written "The 100 possible odd parts include 3n and 5n, so there are atmost 98 odd parts" ? Can you please explain ? Thanks2015-07-10
  • 0
    @JPG: Every positive integer $a$ can be written uniquely in the form $a=2^km$, where $k$ is a non-negative integer, and $m$ is an odd integer; $m$ is the odd part of $n$. If $a\le200$, its odd part is at most $199$, so there are $100$ possible values for the odd part: $1,3,\ldots,199$. If $n$ is an odd integer less than $16$, then $3n$ and $5n$ are possible odd parts of integers in $A$. However, they are multiples of $n$, so if $n\in A$, then can’t be in $A$. This eliminates them as possible odd parts of integers in $A$, leaving only the other $98$ odd numbers less than $200$ as possibilities.2015-07-10
  • 0
    @BrianM.Scott: Thankyou Good Sir2015-07-11
  • 0
    @JPG: You’re welcome.2015-07-11