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!

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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted