Results 1 to 2 of 2

Math Help - Multiplication Principle

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Multiplication Principle

    Use the generalized multiplication principle to show that the set {1,2,...,n} has exactly 2^n subsets.

    Show that if you have a collection of 2^(n-1) + 1 subsets of {1,2,...,n}, then at least two of them are disjoint.

    Can someone show this please? Thanks. I don't have a clue...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45
    Hint :

    Consider for example A=\{1,2,3,4,5\} and the subsets B=\{2,5\}=\emptyset,A . Denote:

    B:\quad 01001

    \emptyset\;:\quad 00000

    A:\quad 11111

    ...


    Fernando Revilla
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: September 21st 2010, 06:13 PM
  2. Well ordering principle and the maximum principle
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: August 3rd 2010, 09:31 AM
  3. first principle help!!
    Posted in the Algebra Forum
    Replies: 1
    Last Post: January 18th 2010, 01:13 PM
  4. solve using the multiplication principle
    Posted in the Algebra Forum
    Replies: 6
    Last Post: December 10th 2009, 07:20 AM
  5. Momentum Principle and Energy Principle Problem
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: October 4th 2009, 02:42 AM

Search Tags


/mathhelpforum @mathhelpforum