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