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

rajesh_balasubramanian
Director, 2IIM Online CAT Preparation  IIT Madras  IIM Bangalore  CAT 100th percentile  CAT 2011, 2012 and 2014.
In how many ways can letters of the word ATTITUDE be rearranged such that no two T’s are adjacent to each other?
ATTITUDE has 8 letters, of which 3 are T’s
Now, Let us place the letters that are not Ts on a straight line. We have AIUDE. These can be arranged in 5! Ways. Now let us create slots between these letters to place the Ts in. In order to ensure that no two T’s are adjacent to each other, let us create exactly one slot between any two letters.
A __ I __ U __ D __ E.
Additionally, let us add one slot at the beginning and end as well as the T’s can go there also
A __ I __ U __ D __ E
Now, out of these 6 slots, some 3 can be T. That can be selected in 6C3 ways.
So, total number of words = 5! × 6C3 = 2400In how many rearrangements of the word SLEEPLESS will no two S’s appear together?
Let us aggregate the other letters LEEPLE and arrange these.
These can be arranged in 6!/2!3! ways. Now, let us create slots in between and before/after these letters, where S can potentially appear.
__ L __ E __ E __ P __ L __ E__.
Out of these 7 slots, 3 should be taken up by S’s. This can be done in 7C3 ways.
So, total number of rearrangements = 6!/2!3! × 7C3 = 60 × 35 = 2100How many numbers of up to 5 digits can be created using the digits 1, 2 and 3 that are multiples of 12?
For a number to be a multiple of 12, it has to be a multiple of 3 and of 4. So, the last two digits have to be a multiple of 4 and the sum of digits should be a multiple of 3.
We need to break this down by number of digits.
2–digit number: Only possibility 12.
3–digit numbers: These can end in 12 or 32. If it ends in 12, the sum of these two digits is 3, the only value the first digit can take is 3. Similarly if it ends in 32, the only value the first digit can take is 1. So, two 3–digit numbers are possible 312 and 132.
4–digit numbers: Again, these can in 12 or 32.
Scenario I: Ending in 12. Sum of these two digits = 3. First two digits can be 12 or 21 or 33.
Scenario II: Ending in 32. Sum of these two digits = 5. First two digits can be 22, 13 or 31.
So, possible 4–digit numbers are 1212, 2112, 3312, 2232, 1332, 3132.
5–digit numbers: Again, these can end in 12 or 32.
Scenario I: Ending in 12. Sum of these two digits = 3. First three digits can be 111, 222, 333, 123 (6 rearrangements 132, 213, 231, 312, 321) – 9 possibilities
Scenario II: Ending in 32. Sum of these two digits = 5. First three digits can add up to 4 or 7.
First 3–digits adding up to 4: 112, 121, 211. 3 possibilities
First 3–digits adding up to 7: 223, 232, 322, 133, 313, 331. 6 possibilities
9 possibilities overall
Total number of 5–digit numbers = 9 + 9 = 18
Overall, total number of possibilities = 1 + 2 + 6 + 18 = 27 numbers.How many numbers of up to 5 digits can be created using the digits 1, 2, 3, 5 each at least once such that they are multiples of 15?
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.How many 4–digit numbers with distinct digits exist product of whose digits is a non–zero multiple of 9?
For the product to be zero, one of the digits has to be zero. So, if the product is non–zero, no digit can be zero.
For the product to be a multiple of 9, one of the digits can be 9, or we could have 3 and 6 as two digits of the number.
Scenario I: One of the digits being equal to 9: 9 can be either in the 1000’s place, or 100’s place, or 10’s place or units place. Now, with 9 in the 1000’s place, we will have 8 × 7 × 6 numbers totally.
So, overall there will be 8 × 7 × 6 × 4 numbers possible. 56 × 24 = 1344 numbers
Scenario II: Two of the digits being equal to 3 and 6: Now, in this list we should exclude all numbers that have a 9 as we would have already accounted for these. So, we need to count all possibilities where two digits being 3 and 6, other two selected from 1, 2, 4, 5, 7, 8. No of ways of selecting 2 digits out of 6 = 6C2.
Number of ways of rearranging = 4!.
So, number of numbers = 6C2 × 4! = 15 × 24 = 360
Total number of possible numbers = 1344 + 360 = 1704.From 4 doctors, 3 engineers and 5 scientists, in how many ways can we create a committee of 6 to 8 people that has more scientists than engineers, more engineers than doctors, and at least one doctor?
Three scenarios are possible – the committee can have 6, 7 or 8 people
Scenario I: 6–member committee. 3 scientists,
2 engineers and 1 doctor. Number of ways =
5C3 × 3C2 × 4C1 = 10 × 3 × 4 = 120
Scenario II: 7–member committee.
4 scientists, 2 engineers and 1 doctor: Number of ways = 5C4 × 3C2 × 4C1 = 5 × 3 × 4 = 60
Scenario III: 8–member committee.
5 scientists, 2 engineers and 1 doctor: Number of ways = 5C5 × 3C2 × 4C1 = 1 × 3 × 4 = 12
4 scientists, 3 engineers and 1 doctor: Number of ways = 5C4 × 3C3 × 4C1 = 5 × 1 × 4 = 20 ways
Total number of possibilities = 120 + 60 + 12 + 20 = 212.A flag is formed with 4 vertical bands. If we can choose from colors blue, green, and yellow and no two adjacent bands should have the same color, how many different flags can be created?
Scenario I: 2 colours chosen: Number of ways of selecting 2 colours = 3C2 . For the two colours that have been selected, say A and B, there are two arrangements possible – ABAB or BABA. Total number of flags with 2 colors = 3C2 × 2 = 3 × 2 = 6
Scenario II: All 3 colours being chosen. Any one colour will have to be repeated. Selecting the one colour that repeats can be done in 3C1 ways. Post this, we have AABC. This can be rearranged in 4!/2! ways. Of these there will be 3! ways when the two A’s appear together. So, the number of ways where 2 A’s do not appear together will be 12 – 6 = 6. These are ABAC, ABCA, ACAB, ACBA, BACA, CABA. Total number of possible flags where three colours are chosen = 3C1 × 6 = 18 ways
So, there are 6 + 18 = 24 different flags possible totally.
This can also be done with another approach.
Let the four bands be called ABCD.
A can be selected in 3 ways. It could be blue, green or yellow.
B can be any of the three colours except A. So, there are 2 possible options for B.
C can be any of the three colours except B. So, there are 2 possible options for C.
D can be any of the three colours except C. So, there are 2 possible options for D.
Total number of options = 3 × 2 × 2 × 2 = 24 waysAn equation ax^2 + 8x + c = 0 has two distinct real roots. If a, c are positive integers less than 11, how many values can (a, c) take?
The equation has distinct real roots
> b^2 – 4ac > 0
> b = 8.
> 64 – 4ac > 0
> 4ac < 64
> ac < 16
If a = 1, c can be 1, 2, 3, 4, 5, 6, 7, 8, 9, or
10 – 10 possibilities
When a = 2, c can be 1, 2, 3, 4, 5, 6, or 7 > 7 possibilities
When a = 3, c can be 1, 2, 3, 4, 5 > 5 possibilities
When a = 4, c can be 1, 2, 3 > 3 possibilities
When a = 5, c can be 1, 2, 3 > 3 possibilities
When a = 6, c can be 1, 2 > 2 possibilities
When a = 7, c can be 1, 2 > 2 possibilities
When a = 8, c can be 1 > 1 possibility
When a = 9, c can be 1 > 1 possibility
When a = 10, c can be 1 > 1 possibility
Totally 35 pairs of values2a + 5b = 103. How many pairs of positive integer values can a, b take such that a > b?
Let us find the one pair of values for a, b. a = 4, b = 19 satisfies this equation. 2×4 + 5×19 = 103. Now, if we increase ‘a’ by 5 and decrease ‘b’ by 2 we should get the next set of numbers. We can keep repeating this to get all values.
Let us think about why we increase ‘a’ by 5 and decrease b by 2. a = 4, b = 19 works. Let us say, we increase ‘a’ by n, then the increase would be 2n. This has to be offset by a corresponding decrease in b. Let us say we decrease b by ‘m’. This would result in a net drop of 5m. In order for the total to be same, 2n should be equal to 5m. The smallest value of m, n for this to work would be 2, 5.
a = 4, b = 19
a = 9, b = 17
a = 14, b = 15
..
And so on till
a = 49, b = 1
We are also told that ‘a’ should be greater than ‘b’, then we have all combinations from (19, 13) … (49, 1).
7 pairs totally.Using the vertices of a regular hexagon as vertices, triangles of how many different areas can be formed?
Let us number the vertices from 1 to 6. There are three different types of triangles that can be formed.
Type I: (1, 2, 3): This type of triangle is also seen with (2, 3, 4), (3, 4, 5) etc.
Type II: (1, 2, 4): (1, 2, 5) has the same shape and area. So, do (2, 3, 5), (3, 4, 6) etc.
Type III: (1, 3, 5): (2, 4, 6) has the same shape and area.
So, there will be 3 triangles of different areas that can be formed from a regular hexagon.
There are 6 triangles of Type I, 12 of type II and 2 of type III, adding up to 20 triangles totally.
The total number of triangles possible = 6C3 = 20.