[superprismatic]

Let N be a positive integer greater than 1.

Show that any subset of N+1 distinct positive

integers less than or equal to 2N contains at

least one pair of integers which are relatively

prime.

[Guest]

  Reveal hidden contents

it seems to me n+1 is always larger than 2n/ln(2n). so i suspect you must always pick at least 1 prime.

[Guest]

  Reveal hidden contents

For a (sub)set to not contain a pair of relatively prime numbers, every number would have to have a common factor. Given: N>1, a set of numbers, A, such that if x is in A 0<x<=2N and a subset of N+1 distinct x's from A. {Inserted assumption: For a set, B, of positive integers, y's, from 1 to Y and a prime number, p, B can contain at most floor(Y/p) distinct y's such that y is divisible by p.} So for every prime number, p, N+1>2N/p. So if you choose 2N/p items divisible by p there will always be at least one number that will not be divisible by p and therefore relatively prime with at least one number divisible by p.

[Guest]

  Reveal hidden contents

Any two consecutive integers are relatively prime. Therefore, to have no integers that are relatively prime, all integers would have to be at least 2 apart. Less than 2N, we can have N integers that are all at least 2 apart. However, we need N+1 integers less than 2N. Having already filled up the N spots of non-relative primes, the only place the last one can go is between two other integers, making it consecutive with them. Therefore, there will be two integers that are consecutive and relatively prime.

[superprismatic]

  On 1/12/2011 at 10:30 PM, rlgandy said:

  Reveal hidden contents

For a (sub)set to not contain a pair of relatively prime numbers, every number would have to have a common factor. Given: N>1, a set of numbers, A, such that if x is in A 0<x<=2N and a subset of N+1 distinct x's from A. {Inserted assumption: For a set, B, of positive integers, y's, from 1 to Y and a prime number, p, B can contain at most floor(Y/p) distinct y's such that y is divisible by p.} So for every prime number, p, N+1>2N/p. So if you choose 2N/p items divisible by p there will always be at least one number that will not be divisible by p and therefore relatively prime with at least one number divisible by p.

  Reveal hidden contents

The set {15,21,35} is a counterexample to your first assertion.

[superprismatic]

  On 1/12/2011 at 10:48 PM, sacohen0326 said:

  Reveal hidden contents

Any two consecutive integers are relatively prime. Therefore, to have no integers that are relatively prime, all integers would have to be at least 2 apart. Less than 2N, we can have N integers that are all at least 2 apart. However, we need N+1 integers less than 2N. Having already filled up the N spots of non-relative primes, the only place the last one can go is between two other integers, making it consecutive with them. Therefore, there will be two integers that are consecutive and relatively prime.

  Reveal hidden contents

except that you should have "less than or equal to 2N" wherever you have "less than 2N". It may seem pretty simple, but most people who understand the problem don't tend to look at it this way.

[Guest]

I was thinking on slightly different lines:

  Reveal hidden contents

so we are bound to have at least 1 odd and 1 even number which will be relatively prime (except when N=1)

[Guest]

  On 1/13/2011 at 4:53 AM, KlueMaster said:

I was thinking on slightly different lines:

  Reveal hidden contents

so we are bound to have at least 1 odd and 1 even number which will be relatively prime (except when N=1)

3 and 6 aren't relatively prime...