Choose 100 numbers from 1~200 (one less than 16) - prove one is divisible by another!

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<b$). 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.

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.

Let us suppose that we have chosen 100 positive integers , not exceeding 200 ,none of which is divisible by any other. Let us prove that none if the numbers from 1 to 15 is contained among these 100 numbers. Let us consider all the greatest odd divisors of the chosen numbers .It is obvious that these divisors from the set of all odd numbers not exceeding 200 .In particular ,these odd divisors there are no two numbers one of which is divisible by the other,the number containing the odd factor 27 must be divisible by a power of 2 whose exponent is at least one ,the number containing the odd factor 9 must be divisible by a power of 2.Whose exponent is atleast 2,the number containing the odd factor 3 must be divisible by a power of 2 whose exponent is atleast 3,the number containing the odd factor 1must he divisible by a power of 2 whose exponent is atleast 4.This means that the number 1,2=1.2, 2,3,4=1.2^2, 6=2.3, 8=1.2^3, 9 and 12 =3.2^2 are not contained among the 100 choen numbers. In just the same way we can consider those of the given numbers whose greatest odd divisors are 5,15 and 45 and prove the given numbers do not donation, 5,10=5.2 and 15.Similarly , if we consider the number 7 ,21 and 63 ,we can show that the numbers 7 and 14 are not among the 100 chosen integers; while if ee consider the numbers 11 and 33 ,we can show that 11 is not amobg the 100 chosen integers and if we consider the numbers 13and 39,we can show that 13 is not among the 100 chosen integers.