Suppose $P$ is a set of $n + 1$ integers selected from $1,2,3,...,2n + 1$. Then how can we show $P$ contains two coprime integers? The result holds if $P$ contains only $n$ integers??
Added Let me add this funny question keeping the same spirit:
If $a_0,\ldots,a_n\in\{1,\ldots,2n\}$ are pairwise distinct then how can we show that there's $(i,j)\in\{1,\ldots,n\}^2$ such that $i\neq j$ and $a_i$ divide $a_j$.
On
Let $P$ be a set of $n+1$ integers selected from $1,2,3,\cdots,2n+1$. If $2n$ and $2n+1$ are in $P$ you are done (since they are coprime). If this is not the case you can erase one element from $P$ in such a way that the reduced set has elements from $1,2,3,\dots,2n-2,2n-1$. Now, the result follows by induction (it is easy to check the statement for $n=1$).
If you take $P$ to be the set of even numbers in $1,2,3,\cdots,2n+1$ you have that $P$ has $n$ elements and there is not a pair of coprime elements in $P$.
On
Re: Addendum: You can write $a_i = 2^{e_i} b_i$, where all $b_i$ are odd. There are only $n$ possible values for $b_i$, so among the $n + 1$ of them one repeats, i.e. there are $a_i$ and $a_j$ which only differ in the power of 2, and one divides the other.
[This should have been a separate question, perhaps linking to the present one.]
If 1 is part of the set, game over. If 1 isn't in the set, there are $n$ pairs $(2, 3)$, $(4, 5)$, ... $(2 n, 2 n + 1)$. As there are $n + 1$ numbers, two must be in the same pair, i.e. $k, k + 1$ are in the set, and they are relatively prime.