Jump to content
BrainDen.com - Brain Teasers
  • 0


superprismatic
 Share

Question

7 answers to this question

Recommended Posts

  • 0

  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.

Link to comment
Share on other sites

  • 0

  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.

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...