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

rajesh_balasubramanian
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 4digit 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! × 1071How 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 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
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!3!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!3!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 = 4018If 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 = 4718When 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 throwsScenario 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 ‘A’; without two D’s adjacent to each other