1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Any subset

  1. Jul 29, 2007 #1
    i got this problem which is killin me :tongue:

    given a set {1,2,...,2n} choose any (n+1) element subset, show there exists an element which divides another element.
  2. jcsd
  3. Jul 29, 2007 #2


    User Avatar
    Staff Emeritus
    Science Advisor

    What's the actual question? Are you asked to choose a subset of {1,2,...,2n} containing n+1 elements such that at least one element divides at least one other? I guess it isn't, since an answer to this is pretty obvious isn't it?
  4. Jul 29, 2007 #3
    The problem is asking, I assume, that is you choose any n+1 element subset then there exists two elements a and b so that a|b.

    Proof. Any number from {1,2,...,2n} can be uniquely expressed as [tex]2^pq[/tex] where p is a non-negative integer and q is an (odd) positive integer.
    Define the sets:
    T_1 = {2^p * 1 }
    T_2 = {2^p * 2 }
    T_n = {2^p * n}
    So we partitioned the set into n sets. By the pigeonhole principle two elements end up in the same set T_j, but we purposely defined these sets in such a way so that one divides the other.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook