2016 CMO 第 4 题

Let $n \geq 2$ be a positive integer and define $k$ to be the number of primes $\leq n$ . Let $A$ be a subset of $S = \{2,...,n\}$ such that $|A| \leq k$ and no two elements in $A$ divide each other. Show that one can find a set $B$ such that $|B| = k$ , $A \subseteq B \subseteq S$ and no two elements in $B$ divide each other.

令 $n \geq 2$ 为正整数，并定义 $k$ 为素数 $\leq n$ 的数量。令 $A$ 为 $S = \{2,...,n\}$ 的子集，使得 $|A| \leq k$ 并且 $A$ 中没有两个元素可以相互分割。表明可以找到一组 $B$ 使得 $|B| = k$ , $A \subseteq B \subseteq S$ 并且 $B$ 中没有两个元素可以相互分割。