# Choosing $100$ numbers in which one of the chosen number is divisible by another one

Prove that if $100$ integers are chosen from $1,2, \ldots, 200$, and one of the integers chosen is less than $15$, then there are two chosen numbers such that one of them is divisible by the other.

It is a classic exercise in combinatorics. For the answer, please refer to Choose 100 numbers from 1~200 (one less than 16) - prove one is divisible by another!. I want to move forward and ask something more. First, let me rephrase the question:

$100$ integers are chosen from $1,2, \ldots, 200$. Let $n$ be the smallest number of these chosen numbers. Prove that if $n=1,2,\ldots, 15$, then two chosen numbers can be found such that one of them is divisible by the other.

Now my question is:

Find all possible $n$.

This question comes to my mind when I first encounter this exercise. I was curious that why we should have the condition 'less than 16'. What if I change it to 'less than 17'? Does it mean that if $n=16$, it would be possible for me to find a counterexample? Of course, $n$ cannot be too large, as if $n=101$, then the chosen numbers would be $101, 102, \ldots, 200$ and none of them is a multiple of the others. So, I get the sense that some values of $n$ work, while some don't. So I post here to gather your opinions.

By the way, I cannot prove or disprove the statement when $n=16$. I think the idea to prove or disprove this case would help understand more about my ultimate questions.

$100$ integers are chosen from $1,2, \ldots, 200$. Let $n$ be the smallest number of these chosen numbers.

Prove or disprove: If $n=16$, then two chosen numbers can be found such that one of them is divisible by the other.

My attempt to construct a counterexample:

• I noticed that no two numbers in the set $\{101, 102, \ldots, 200\}$ divides each other. So, I started with this set and added in $16$.
• Then I had to remove $112, 128, 144, 160, 176, 192$.
• I needed to add in some new numbers, but I then would need to, again, remove many more existing numbers. So I think it is getting nowhere....
• Think in another direction: Start with an empty set. Add in the smallest number $16$. Then all the multiple of $16$ cannot be in the set.
• Add in another number, say $17, 18, \ldots, 31$. Wait... Then I cannot add in anymore numbers...

I welcome any comments and suggestions.

• If you read the accepted answer, you know that you need to be careful with what pigeon holes you choose, you can't just start off with all the numbers above $100$. That being said, it's entirely possible that the $16$ was not a real limit to the problem, but rather the limit as to where a pigeon hole proof stops being practical. – Arthur Sep 23 '15 at 13:48

There is a counterexample for the case where the condition is a number chosen is less than or equal to $16$. It is built on the ideas found in the question link and another similar question:

## Prove that at most $100$ numbers can be selected

Form descending 2-sequences (these are the pigeonholes) starting with each term in $T=\{101,102,\ldots,199,200\}$, where each sequence is finite and ends on an odd term and the term in any sequence is the previous term divided by $2$. Denote each sequence by its starting term (note that $n=100$), e.g. $$\begin{array}{rll} S_{2n}&=(2n,n,\ldots)&=(200,100,50,25) \\ S_{2n-1}&=(2n-1) &=(199)\\ &\quad\vdots \\ S_{n+2}&=\{n+2,\ldots\}&=(102,51) \\ S_{n+1}&=\{n+1,\ldots\}&=(101) \end{array}$$

Every number in $\{1,2,\ldots,2n\}$ appears in exactly one of the $S_{k}$ because:

1. Surjective. Every number inclusively between $1$ and $n$ has a multiple of a power of two inclusively between $n+1$ and $2n$. If not, $2 \ge \frac{2n+1}{n}$, which is absurd.
2. Injective. No number can appear in more than one sequence. If this was untrue we could find two distinct terms in $\{n+1,n+2,\ldots,2n\}$, one of which is a multiple (of a power of two) of the other.

It is clear that every pair of terms in a given $S_{k}$ has the smaller term dividing the larger one, so we can choose at most one term from each $S_{k}$.
To construct a counterexample, we need to choose exactly one from each, and ensure that $16$ is included.

## Sketch of the counteraxample P

When $n$ is odd, $S_n={n}$ has only one element, so this must be chosen. Hence, we need that $P$ contains every odd integer between $100$ and $200$, i.e. $$P_1=\{101,103,105,\ldots,199\}$$

This eliminates all submultiples so for the elements that cannot be chosen: $$Q_1=\{1,3,5,\ldots,65\}$$