For a given integer n, what is the cardinality of the greatest subset of (1,n) such that no element of the subset divides another element?

Question

i.e. Let $A=\{1,2,3,...,n\}$, what is the greatest cardinality of $B\subset A$ s.t. no element in $B$ divides another element in $B$. Preferably using pigeonhole principle.

Answer 1

As pointed out in the comments, all we need is a minor addition to an earlier question

Suppose first that $n=2m$. Clearly the subset $m+1,\dots,2m$ works. Now make pigeonholes for $k=1,\dots,m$, so that the pigeonhole for $k$ contains all numbers $(2k-1)2^r$ (with $r\ge0)$) from $A$. Between them the pigeonholes contain the whole of $A$ and we can pick at most one number from each pigeonhole.

For $n=2m+1$, again the subset $m+1,\dots,2m+1$ works. Now we know we cannot pick more than $m$ from $1,2,\dots,2m$, so we cannot pick more than $m+1$ from $1,2,\dots,2m+1$.