Pigeon Hole Principle on a set of n elements

Question

Homework question:

It is asking us to prove that if we have $\frac{n}{2} + 1$ integers selected from a set$ A = {1, 2, ..., n}$, $n$ being an even integer, then the selection includes integers $x$ and $y$ such that the gcd of $x$ and $y$ is 1.

It seems like this is going to be really easy once I see it, but I'm not seeing it right now. It seems like I need to take all the numbers that can be formed from $2^m a$ where $a \in A$ since the gcd cof all of these elements is $ \ge 2 \ne 1$. The size of this set would be $\frac{n}{2} $. Therefore since there are 70 elements in this set if we select one more we will have to select it from out of this set.

I don't think this is right though since I am not seeing obvious pigeons or pigeon holes. Thanks in advance.

Answer 1

Hint: Two elements which are consecutive have GCD equal to 1.So if you select more than half two elements must be consecutive.

Answer 2

Make holes $\{1,2\}$, $\{3,4\}$, $\ldots$, $\{n-1,n\}$. Each of these $n/2$ pairs contains two numbers with gcd 1.