Combinatorics  Rajesh Balasubramanian  CAT 100th Percentile  CAT 2011, 2012 and 2014  Part (1/2)

rajesh_balasubramanian
Director, 2IIM Online CAT Preparation  IIT Madras  IIM Bangalore  CAT 100th percentile  CAT 2011, 2012 and 2014.
This section hosts a number of CAT Level questions on Permutation and Combination, and Probability.
Counting Natural Numbers:
Sum of three Natural numbers a, b and c is 10. How many ordered triplets (a, b, c) exist?
45
36
54
28a + b + c = 10. Now, let us place ten sticks in a row
         
This question now becomes the equivalent of placing two '+' symbols somewhere between these sticks. For instance
    +      + 
This would be the equivalent of 4 + 5 + 1. or, a = 4, b = 5, c = 1.
There are 9 slots between the sticks, out of which one has to select 2 for placing the '+'s.
The number of ways of doing this would be 9C2. Bear in mind that this kind of calculation counts ordered triplets. (4, 5, 1) and (1, 4, 5) will both be counted as distinct possibilities.
We can also do a + b + c = n where a, b, c have to be whole numbers (instead of natural numbers as in this question) with a small change to the above approach. Give it some thought.Counting Whole Numbers:
Sum of three Whole numbers a, b and c is 10. How many ordered triplets (a, b, c) exist?
66
78
72
56a + b + c = 10. a, b, c are whole numbers. Now this is similar to the previous question that we solved by placing 10 sticks and simplifying. We cannot follow an exactly similar approach, as in this case a, b and c can be zero. Let us modify the approach a little bit. Let us see if we can remove the constraint that a, b, c can be zero.
If we give a minimum of 1 to a, b, c then the original approach can be used. And then we can finally remove 1 from each of a, b, c. So, let us distribute 13 sticks across a, b and c and finally remove one from each.
a + b + c = 13. Now, let us place ten sticks in a row
            
This question now becomes the equivalent of placing two '+' symbols somewhere between these sticks. For instance
    +      +    ,
