1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ (+1).. this is a solution not a hint. $\endgroup$ – Guy Mar 14 '14 at 6:16
  • 1
    $\begingroup$ @Sabyasachi I still left pigeons and pigeon holes for evan to figure out $\endgroup$ – happymath Mar 14 '14 at 6:17
  • $\begingroup$ 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. $\endgroup$ – Guy Mar 14 '14 at 6:21
  • 1
    $\begingroup$ @Sabyasachi yes as you have said my argument is enough but the second statement i made needs pigeon hole for justification $\endgroup$ – happymath Mar 14 '14 at 6:23
  • $\begingroup$ 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. $\endgroup$ – Guy Mar 14 '14 at 6:25
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.