The following is a standard combinatorics question:



> 
> Any set of $n+1$ numbers from $1, \dotsc, 2n$ contains a pair of
>  numbers $a, b$ where $a \left| b \right.$
> 
> 
> 


The argument is by pigeonhole principle: consider $A\_i = \{2^k (2i-1), k\in \mathbb{N}\}.$ The sets $A\_i$ cover $1, \dotsc, 2n,$ and there are $n$ of them. 


The question is this: to find the maximal division-free set, the obvious way is to do the following (in *Mathematica*):



```
divGraph[n_] := With[{pairs = Subsets[Range[n], {2}]},
  With[{divis = Select[pairs, Mod[#[[2]], #[[1]]] == 0 &]},
   Graph[Apply[Rule, #] & /@ divis]]]

FindIndependentSet[divGraph[n]]

```

Now, when one runs this for smallish numbers one sees that the maximal set $S\_m(2n)$ always has cardinality $n,$ but also, the minimum of $S\_m(2n)$ is equal to 


* 1 once
* 2 thrice
* 4 nine times
* 8 $27$ times
* 16 $81$ times
* 32 $243$ times


And so on. The question is: what is going on? Is this the true size of the minimal element of $S\_m?$ As Vladimir Dotsenko points out, the obvious example has the minimum equal to $n+1.$



divisibility independence
First, I ran some bruteforce myself (I don't have access to Mathematica at the moment), and I'm fairly sure the mysterious numbers obtained in OP ($1, 2, 2, 2, 4\ldots$) are the *minimal possible numbers that are present in any $S\_m(2n)$*. I'm going to explain the pattern in this assumption.


Long story short, the minimal possible number in $S\_m(n)$ is $2^{\left\lfloor \frac{\log n}{\log 3} \right\rfloor}$.


As follows from the OP's explanation, for any odd number $x \leq n$ there is *exactly one* representative of form $x 2^k$ in any $S\_m(n)$. Let us call the exponent $k = d(x)$ the *degree* of $x$ in a particular $S\_m(n)$. Obviously, for non-equal $x \vert y$ we must $d(x) > d(y)$.


One can see that the "critical" values where the OP's minimal numbers change are exactly $\frac{3^k + 1}{2}$, that is, the minimum changes whenever a new power of 3 arrives in the set. One can indeed see that in any $S\_m(n)$ we have $d(1) \geq \left\lfloor \frac{\log n}{\log 3} \right\rfloor = k\_0$ by simply applying the inequality above for a divisor chain $1 \vert 3 \vert \ldots \vert 3^{k\_0}$. The numbers $2^{k\_0}$ follow the OP's pattern exactly.


But why any number that is not a binary power cannot be less than $2^{k\_0}$ in an $S\_m(n)$? Let $1 < x \leq n$ be an odd number. Then for any $S\_m(n)$ the numbers $\{2^{d(x)}, 3\cdot 2^{d(3x)}, \ldots\}$ must be an $S\_m(\left\lfloor \frac{n}{x} \right\rfloor)$. As we have shown above, that implies $d(x) \geq \left\lfloor \frac{\log \lfloor n/x \rfloor}{\log 3} \right \rfloor$. It suffices to show $2^{\left\lfloor \frac{\log n}{\log 3} \right\rfloor} < x \cdot 2^{\left\lfloor \frac{\log \lfloor n/x \rfloor}{\log 3} \right\rfloor}$. But $2^{\left\lfloor \frac{\log n}{\log 3} \right\rfloor - \left\lfloor \frac{\log \lfloor n/x \rfloor}{\log 3} \right\rfloor} \leq 2^{\frac{\log x}{\log 3} + 1} = 2 \cdot x^{\frac{\log 2}{\log 3}} < x$ for all $x > 5$ (for $x = 3, 5$ we may still have the claim by handling the rounding error more carefully).


To finish the proof, notice that the set $\{x \cdot 2^{\left\lfloor \frac{\log \lfloor n/x \rfloor}{\log 3} \right\rfloor}\}$ with $x$ ranging over odd numbers at most $n$ is an $S\_m(n)$. Note that this set is minimal with respect to any measure, e.g. no proper divisor of any of its elements can be in an $S\_m(n)$, hence it's also lexicographically minimal when sorted.


