1

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.

Kailas
  • 241
  • 1
  • 7
Evan
  • 375

2 Answers2

4

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

happymath
  • 6,148
  • (+1).. this is a solution not a hint. – Guy Mar 14 '14 at 06:16
  • 1
    @Sabyasachi I still left pigeons and pigeon holes for evan to figure out – happymath Mar 14 '14 at 06: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 '14 at 06:21
  • 1
    @Sabyasachi yes as you have said my argument is enough but the second statement i made needs pigeon hole for justification – happymath Mar 14 '14 at 06: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 '14 at 06:25
  • That is an issue with these problems. Either you see it or you don't. Any hint seems to give the answer away. Thank you User 129901. I did generalize the problem in the homework to use n instead of the numbers, but it is really the same thing. – Evan Mar 14 '14 at 06:27
1

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

user133281
  • 16,073