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


  • 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
    28

    a + 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
    56

    a + 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
    36

    This 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 = 45

    Permutation 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
    4

    Exactly 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 seven-digit number comprises of only 2's and 3's. How many of these are multiples of 12?
    11
    12
    10
    22

    Number 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
    1717

    The 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 = 4718

    Combinatorics Basics
    If we listed all numbers from 100 to 10,000, how many times would the digit 3 be printed?
    3980
    3700
    3840
    3780

    We need to consider all three digit and all 4-digit numbers.
    Three-digit 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 3-digit numbers
    Four-digit 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 4-digit numbers.
    So, there are totally 3700 + 280 = 3980 numbers.

    Number Systems - Combinatorics
    From the digits 2, 3, 4, 5, 6 and 7, how many 5-digit numbers can be formed that have distinct digits and are multiples of 12?
    36
    60
    84
    72

    Any 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 5-digit numbers possible

    Numbers 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 non-zero units digit in both base 6 and base 7 notations?
    143
    200
    157
    122

    If 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 non-zero units digit = 200 - 57 = 143.

    Non-Zero 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
    45

    Any 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 3-digit 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
    12

    For 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
    86

    Number 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 = 240

    Words 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 = 36

    Next 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 DEMAND

    Rank 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/17

    A 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/23

    Probability 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/2

    Let 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.1

    Given 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.


Log in to reply
 

Looks like your connection to MBAtious was lost, please wait while we try to reconnect.