• 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

Sub sets probability

This topic has expert replies
Legendary Member
Posts: 641
Joined: 14 Feb 2012
Thanked: 11 times
Followed by:8 members

Sub sets probability

by gmattesttaker2 » Sat Jan 11, 2014 4:30 pm
Hello,

Can you please assist with this:

The subsets of set {s,u,t} are {s},{u},{t},{su},{st},{ut},{s,u,t},and the
empty set { }. How many of the subsets of set {s,u,t,w, x}do NOT contain element t?

(A) 13
(B) 14
(C) 15
(D) 15
(E) 16

OA: E

Thanks a lot,
Sri

GMAT/MBA Expert

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

by Brent@GMATPrepNow » Sat Jan 11, 2014 4:48 pm
gmattesttaker2 wrote:Hello,

Can you please assist with this:

The subsets of set {s,u,t} are {s},{u},{t},{su},{st},{ut},{s,u,t},and the
empty set { }. How many of the subsets of set {s,u,t,w, x}do NOT contain element t?

(A) 13
(B) 14
(C) 15
(D) 15
(E) 16
This is very similar to this question: https://www.beatthegmat.com/combinatoric ... 73180.html


Here's one approach:

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

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

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

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

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

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

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

Cheers,
Brent

Aside: For more information about the FCP, watch our free video: https://www.gmatprepnow.com/module/gmat-counting?id=775
Brent Hanneson - Creator of GMATPrepNow.com
Use my video course along with Beat The GMAT's free 60-Day Study Guide
Image
Sign up for free Question of the Day emails
And check out all of these free resources

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

by vipulgoyal » Sun Jan 12, 2014 11:04 pm
first approach
no of subsets in any set are 2^n where n is the number of elements in given set
just remove t from superset and now new set have 4 elements therefore no of subsets = 2^4 = 16

second approach
just remove t from superset and now new set have 4 elements therefore no of subsets
with one element 4c1 + with 2 4c2+ with 3 4c3 + with 4 4c4 + 1empty set = 16

GMAT/MBA Expert

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

by Brent@GMATPrepNow » Mon Jan 13, 2014 6:45 am
vipulgoyal wrote:first approach
no of subsets in any set are 2^n where n is the number of elements in given set
just remove t from superset and now new set have 4 elements therefore no of subsets = 2^4 = 16

second approach
just remove t from superset and now new set have 4 elements therefore no of subsets
with one element 4c1 + with 2 4c2+ with 3 4c3 + with 4 4c4 + 1empty set = 16
vipulgoyal's solution demonstrates a useful property regarding sums of combinations:
nC0 + nC1 + nC2 + . . . . nCn = 2^n

So, for this question, we have: 4C0 + 4C1 + 4C2 + 4C3 + 4C4 = 2^4 = 16
Likewise, 5C0 + 5C1 + 5C2 + 5C3 + 5C4 + 5C5 = 2^5
And 7C0 + 7C1 + 7C2 + . . . 7C6 + 7C7 = 2^7
etc.

Cheers,
Brent
Brent Hanneson - Creator of GMATPrepNow.com
Use my video course along with Beat The GMAT's free 60-Day Study Guide
Image
Sign up for free Question of the Day emails
And check out all of these free resources

Newbie | Next Rank: 10 Posts
Posts: 6
Joined: 06 Feb 2016

by konan » Sat Feb 06, 2016 1:12 am
why not the answer can be 13??
as we have 7 subsets of {s,u,t} and if we list all the subsets of {s,u,t,w,x} the total number of subsets are 16. by excluding the subsets which contain t, we get the answer 13.

User avatar
Legendary Member
Posts: 2073
Joined: 03 Feb 2014
Location: New York City Metro Area and Worldwide Online
Thanked: 955 times
Followed by:135 members
GMAT Score:800

by Marty Murray » Sat Feb 06, 2016 5:33 am
konan wrote:why not the answer can be 13??
as we have 7 subsets of {s,u,t} and if we list all the subsets of {s,u,t,w,x} the total number of subsets are 16. by excluding the subsets which contain t, we get the answer 13.
Here's the list.

{} {s} {u} {w} {x} {su} {sw} {sx} {uw} {ux} {wx} {suw} {sux} {swx} {uwx} {suwx}

Which ones did you miss? I didn't think of {suwx} at first myself.
Marty Murray
GMAT Coach
m.w.murray@hotmail.com
https://infinitemindprep.com/
In Person in the New York Area and Online Worldwide

GMAT/MBA Expert

GMAT Instructor
Posts: 2630
Joined: 12 Sep 2012
Location: East Bay all the way
Thanked: 625 times
Followed by:117 members
GMAT Score:780

by Matt@VeritasPrep » Mon Feb 08, 2016 9:15 am
konan wrote:why not the answer can be 13??
as we have 7 subsets of {s,u,t} and if we list all the subsets of {s,u,t,w,x} the total number of subsets are 16. by excluding the subsets which contain t, we get the answer 13.
There are 32 subsets of {s, u, t, w, x}: for each subset, we have two choices (s is in or s in out, t is in or t is out, etc.), which gives us 2� or 32 subsets. (If you don't want to consider {s, u, t, w, x} itself, you could say there are 31 proper subsets, but 32 is still the correct answer.)

Junior | Next Rank: 30 Posts
Posts: 11
Joined: 09 Nov 2010
Thanked: 1 times

by gary391 » Tue Aug 23, 2016 10:26 am
Using combination i.e. "selection" logic.

No. of ways to select Subset that doesn't contain t = (All subset) - (Subset always contains t) ---(1)

All Subset = 5C5 + 5C4 + 5C3 + 5C2 + 5C1 = 1 + 5 + 10 + 10 + 5 = 31

Subset always contains t = 4C4 +4C3 + 4C2 + 4C1 = 1 + 4 + 6 + 4 = 15

From (1), Answer is 16.

User avatar
Legendary Member
Posts: 2666
Joined: 14 Jan 2015
Location: Boston, MA
Thanked: 1153 times
Followed by:125 members
GMAT Score:770

by DavidG@VeritasPrep » Tue Aug 23, 2016 11:17 am
You can also use the same logic Matt uses for the full set. If you exclude t, you'd have 4 elements in the set. You have 2 options for each element: in or out of the set. 2^4 = 16.
Veritas Prep | GMAT Instructor

Veritas Prep Reviews
Save $100 off any live Veritas Prep GMAT Course

GMAT/MBA Expert

GMAT Instructor
Posts: 2630
Joined: 12 Sep 2012
Location: East Bay all the way
Thanked: 625 times
Followed by:117 members
GMAT Score:780

by Matt@VeritasPrep » Thu Sep 01, 2016 6:08 pm
Just realized there's a blunderous typo in my post:
There are 32 subsets of {s, u, t, w, x}: for each subset, we have two choices


is technically correct, I suppose, but not in the sense I intended. I meant to say
There are 32 subsets of {s, u, t, w, x}: for each element in the set, we have two choices
My bad if that confused anybody, I know this is hard enough to follow as is!