（1）：是 （2）：至少是$\lceil \frac{n}{2}\rceil$：取最大的$\lceil \frac{n}{2}\rceil$个数 至多是$\lceil \frac{n}{2}\rceil$：用Dilworth定理。整除关系构成一个偏序集，我们要求最大反链的大小，其等于最小链覆盖的大小。在这里一个“链”是指$\{1,2,\dots,n\}$的子集$S$，使得对任意两个数$i,j\in S$，要么$i\mid j$，要么$j\mid i$。链覆盖指将$\{1,2,\dots,n\}$分成若干个链，最小链覆盖指分成的链的个数最小。 $\{1,2,\dots,n\}$有如下的链覆盖：对每个奇数$s$，构造一个链$\{s,2s,4s,8s,\dots,2^is\}$，其中$2^i$是不超过$n/s$的最大的$2$的幂。 这个链覆盖的大小为$\lceil\frac{n}{2}\rceil$，故最小链覆盖的大小不超过$\lceil\frac{n}{2}\rceil$。 （3）（4）：我不会:(

(4) 按所含的最大奇因子对 $[1,n]$ 进行划分，每一类恰好选一个数。设 $S(x)$ 表示奇数因子 $x$ 对应的集合，$f(x)$ 表示 $S(x)$ 中选的数是 $2^{f(x)}x$。那么 $\lceil \frac{n}{2} \rceil$ 的集合与一组满足 $\forall x\vert y, f(x)>f(y)$ 的 $f$ 一一对应。于是只要枚举合法的 $f$。这就是给定一个 DAG（有向无环图），每个点指定一个不超过该点上限的权值，并且满足每条边从权值大的指向权值小的。按某个拓扑序 DFS 枚举合法方案就行了，时间可以做到和合法方案数同阶。 (3) 我猜是 #P-Complete 的？因为从 (4) 来看这个问题很可能不弱于 DAG 拓扑序计数。