## Solution #022 - coprimes in the crowd

167

This post contains my proposed solution to Problem #022 - coprimes in the crowd. Please do not read this solution before making a serious attempt at the problem.

### Solution

The solution is a simple application of the pigeonhole principle.

For some $$n \geq 2$$, consider the following $$n-1$$ pairs of integers:

$\{3, 4\}, \{5, 6\}, \cdots, \{2n-1, 2n\}$

which together make up for the whole set $$\{3, 4, \cdots, 2n-1, 2n\}$$. If we pick $$n$$ numbers from this set (the pigeons) and if we look for the pairs from where they came (the holes) then we see we must have picked two consecutive integers from one of the pairs. Those two numbers that came from the same pair are consecutive integers, and hence are coprime!

To see that two consecutive integers are coprime, you can read this twitter proof.