Demystifying Permutation & Combination - Rajesh Balasubramanian - CAT 100th Percentile - CAT 2011, 2012 and 2014 (Part 6/7)


  • Director, 2IIM Online CAT Preparation | IIT Madras | IIM Bangalore | CAT 100th percentile - CAT 2011, 2012 and 2014.


    If we listed all numbers from 100 to 10,000, how many times would the digit 3 be printed?

    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 unit’s 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 unit’s 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.
    The alternative, much simpler way, would be to count the number of ways 3 would be printed while printing numbers from 1 to 10000, and then subtract the number of ways 3 would get printed from 1 to 100 from this number.
    Number of ways 3 would be printed while printing numbers from 1 to 10000: 4000. 3 would get printed 1000 times in the units place, 1000 times in the tens place, 1000 times in the hundreds place and 1000 times in the thousands place.
    Number of ways 3 would be printed while printing numbers from 1 to 100: 20. 10 times each in the units and tens place.
    Answer = 4000 - 20 = 3980. As we have mentioned before, sometimes solving by a circuitous route could be instructive. So, we will continue to take detours like these.

    How many odd numbers with distinct digits can be created using the digits 1, 2, 3, 4, 5 and 6?

    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.

    How many 5–digit numbers with distinct digits can be created with digits 1, 2, 3, 4, 5, 6 such that the number is multiple of 12?

    For a number to be a multiple of 12, it has to be a multiple of 3 and 4.
    For the number to be a multiple of 3, the sum of the digits should be a multiple of 3. The sum of all 6 digits = 21. This is a multiple of 3. So, if the sum of 5 digits has to be a multiple of 3, we need to drop one multiple of 3 from this.
    So, the 5 distinct digits that can go into forming the number can be 1, 2, 3, 4, 5 or 1, 2, 4, 5, 6.
    Numbers with digits 1, 2, 3, 4 and 5: For the number to be a multiple of 4, the last two digits should be a multiple of 4. The last two digits can be 12, 32, 52 or 24.
    When the last two digits are 12: The number is __ __ __ 12. The first 3 digits have to be 3, 4, 5 in some order. There are 3! such numbers possible. Or, there are 6 numbers in this list.
    So, total number of numbers possible with the digits 1, 2, 3, 4 and 5 = 6 × 4 = 24
    Numbers with digits 1, 2, 4, 5 and 6: For the number to be a multiple of 4, the last two digits should be multiple’s of 4. The last two digits can be 12, 32, 24, 64, 16 or 56.
    With each of these as the last two digits, we can have 3! or 6 numbers.
    So, the total number of numbers possible with the digits 1, 2, 4, 5 and 6 = 6 × 6 = 36.
    The Total number of numbers = 24 + 36 = 60.

    How many 6 letter words with distinct letters exist that have more vowels than consonants?

    vowels and 2 consonants: 5C4 × 21C2 × 6!
    5 vowels and 1 consonants: 5C5 × 21C1 × 6!
    Total number of words = 5C4 × 21C2 × 6! + 5C5 × 21C1 × 6! = 6! (5 × 210 + 1 × 21) = 6! × 1071

    How many 4 letters words can be created with more consonants than vowels?

    4 consonants and 0 vowels: 21^4
    3 consonants and 1 vowel: This can happen in three different ways
    3 distinct consonants and 1 vowel: 21C3 × 5C1 × 4!
    2 consonants of which 1 occurs twice and 1 vowel: 21C2 × 2C1 × 5C1 × 4!/2!
    1 consonant that appears thrice and 1 vowel: 21C1 × 5C1 × 4!/3!
    Total number of words = 214 + 21C3 × 5C1 × 4! + 21C2 × 2C1 × 5C1 × 4!/2! + 21C1 × 5C1 × 4!/3!
    Alternatively, the above answer can be given as 214 + 213 * 20. Try to figure out the logic behind that answer.

    All the rearrangements of the word “DEMAND” are written without including any word that has 2 D’s appearing together. If these are arranged alphabetically, what would be the rank of “DEMAND”?

    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

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

    If letters of the word SLEEPLESS were arranged alphabetically, what rank would ‘SLEEPLESS’ hold?

    Total number of words = 9!/3!3!2! = 5040
    Words starting with E = 8!/3!2!2! = 1680
    Words starting with L = 8!/3!3! = 1120
    Words starting with P = 8!/3!3!2! = 560
    Words starting with S = 8!/3!2!2! = 1680
    Words gone by thus far
    Starting with E - 1680
    Starting with L - 1120
    Stating with P - 560
    Now, within the words starting with S
    Words starting with SE = 7!/2!2!2! = 630
    Words starting with SL = 7!/3!2! = 630, SLEEPLESS is within this list, so we need to drill further.
    Words starting with SLEEE = 4!/2!= 12 words
    Words starting with SLEEL = 4!/2! = 12 words
    Words starting with SLEEPE = 3!/2! = 3 words
    Words gone thus far
    Starting with E - 1680
    Starting with L - 1120
    Starting with P - 560
    Starting with SE - 630
    Starting with SLEEE - 12
    Starting with SLEEL - 12
    Starting with SLEEPE - 3
    Then comes SLEEPLESS (at long last): Rank = 4018

    If all words with 2 distinct vowels and 3 distinct consonants were listed alphabetically, what would be the rank of “ACDEF’?

    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, the 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, the 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 when we move to words starting with ACDE, the first possible word is ACDEB. After this we have ACDEF.
    So, rank of ACDEF = 4718

    When a die is thrown 4 times in how many ways can we have at least one digit appearing exactly twice?

    Two scenarios are possible.
    Scenario I: One digit appears twice accompanied with two distinct digits, AABC. 6C1 × 5C2 × 4C2 × 2!.
    Selecting the digit that appears twice
    Selecting the other two digits
    Selecting the two throws where the digit appearing twice appears
    Number of arrangements for the final two throws

    Scenario II: Two digits appear twice each, AABB. 6C2 × 4!/2!2!.
    Selecting the digits that appear twice
    Number of arrangements for AABB
    Total number of ways = 6C1 × 5C2 × 4C2 × 2! + 6C2 × 4!/2!2!

    When a die is rolled 3 times, how many possibilities exist such that each throw results in a number that is at least as high as that of the preceding throw?

    If the first throw were 6, there is only one possibility = 666
    If the first throw were 5, there are three possibilities for the next two throws = 55, 56 and 66
    If the first throw were 4, the next two
    throws can be 44, 45, 46, 55, 56, and 66 = 6 possibilities
    If the first throw were 3, the next two throws can be 33, 34, 35, 36, 44, 45, 46, 55, 56, 66 = 10 possibilities; this is nothing but 4 + 3 + 2 + 1.

    [ It is important to pick this pattern. The {1, 3, 6, 10, 15, 21…} pattern is very common in counting. In this sequence each term tn is nothing but the sum of natural numbers till n.]

    If the first throw were 2, the next two throws can be obtained in 5 + 4 + 3 + 2 + 1 = 15 ways.
    If the first throw were 1, the next two throws can be obtained in 6 + 5 + 4 + 3 + 2 + 1 = 21 ways.
    Total number of possibilities = 21 + 15 + 10 + 6 + 3 + 1 = 56 ways.



  • Words starting with E = 8!/3!3!2! = 1680

    It should be-

    Words starting with E = 8!/3!2!2!


  • administrators

    @Vikrant-Garg Yes, it should be 8!/3!2!2! (omitting first E, we are left with 3 S, 2 E, 2 L and 1 P)
    Same applies to words starting with S too.
    Whole problem needs to be reworked now because of one mistake :smiling_imp:


  • Being MBAtious!


    @Vikrant-Garg it is a typo only as 1680 is obtained as 8!/3!2!2!.. (8!/3!3!2! is 560)
    Thanks for pointing out.. will correct it.
    Happy learning.


Log in to reply
 

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