Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Choose subset of n+1 from 2n set

  1. Mar 16, 2008 #1

    xax

    User Avatar

    Every subset of n+1 from a 2n set has a pair of numbers with gcd=1. How can I prove this?
     
  2. jcsd
  3. Mar 16, 2008 #2
    Well, you can't because it's not true. For example let [tex]S = \left\{2, 4, 6, 8\right\} [/tex].
     
  4. Mar 16, 2008 #3
    I think what xax meant was this:
    Given is the set of integers from 1 to 2n. If you choose n+1 numbers from this set there is always a pair of numbers (among these n+1 numbers) with gcd=1.
     
    Last edited: Mar 16, 2008
  5. Mar 16, 2008 #4

    xax

    User Avatar

    Edgardo, you're right.
     
  6. Mar 16, 2008 #5
    Well that makes more sense!

    Xax, given any natural number, b, what is the gcd(b, b+1)? In your subset of size n+1 must there be a pair of the form {b, b+1}?
     
  7. Mar 17, 2008 #6

    xax

    User Avatar

    Thank you both, but I solved it using pigeonhole principle and the fact that gcd(n,n+1)=1
     
  8. Mar 17, 2008 #7
    but the first counter example of rodigee is correct since the property this is true if and only if the set elements can be ordered sucht that the diference between consective numbers is equal to 1
     
    Last edited: Mar 17, 2008
  9. Apr 10, 2008 #8
    cause n+1 numbers in 1..2n includes 2 consecutive ones, whose gcd is 1
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Choose subset of n+1 from 2n set
Loading...