MathNet 2001 — Part 01 Question 17

Let $n$ be a positive integer. Prove that at least $2^{n-1} + n$ numbers can be chosen from the set $\{1, 2, 3, \ldots, 2^n\}$ such that for any two different chosen numbers $x$ and $y$, $x + y$ is not a divisor of $x \cdot y$.