Problem

Source: China Mathematical Olympiad 2016 Problem 4

Tags: number theory



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.