# Pigeon Hole Principle on a set of n elements

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.

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

• (+1).. this is a solution not a hint.
– Guy
Mar 14, 2014 at 6:16
• @Sabyasachi I still left pigeons and pigeon holes for evan to figure out Mar 14, 2014 at 6:17
• Well, from a mathematical perspective, you don't need to use pigeon holes and pigeons anymore. The way I see it that argument is sufficient.
– Guy
Mar 14, 2014 at 6:21
• @Sabyasachi yes as you have said my argument is enough but the second statement i made needs pigeon hole for justification Mar 14, 2014 at 6:23
• fair enough. it's obvious though. :D I guess I am seeing it this way because I only recently heard the term pigeonhole principle. I have been using it for ages(its obvious) but I never knew it had a name.
– Guy
Mar 14, 2014 at 6:25

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