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....
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....
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
In the latter case, let $n$ be the chosen number that's less than 16. Consider these four cases.
So in all cases, there'll be a number in one pigeonhole that divides a number from another pigeonhole.
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.