Originally Posted by

**Grandad** Hello VENILet $\displaystyle A=\{1,2,...,2n\}$, and we select the subset $\displaystyle S \subset A, |S| = n+1$.

Let $\displaystyle S = \{a_i, i = 1 \dots n+1\}$. Then each of the $\displaystyle a_i$ can be factorised into $\displaystyle 2^p_i \times q_i$, where $\displaystyle q_i$ is odd, $\displaystyle q<2n$ and $\displaystyle p \ge 0$. But there are just $\displaystyle n$ odd integers $\displaystyle < 2n$. Therefore, by the pigeon-hole principle, two of the $\displaystyle q_i$ are equal, and hence one of the $\displaystyle a_i$ is a multiple of another.

Grandad