Problem

Source: Baltic Way 2001

Tags: number theory proposed, number theory, Combinatorial Number Theory



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$.