This would be the equivalent of 4 + 5 + 4. or, a = 4, b = 5, c = 4.
There are 12 slots between the sticks, out of which one has to select 2 for placing the '+'s.
The number of ways of doing this is 12C2.Counting  Toys and Boxes
In how many ways 11 identical toys be placed in 3 distinct boxes such that no box is empty?
72
54
45
36This is nothing but the number of ways of having a, b, c such that a + b + c = 11, where a, b, c are natural numbers. By having them to be natural numbers, we ensure that no box can be empty (no zeroes)
The question is similar to the previous one.
Correct Answer : 10C2 = 45Permutation Combination Puzzle
a, b, c are three distinct integers from 2 to 10 (both inclusive). Exactly one of ab, bc and ca is odd. abc is a multiple of 4. The arithmetic mean of a and b is an integer and so is the arithmetic mean of a, b and c. How many such triplets are possible (unordered triplets)?
8
6
2
4Exactly one of ab, bc and ca is odd => Two are odd and one is even
abc is a multiple of 4 => the even number is a multiple of 4
The arithmetic mean of a and b is an integer => a and b are odd
and so is the arithmetic mean of a, b and c. => a+ b + c is a multiple of 3
c can be 4 or 8.
c = 4; a, b can be 3, 5 or 5, 9
c = 8; a, b can be 3, 7 or 7, 9
Four triplets are possible.Counting 7 Digit Numbers
A sevendigit number comprises of only 2's and 3's. How many of these are multiples of 12?
11
12
10
22Number should be a multiple of 3 and 4. So, the sum of the digits should be a multiple of 3. WE can either have all seven digits as 3, or have three 2's and four 3's, or six 2's and a 3. (The number of 2's should be a multiple of 3).
For the number to be a multiple of 4, the last 2 digits should be 32. Now, let us combine these two.
All seven 3's  No possibility.
Three 2's and four 3's  The first 5 digits should have two 2's and three 3's in some order. No of possibilities = 5!/3!2! = 10
Six 2's and one 3  The first 5 digits should all be 2's. So, there is only one number 2222232.
So, there are a total of 10 + 1 = 11 solutions.Alphabetical Order
If all words with 2 distinct vowels and 3 distinct consonants were listed alphabetically, what would be the rank of “ACDEF’?
4716
4720
4718
1717The first word would be ABCDE. With 2 distinct vowels, 3 distinct consonants, this is the first word we can come up with.
Starting with AB, we can have a number of words.
AB __ __ __. The next three slots should have 2 consonants and one vowel. This can be selected in 20C2 and 4C1 ways. Then the three distinct letters can be rearranged in 3! Ways.
Or, number of words starting with AB = 20C2 * 4C1 * 3! = 190 * 4 * 6 = 4560
Next, we move on to words starting with ACB
ACB __ __. The last two slots have to be filled with one vowel and one consonant. = 19C1 * 4C1. This can be rearranged in 2! Ways.
Or, number of words starting with ACB = 19C1 * 4C1 * 2 = 19 * 4 * 2 = 152
Next we move on words starting with ACDB: There are 4 different words on this list – ACDBE, ACDBI, ACDBO, ACDBU
So far number of words gone = 4560 + 152 + 4 = 4716
Starting with AB 4560
Starting with ACB 152
Starting with ACDB 4
Total words gone 4716
After this we move to words starting with ACDE, the first possible word is ACDEB. After this we have ACDEF.
So, rank of ACDEF = 4718Combinatorics Basics
If we listed all numbers from 100 to 10,000, how many times would the digit 3 be printed?
3980
3700
3840
3780We need to consider all three digit and all 4digit numbers.
Threedigit numbers: A B C. 3 can be printed in the 100’s place or 10’s place or units place.
=> 100’s place: 3 B C. B can take values 0 to 9, C can take values 0 to 9. So, 3 gets printed in the 100’s place 100 times
=> 10’s place: A 3 C. A can take values 1 to 9, C can take values 0 to 9. So, 3 gets printed in the 10’s place 90 times
=> Unit’s place: A B 3. A can take values 1 to 9, B can take values 0 to 9. So, 3 gets printed in the unit’s place 90 times
So, 3 gets printed 280 times in 3digit numbers
Fourdigit numbers: A B C D. 3 can be printed in the 1000’s place, 100’s place or 10’s place or units place.
=> 1000’s place: 3 B C D. B can take values 0 to 9, C can take values 0 to 9, D can take values 0 to 9. So, 3 gets printed in the 100’s place 1000 times.
=> 100’s place: A 3 C D. A can take values 1 to 9, C & D can take values 0 to 9. So, 3 gets printed in the 100’s place 900 times.
=> 10’s place: A B 3 D. A can take values 1 to 9, B & D can take values 0 to 9. So, 3 gets printed in the 10’s place 900 times.
=> Unit’s place: A B C 3. A can take values 1 to 9, B & C can take values 0 to 9. So, 3 gets printed in the unit’s place 900 times.
3 gets printed 3700 times in 4digit numbers.
So, there are totally 3700 + 280 = 3980 numbers.Number Systems  Combinatorics
From the digits 2, 3, 4, 5, 6 and 7, how many 5digit numbers can be formed that have distinct digits and are multiples of 12?
36
60
84
72Any multiple of 12 should be a multiple of 4 and 3. First, let us look at the constraint for a number being a multiple of 3. Sum of the digits should be a multiple of 3. Sum of all numbers from 2 to 7 is 27. So, if we have to drop a digit and still retain a multiple of 3, we should drop either 3 or 6.
So, the possible 5 digits are 2, 4, 5, 6, 7 or 2, 3, 4, 5, 7.
When the digits are 2, 4, 5, 6, 7. the last two digits possible for the number to be a multiple of 4 are 24, 64, 52, 72, 56, 76. For each of these combinations, there are 6 different numbers possible. So, with this set of 5 digits we can have 36 different numbers.
When the digits are 2, 3, 4, 5, 7. The last two digits possible for the number to be a multiple of 4 are 32, 52, 72, 24. For each of these combinations, there are 6 different numbers possible. So, with this set of 5 digits we can have 24 different numbers.
Overall, there are 60 different 5digit numbers possibleNumbers in Different Bases
All numbers from 1 to 200 (in decimal system) are written in base 6 and base 7 systems. How many of the numbers will have a nonzero units digit in both base 6 and base 7 notations?
143
200
157
122If a number written in base 6 ends with a zero, it should be a multiple of 6. In other words, the question wants us to find all numbers from 1 to 200 that are not multiples of 6 or 7. There are 33 multiples of 6 less than 201. There are 28 multiples of 7 less than 201. There are 4 multiples of 6 & 7 (or multiple of 42) from 1 to 200.
So, total multiples of 6 or 7 less than 201 = 33 + 28  4 = 57.
Number of numbers with nonzero units digit = 200  57 = 143.NonZero Numbers
All numbers from 1 to 150 (in decimal system) are written in base 6 notation. How many of these will contain zero's?
25
20
35
45Any multiple of 6 will end in a zero. There are 25 such numbers. Beyond this, we can have zero as the middle digit of a 3digit number.
This will be the case for numbers from 37  41, 73  77, 109  113 and 145  149. There are 20 such numbers.
Overall, there are 45 numbers that have a zero in them.5 Digit Numbers
How many numbers of up to 5 digits can be created using the digits 1, 2, 3 and 5 each at least once such that they are a multiple of 15?
24
18
15
12For a number to be a multiple of 15, it has to be a multiple of 3 and of 5. So, the last digit has to be 5 and the sum of digits should be a multiple of 3.
We can have either 4–digit or 5–digit numbers. If we have a 4–digit number, sum of the digits will be 1 + 2 + 3 + 5 = 11. No 4–digit number formed with digits 1, 2, 3, 5 exactly once can be a multiple of 3. So, there is no possible 4–digit number.
Now, in any 5 digit number, we will have 1, 2, 3, 5 once and one of these 4 digits repeating once. 1 + 2 + 3 + 5 = 11. So, the digit that repeats in order for the number to be a multiple of 3 has to be 1. In this instance, sum of the digits will be 12 and this is the only possibility.
So, any 5–digit number has to have the digits 1, 1, 2, 3, 5. For the number to be a multiple of 5, it has to end in 5.
So, number should be of the form __ __ __ __ 5, with the first 4 slots taken up by 1, 1, 2, 3. These can be rearranged in 4!/2! = 12 ways.
There are 12 possibilities overall.Numbers with Distinct Digits
How many odd numbers with distinct digits can be created using the digits 1, 2, 3, 4, 5 and 6?
975
960
978
986=> Single digit numbers: 1, 3 or 5: Three numbers
=> Two–digit numbers: Units digit = 1, 3 or 5. For the tens’ digit, there are 5 choices {anything apart from what went into the units digit}. So, there will be 3 × 5 = 15 such numbers.
=> Three–digit numbers: Units digit = 1, 3 or 5. For the tens’ digit, there are 5 choices {anything apart from what went into the units digit}. For the 100s’ digit, there are 4 choices {anything apart from what went into the units digit or tens digit}. So, there will be 3 × 5 × 4 = 60 such numbers.
=> 4–digit numbers: There will be 3 × 5 × 4 × 3 = 180 numbers.
=> 5–digit numbers: There will be 3 × 5 × 4 × 3 × 2 = 360 numbers.
=> 6–digit numbers: There will be 3 × 5 × 4 × 3 × 2 × 1 = 360 numbers.
Total number of numbers = 360 +360 + 180 + 60 + 15 + 3 = 978.Alphabetical Order
All the rearrangements of the word "DEMAND" are written without including any word that has two D's appearing together. If these are arranged alphabetically, what would be the rank of "DEMAND"
36
74
42
86Number of rearrangements of word DEMAND = 6!/2! = 360
Number of rearrangements of word DEMAND where 2 D’s appear together = 5! = 120
Number of rearrangements of word DEMAND where 2D’s do not appear together = 360 – 120 = 240Words starting with ‘A’; without two D’s adjacent to each other
Words starting with A: "5!" /"2!" = 60
Words starting with A where 2 D’s are together = 4! = 24
Words starting with ‘A’, without two D’s adjacent to each other = 36Next we have words starting with D.
Within this, we have words starting with DA: 4! words = 24 words
Then words starting with DE
Within this, words starting with DEA => 3! = 6 words
Then starting with DED – 3! = 6 words
Then starting with DEM
=> First word is DEMADN
=> Second is DEMANDRank of DEMAND = 36 + 24 + 6 + 6 + 2 = 74
Probability and GP
A and B take part in a duel. A can strike with an accuracy of 0.6. B can strike with an accuracy of 0.8. A has the first shot, post which they strike alternately. What is the probability that A wins the duel?
7/10
12/23
2/3
11/17A can win in the following scenarios:
A strikes in first shot.
A misses in the first shot, B misses in the second, A strikes in the third.
A misses in the 1st shot, B misses in the 2nd, A misses the 3rd, B misses the 4th and A strikes the 5th.
And so on…P(A in 1st shot) = 0.6
P(A in 3rd shot) = 0.4 × 0.2 × 0.6 {A misses, then B misses and then A strikes}
P(A in 5st shot) = 0.4 × 0.2 × 0.4 × 0.2 × 0.6 {A misses, then B misses and then A misses, then B misses, then A strikes}Overall probability = Sum of all these
= 0.6 + 0.4 × 0.2 × 0.6 + 0.4 × 0.2 × 0.4 × 0.2 × 0.6 + …Which is nothing but
0.6 + (0.4 × 0.2) × 0.6 + (0.4 × 0.2)2 × 0.6 + (0.4 × 0.2)3 × 0.6…This is an infinite geometric progression with first term 0.6 and common ratio 0.4 × 0.2
Required Probability = a/(1−r) = 0.6/(1−0.08) = 0.60/0.92 = 30/46 = 15/23Probability Bayes Theorem
Doctors have devised a test for leptospirosis that has the following property: For any person suffering from lepto, there is a 90% chance of the test returning positive. For a person not suffering from lepto, there is an 80% chance of the test returning negative. It is known that 10% of people who go for testing have lepto. If a person who gets tested gets a +ve result for lepto (as in, the test result says they have got lepto), what is the probability that they actually have lepto?
7/10
8/11
1/3
1/2Let us draw the possibilities in this scenario.
Prob (patient having lepto) = 0.9
Prob (patient not having lepto) = 0.1
Given that patient has lepto, Prob (test being positive) = 0.9
Given that patient has lepto, (Prob test being negative) = 0.1Given that patient does not have lepto, Prob (test being negative) = 0.8
Given that patient does not have lepto, Prob (test being positive) = 0.2
Now, we are told that the test turns positive. This could happen under two scenarios – the patient has lepto and the test turns positive and patient does not have lepto and the test turns positive.
Probability of test turning positive = 0.9 × 0.1 + 0.9 × 0.2 = 0.27.
Now, we have not been asked for the probability of test turning positive. We are asked for the probability of patient having lepto given that he/she tests positive. So, the patient has already tested positive. So, this 0.27 includes the set of universal outcomes. Or, this 0.27 sits in the denominator.
Within this 0.27, which subset was the scenario that the patient does indeed have lepto?
This is the key question. This probability is 0.1 × 0.9 = 0.09. So, the required probability = 0.09/0.27 = 1/3
So, if a patient tests positive, there is a 1 in 3 chance of him/her having lepto. This is the key reason that we need to be careful with medical test results.