It is currently 14 Dec 2017, 05:22

Decision(s) Day!:

CHAT Rooms | Wharton R1 | Stanford R1 | Tuck R1 | Ross R1 | Haas R1


Close

GMAT Club Daily Prep

Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track
Your Progress

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

Not interested in getting valuable practice questions and articles delivered to your email? No problem, unsubscribe here.

Close

Request Expert Reply

Confirm Cancel

Events & Promotions

Events & Promotions in June
Open Detailed Calendar

Combinatorics Made Easy!

  new topic post reply Question banks Downloads My Bookmarks Reviews Important topics  
Author Message
TAGS:

Hide Tags

Director
Director
avatar
S
Joined: 21 Mar 2016
Posts: 542

Kudos [?]: 7 [0], given: 98

Reviews Badge CAT Tests
Re: Combinatorics Made Easy! [#permalink]

Show Tags

New post 04 Jul 2017, 21:17
Question 4 : same as question 3,,,answer shud be 512

Kudos [?]: 7 [0], given: 98

Manager
Manager
avatar
B
Joined: 07 Jun 2017
Posts: 110

Kudos [?]: 3 [0], given: 454

Re: Combinatorics Made Easy! [#permalink]

Show Tags

New post 05 Jul 2017, 19:31
I think my head burned but I still don't get the explanation to question #3.

"You have 10 different paintings. Each painting can be given to one of the 2 people in 2 ways. You do that with 9 paintings in 2*2*2… = 2^9 ways. When you distribute 9 paintings, one person will have odd number of paintings and one will have even number of paintings (0 + 9 or 1 + 8 or 2 + 7 or 3 + 6 or 4 + 5).

The tenth painting needs to be given to the person who has the odd number of paintings so you give the tenth painting in only one way. This accounts for all cases in which both get even number of paintings."

Why 2^9? i can't see it connected to 10 paintings

Kudos [?]: 3 [0], given: 454

Intern
Intern
avatar
B
Joined: 30 Aug 2017
Posts: 22

Kudos [?]: 2 [0], given: 45

Concentration: Real Estate, Operations
CAT Tests
Re: Combinatorics Made Easy! [#permalink]

Show Tags

New post 15 Oct 2017, 10:09
1
This post was
BOOKMARKED
Bunuel wrote:
The Dreaded Combinatorics

BY KARISHMA, VERITAS PREP


The first thing I want to discuss is something we call “Basic Counting Principle” because it is useful in almost all 600-700 level questions of Combinatorics (Note here that I will avoid using the terms “Permutation” and “Combination” and the formulas associated with them since they are not necessary and make people uncomfortable). Also, many of the 700+ level questions use basic counting principle as the starting point so it’s not possible to start a discussion on combinatorics without discussing this principle first. Let’s try to understand it using an example.

Example 1: There are 3 boys and 2 girls. We want to select a pair of one boy and one girl for a dance. In how many ways can we do it?

Solution: Let’s discuss the solution in detail. This is a very basic and very important concept.

Say the 3 boys are B1, B2 and B3. Say the 2 girls are G1 and G2.

In how many ways can you make a pair?

B1 – G1

B1 – G2

B2 – G1

B2 – G2

B3 – G1

B3 – G2

A total of 6 ways. We see that we can select a boy in 3 ways (since there are 3 boys) and we can select a girl in 2 ways (since there are 2 girls). So we can make a pair in 3*2 = 6 ways.

The basic counting principle deals with problems having ‘distinct spots’ and ‘available contenders’. Here we have 1 spot for a boy and 1 spot for a girl i.e. 2 distinct spots. There are 3 contenders for the empty ‘boy spot’ and 2 contenders for the empty ‘girl spot’. These spots can be filled in 3*2 = 6 ways. The word ‘distinct’ is important here as we will see in the next few weeks.

Also notice here that it is not 3+2 = 5 ways. This is so because we have to choose a boy AND a girl simultaneously. For every boy, we could choose a girl in 2 ways and there are 3 boys so we can choose a pair in 3*2 ways. If we had to choose one boy OR one girl (i.e. just one person), we could have done it in 3+2 = 5 ways because there are 5 people and we have to choose one of them. The distinction between ‘AND’ and ‘OR’ is quite important since it defines whether you will multiply or add.

Let’s look at some more examples of basic counting principle.

Example 2: A restaurant serves 6 varieties of appetizers, 10 different entrees and 4 different desserts. In how many ways can one make a meal if one chooses one appetizer, one entree and one dessert?

Solution: In how many ways can you choose an appetizer? 6 ways

In how many ways can you choose your entree? 10 ways

In how many ways can you choose your dessert? 4 ways

In how many different ways can you make your meal? To make your meal, you need one appetizer AND one entree AND one dessert. There are 3 distinct spots and you have to fill each one of them. You can do it in 6*10*4 = 240 ways.

Example 3: In how many ways can you make a five letter password using the first ten letters of the English alphabet? (You can use only capital letters.)

Solution: In how many ways can you choose the first letter of the password? 10 ways. You can put in any letter from A to J.

What about the second letter? Again, you can choose it in 10 ways. The question doesn’t say that you cannot repeat a letter once you use it.

Similarly, each digit can be chosen in 10 ways.

Since you have to choose the first letter AND the second letter AND the third letter etc, the total number of ways of selecting a five letter password is 10*10*10*10*10 = 10^5 ways. You have 5 distinct spots and you can fill each one of them in 10 ways.

You can make the 5 letter password in 10^5 ways.

Example 4: Five friends go to watch a movie. They are supposed to occupy seat numbers 51 to 55. In how many different ways can they do it?

Solution: Let’s look at the first seat i.e. seat number 51. In how many ways can you make someone sit there? Of course 5 ways since you have 5 people. Say, you make one of them sit on seat number 51. Now in how many ways can you make someone sit on seat number 52? Remember that you have only 4 contenders left now since one of them is already sitting on seat number 51. Therefore, you can make someone sit there in 4 ways only. Next, for seat number 53, you only have 3 contenders left. For seat number 54, you have only 2 contenders left and then for seat number 55, only the last person is remaining i.e. just one option.

The total number of ways of arranging 5 people on 5 distinct seats is 5*4*3*2*1 = 120

These are some of the most basic examples of basic counting principle. Below, I am giving more questions which are just twists on these questions. Try them and get back if you have any doubts. We will take some higher level concepts from next post on.

Question 1: A restaurant serves 6 varieties of appetizers, 10 different entrees and 4 different desserts. In how many ways can one make a meal if one chooses an appetizer, at least one and at most two different entrees and one dessert?

Question 2: In how many ways can you make a five digit password using the first ten letters of the English alphabet if each letter can be used at most once? (You can use only capital letters.)

Question 3: In how many ways can BRIAN make a five digit password using the first ten letters of the English alphabet if each letter can be used at most once and one is not allowed to use any letter which appears in one’s name? (You can use only capital letters.)

Question 4: Six friends go to watch a movie. They are supposed to occupy seat numbers 51 to 56. However one of them falls sick and returns home. In how many different ways can the 5 people sit?

Question 5: Eight friends go to watch a movie but only 5 tickets were available. In how many different ways can 5 people sit and watch the movie?


Solutions to the questions (from veritas prep site- https://www.veritasprep.com/blog/2011/1 ... inatorics/):

1. 6*10*4 + 6*(10*9)/2 * 4 (Choose one entree or two but do not arrange entrees in case you select two)

2. 10*9*8*7*6 (First digit selected in 10 ways, second digit in 9 ways etc)

3. 7*6*5*4*3 (Out of first ten letterns, Brian cannot use A, B and I)

4. 6*5*4*3*2 (Allot the seats to the friends say the first friend has 6 seat options, second friend has 5 seat options etc)

5. 8*7*6*5*4 (First seat can be filled in 8 ways, second seat in 7 ways etc)

Kudos [?]: 2 [0], given: 45

Intern
Intern
avatar
B
Joined: 14 Dec 2012
Posts: 12

Kudos [?]: 5 [0], given: 5

Location: India
GMAT ToolKit User
Combinatorics Made Easy! [#permalink]

Show Tags

New post 08 Nov 2017, 05:16
Now let’s discuss some trickier variations of this question.

Question 3: 7 people, A, B, C, D, E, F and H, go to a movie and sit next to each other in 8 adjacent seats in the front row of the theatre. A and F will not sit next to each other in how many different arrangements?

Solution: Here, there is an additional vacant spot since there are only 7 people but 8 seats. You might think that it is a little confusing since you will need to deal with the vacant spot separately. Actually, this be done in a very straight forward way.

7 people including A and F have to be seated such that A and F are not next to each other. So an arrangement where A and F have the vacant spot between them is acceptable. I will just imagine that there is an invisible person called Mr. V. He takes the vacant spot. If A and F have V between them, that arrangement is acceptable to us. Now this question is exactly like the question above. We have 8 people sitting in 8 distinct seats. 8 people (including our imaginary Mr. V) can sit in 8 seats in 8! arrangements.

A and F can sit together in 2*7! arrangements (similar to question no. 2)

Hence, the number of arrangements in which A and F will not sit together = 8! – 2*7!

Does the solution cover the scenario where A and F will be seated at two extreme ends of the row?

Kudos [?]: 5 [0], given: 5

Combinatorics Made Easy!   [#permalink] 08 Nov 2017, 05:16

Go to page   Previous    1   2   [ 24 posts ] 

Display posts from previous: Sort by

Combinatorics Made Easy!

  new topic post reply Question banks Downloads My Bookmarks Reviews Important topics  


GMAT Club MBA Forum Home| About| Terms and Conditions| GMAT Club Rules| Contact| Sitemap

Powered by phpBB © phpBB Group | Emoji artwork provided by EmojiOne

Kindly note that the GMAT® test is a registered trademark of the Graduate Management Admission Council®, and this site has neither been reviewed nor endorsed by GMAC®.