Each number in a subset $S\subseteq \{1,\ldots,2n\}$ does not divide another one. Then $\max |S|$? This problem comes from a seemingly innocuous question from a professor during a lesson for a Math Olympiad course. [A part of this question is really a classic of number theory/combinatorics]
Problem: Let $S$ be a a non-empty subset of $\{1,2,\ldots,2n\}$. It is clear that if $|S|$ is "enough large" then, independently from the choice of $S$, there are for sure some distinct $a,b \in S$ such that $a$ divides $b$.
Then, what is the maximal $k$ such that, for some $S$ with cardinality $k$, if $a,b$ are distinct members of $S$ then $a$ does not divide $b$?
[Ps. I know the solution]
 A: Let $S=\{n+1,n+2,\ldots,2n\}$. The claim is that $|S|$ is maximal. 
To prove this, form descending sequences starting with each term in $S$, 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, e.g.
$$\begin{align}
S^{(2n)}&=\{2n,n,\ldots\} \\ 
S^{(2n-1)}&=\{2n-1\} \\
&\quad\vdots \\
S^{(n+1)}&=\{n+1,\ldots\}
\end{align}$$
Every number in $\{1,2,\ldots,2n\}$ appears in exactly one of the $S^{(k)}$ because:


*

*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.

*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 are free to choose at most one term from each $S^{(k)}$, i.e. $|S|\le n$ for any prospective set $S$. It is also clear that choosing $S$ as originally proposed gives $|S|=n$, so this is maximal.
