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.