• 7 CATs FREE!
    If you earn 100 Forum Points

    Engage in the Beat The GMAT forums to earn
    100 points for $49 worth of Veritas practice GMATs FREE

    Veritas Prep
    VERITAS PRACTICE GMAT EXAMS
    Earn 10 Points Per Post
    Earn 10 Points Per Thanks
    Earn 10 Points Per Upvote
    REDEEM NOW

Combinatorics problem

This topic has expert replies
Master | Next Rank: 500 Posts
Posts: 103
Joined: 02 Jun 2012
Thanked: 1 times

Combinatorics problem

by topspin360 » Sat Jan 04, 2014 10:29 am
Can someone please solve the following:

How many different subsets of the set {0, 1, 2, 3, 4, 5} do not contain 0?

A) 16
B) 27
C) 31
D) 32
E) 64

OA is D

User avatar
Legendary Member
Posts: 1556
Joined: 14 Aug 2012
Thanked: 448 times
Followed by:34 members
GMAT Score:650

by theCodeToGMAT » Sat Jan 04, 2014 10:36 am
(6c6 + 6c5 + 6c4 + 6c3 + 6c2 + 6c1) - (5c5 + 5c4 + 5c3 + 5c2 + 5c1)

= (1 + 6 + 3x5 + 5x4 + 3x5 + 6) - (1 + 5 + 5x2 + 5x2 + 5)

= (7 + 15 + 20 + 15 + 6) - (6 + 10 + 10 + 5)

= 63 - 31

= 32
R A H U L

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 14172
Joined: 08 Dec 2008
Location: Vancouver, BC
Thanked: 5254 times
Followed by:1259 members
GMAT Score:770

by Brent@GMATPrepNow » Sat Jan 04, 2014 12:28 pm
topspin360 wrote:
How many different subsets of the set {0, 1, 2, 3, 4, 5} do not contain 0?

A) 16
B) 27
C) 31
D) 32
E) 64
Here's another approach...

Take the task of building subsets and break it into stages.

Stage 1: Determine whether or not to place "0" in the subset
The question tells us that "0" cannot be in the subset.
So, we can complete stage 1 in 1 way (that is, we DO NOT place "0" in the subset

Stage 2: Determine whether or not to place "1" in the subset
We can either HAVE "1" in the subset or NOT HAVE "1" in the subset
So, we can complete stage 2 in 2 ways

Stage 3: Determine whether or not to place "2" in the subset
We can either HAVE "2" in the subset or NOT HAVE "2" in the subset
So, we can complete this stage in 2 ways

Stage 4: Determine whether or not to place "3" in the subset
We can either HAVE "3" in the subset or NOT HAVE "3" in the subset
So, we can complete this stage in 2 ways

Stage 5: Determine whether or not to place "4" in the subset
We can complete this stage in 2 ways

Stage 6: Determine whether or not to place "5" in the subset
We can complete this stage in 2 ways

By the Fundamental Counting Principle (FCP), we can complete all 6 stages (and thus build all possible subsets ) in (1)(2)(2)(2)(2)(2) ways ([spoiler]= 32 ways = D[/spoiler])

Cheers,
Brent

Aside: For more information about the FCP, watch our free video: https://www.gmatprepnow.com/module/gmat-counting?id=775
Last edited by Brent@GMATPrepNow on Sat Jan 11, 2014 4:49 pm, edited 1 time in total.
Brent Hanneson - Creator of GMATPrepNow.com
Use my video course along with Beat The GMAT's free 60-Day Study Guide
Image
Watch these video reviews of my course
And check out these free resources

Master | Next Rank: 500 Posts
Posts: 468
Joined: 25 Jul 2011
Thanked: 29 times
Followed by:4 members

by vipulgoyal » Mon Jan 06, 2014 10:29 pm
alt way

(5c5 + 5c4 + 5c3 + 5c2 + 5c1) + 1 empty set
31+1=32