[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]

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]

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]

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]

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.

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

[superprismatic]

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.

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:

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

[Guest]

I was thinking on slightly different lines:

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...