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$

2 Answers 2

Reset to default
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, 2014 at 6:16
  • 1
    $\begingroup$ @Sabyasachi I still left pigeons and pigeon holes for evan to figure out $\endgroup$
    – happymath
    Mar 14, 2014 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, 2014 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, 2014 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, 2014 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.