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

Subsets of a set such that no two have two equal elements

  1. Nov 13, 2011 #1
    1. The problem statement, all variables and given/known data
    Given a set of n elements one after another (1,2,....n) Find the minimum n for which there are about 1000 subsets such that every two subsets will have at least 2 elements not in common

    2. Relevant equations

    3. The attempt at a solution

    I did this problem for 1 element not in common and I got n C (n/2)=1000 so n is around 12 or 13 which means that for n=13, we can take a subset with cardinality 6 or 7 such that no two of the subsets will have all the same elements...This answer was right.
    Saying n=24 or 26 will result in a sufficient number to guarantee every 2 subsets will have alteast 2 elements not in common, but I don't know if it will be the minimum number
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?