My reasoning so far is:
If the number 1 is chosen, we are done since 1 divides any number.
If 2 is chosen, then the remaining n numbers to choose will either be all odd (including 1) or contain an even number.
I do not know how to progress from here. Does it require the pigeonhole principle? Thank you in advance.
Note that any $n \in \mathbb{Z}^{+}$ can be expressed in the form $2^{k} \times O$, where $k \in \mathbb{Z}_{\geq 0}$ and $O$ is the greatest positive odd divisor of $n$. This can be quite easily proved.
Now, consider any integer $z$ from $1,2,3, \ldots, 2n$. The greatest positive odd divisor of $z$ must be one of $1,3,5,7,\dots,2n - 1$. Hence the greatest positive divisor of $z$ can take any one of $n$ such values.
Now, let the pigeons be the $n + 1$ integers selected and the $n$ pigeonholes correspond to the possible values of the greatest positive odd divisor. Place each integer in the sequence $1,2,3,\ldots,2n$ into its unique pigeonhole.
By the pigeonhole principle, when $n+1$ integers are selected from $1,2,3,\ldots,2n$ it is guaranteed that two integers are selected from the same pigeonhole. Let $a,b$ be the integers selected from the same pigeonhole and let $O$ be the greatest positive odd divisor of $a,b$. Assume WLOG $a \lt b$ such that $a = 2^{r} \times O$ and $b = 2^{s} \times O$ where $r \lt s$ and $r,s \in \mathbb{Z}_{\geq 0}$. Now,
$$ \frac{b}{a} = \frac{2^{s} \times O}{2^{r} \times O}$$ $$ \implies b = 2^{s - r}\times a$$
By the closure of integers under subtraction, $s - r \in \mathbb{Z}$ and hence $2^{s - r} \in \mathbb{Z}$. Then it immediately follows by the definition of divisibility that $a|b$.