BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

Combination sum

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Master | Next Rank: 500 Posts
Posts: 231
Joined: Thu Apr 12, 2007 2:45 am
Thanked: 5 times
Followed by:1 members

Combination sum

by winnerhere » Mon Aug 17, 2009 3:05 am
Ten books are arranged in a row on a shelf.In how many ways can 3
books be selected simultaneously from the self such that no two
adjacent books from the shelf are chosen?

1) 36

2) 48

3) 42

4) 56

5) 84
Top
Source: — Problem Solving |
Legendary Member
Posts: 752
Joined: Sun May 17, 2009 11:04 pm
Location: Tokyo
Thanked: 81 times
GMAT Score:680

by tohellandback » Mon Aug 17, 2009 4:31 am
is it D) 56

what I did was:
lets take the case
aXbXcXd

where the three X's are the books and b and C must be atleast one book each. a and d can be 0 or more books

so equation is a+b+c+d=5
because 3X's and c and d are total 5 books. we are left with 5 books to arrange
a+b+c+d=5, where a,b,c,d can be 0 or more( we have already allotted one book each to b and c so now they can be 0)
answer is 8!/(5!*3!)=56
(if you don't understand this step, go here
https://www.beatthegmat.com/combination-t41362.html)
The powers of two are bloody impolite!!
Top
Master | Next Rank: 500 Posts
Posts: 231
Joined: Thu Apr 12, 2007 2:45 am
Thanked: 5 times
Followed by:1 members

by winnerhere » Mon Aug 17, 2009 8:41 am
Wonderful explanaton..especially the link u provided where Ian stewart has given a way to understand the combination sum

Thanks buddy :)
Top
User avatar
Master | Next Rank: 500 Posts
Posts: 157
Joined: Tue Oct 07, 2008 5:47 am
Thanked: 3 times

by PussInBoots » Mon Aug 17, 2009 3:37 pm
tohellandback
Could you explain your solution again?

My way of solving: rephrase the problem. We have 7 books on shelf and we need to insert 3 more, such that no 2 of those 3 are next to each other. We have 8 slots, hence 8C3.
-B B B B B B B
S S S S S S S S

B=Book
S=Slots between books
Top
Master | Next Rank: 500 Posts
Posts: 231
Joined: Thu Apr 12, 2007 2:45 am
Thanked: 5 times
Followed by:1 members

by winnerhere » Tue Aug 18, 2009 10:26 pm
PussInBoots wrote:tohellandback
Could you explain your solution again?

My way of solving: rephrase the problem. We have 7 books on shelf and we need to insert 3 more, such that no 2 of those 3 are next to each other. We have 8 slots, hence 8C3.
-B B B B B B B
S S S S S S S S

B=Book
S=Slots between books
Your method is also correct.But for indepth understandng let me explain the method put forth by those people above

1.You have to pick three books from 10 books

2.Those three books shouldnot be neighbours.

so between these three books there will be two slots(filled by one or more books) and to the left and right end there are two slots (with zero or more books).

slot1 book1 slot2 book2 slot3 book3 slot4

so slot1+slot2+slot3+slot4=7(remaining books) ----equation 1

slot2 and slot3 can take 1 or more books,not zero,as it is mandatory to have atleast one book between them.

slot1 and slot4 can have zero or more books (as one of the three books can occupy the left and right end)

we know that the number of positive integral solutions for

a1+a2+a3....+ar= n is n-1Cr-1

slot1 and slot2 must be made to be >=1

slo let A=slot1+1
B=slot4+1

so equation 1 becomes

A+slot2+slot3+D = 7 + 1 + 1 =9

therefore the number of different combinations is 8c3

8=9(constant on right hand side)-1
3=4(four dirrent variables)-1
Top
Post new topic Post Reply
• Page 1 of 1