Results 1 to 2 of 2

Math Help - Subsets (2)

  1. #1
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Subsets (2)

    We want to select as many subsets of [n] as possible so that any two selected subsets have at least one element in common. What is the largest number of subsets we can select?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1

    Re: Subsets (2)

    I may commit a mistake in my working so please check it.

    Claim: There are at least 2^{n-1} ways of doing this.
    Proof: Consider the set A=\{2,3, \ldots, n\}. There are 2^{n-1} possible sunsets of this set.
    plug in the element 1 in each of the subsets of A and we will have 2^{n-1} subsets of [n] any two of which have 1 as a common element.

    Claim2: There are no more than 2^{n-1} ways of doing this.
    Proof: Suppose 2^{n-1} subsets are found out which satisfy the question's demand. If B is a subset then the complement of B cant appear in our list of subsets. So for each subset of [n] chosen there is one subset you can't choose namely its complement. Since we had chosen 2^{n-1} subsets, there are precisely 2^{n-1} subsets(complements of the chosen subsets) we can't chose. Since 2^{n-1}+2^{n-1}=2^n we see that we can't choose any more subsets as there were only 2^n possible subsets of [n].
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Subsets of R^3
    Posted in the Advanced Algebra Forum
    Replies: 11
    Last Post: May 14th 2011, 02:26 AM
  2. Subsets
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: December 29th 2010, 11:33 AM
  3. How many subsets
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 17th 2010, 06:41 AM
  4. Subsets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 1st 2009, 08:54 PM
  5. Subsets
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: October 22nd 2008, 01:58 AM

Search Tags


/mathhelpforum @mathhelpforum