Solution

Consider the first $2n$ integers, $1, 2, 3, \ldots, 2n$. If more than $n$ of these integers are selected, show that two of the selected integers must be relatively prime.


We can argue with the pigeon-hole principle...

Consider the sets $\{1,2\}, \{3,4\}, \{5,6\}, \ldots \{2n-1,2n\}$. These sets will be our "pigeon-holes". For any one of these sets, say $\{a,a+1\}$, we note that $a$ and $a+1$ have to be relatively prime. To see this, suppose $d$ was a positive integer divisor of both. Then $$\begin{array}{rcl} d \mid a \textrm{ and } d \mid a+1 &\Rightarrow& d \mid (a+1) - a\\ &\Rightarrow& d \mid 1\\ &\Rightarrow& d = 1 \end{array}$$

So we have $n$ sets that each consist of two relatively prime numbers. If we select more than $n$ of the integers from $1$ to $2n$ (these are our "pigeons"), then by the pigeon-hole principle, one of the sets must contain two of the selected integers. Since these two integers must then be relatively prime, we are done.

QED.