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

rajesh_balasubramanian
Director, 2IIM Online CAT Preparation  IIT Madras  IIM Bangalore  CAT 100th percentile  CAT 2011, 2012 and 2014.
Rearranging Letters:
In how many ways can letters the word ATTITUDE be rearranged such that no two Ts are adjacent to each other?
6720
2400
4320
1800ATTITUDE has 8 letters, of which 3 are Ts
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 Ts 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 Ts 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 = 2400
Answer choice (b)Possible Integer Solutions:
2a + 5b = 103. How many pairs of positive integer values can a, b take such that a > b?
7
9
14
15Let 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 totallyRearrangement of Letters  Probability:
If all the rearrangements of the word AMAZON are considered, what is the probability that M will feature between the 2As?
1/3
1/6
2/5
3/8For this type of question, we need to consider only the internal arrangement within the M and 2As.
M and 2As can be rearranged as AMA, AAM, or MAA.
So, the probability that M will feature between the 2As is 1/3.
Now, let us think why we need to consider only the M and 2As.
Let us start by considering a set of words where the M and 2 As are placed at positions 2, 3 and 5.
The other three letters have to be in slots 1, 4 and 6
Three letters can be placed in three different slots in 3! = 6 ways.
Now with __ M A __ A __ there are 6 different words.
With __ A M __ A __ there are 6 different words.
With __ A A __ M __ there are 6 different words.
For each selection of the positions for A,A and M, exactly onethird of words will have M between the two A’s.
This is why only the internal arrangement between A, A and M matters.
So, probability of M being between 2 As is 1/3.Probability and Number Theory:
N is a 3digit number that is a multiple of 7; what is the probability that it will be a multiple of 5?
1/5
11/54
13/64
13/66N is a three digit multiple of 7.
N could be 105, 112, 119, 126…..994.
Or, 15 × 7, 16 × 7…..142 × 7.
Or there are 142–14 = 128 numbers.
Within these we need to locate the multiples of 5.
Or, we need to isolate multiples of 35.
Or, we need to see how many numbers there are in the list 105, 140, 175…..980.
35 × 3, 35 × 4…35 × 28…
Or, there are 26 such numbers.
Probability 26/128 = 13/64Probability
A boss decides to distribute Rs. 2000 between 2 employees. He knows X deserves more that Y, but does not know how much more. So he decides to arbitrarily break Rs. 2000 into two parts and give X the bigger part. What is the chance that X gets twice as much as Y or more?
2/5
1/2
1/3
2/3he bigger part could be any number from 1000 to 2000.
Now, if the bigger part is to be at least twice as much as the smaller part, we have
X ≥ 2Y or X ≥ 2(2000 – X )
Or X ≥ 4000/3
Given that X lies between 1000 and 2000, what is the probability that X lies between 4000/3 and 2000?
This probability is equal to (2000 − 4000/3)/(2000 − 1000) = 2/3Rolling a Die:
I roll a die four times. In how many outcomes do we have two throws have the same number and the other two something different?
720
480
360
350If we want to have two throws to have the same outcome and the other two being something different, we are essentially looking for three different outcomes in each throw.
We can have three different outcomes in each throw in 6C3 ways. We can select the one that is being repeated out of the three outcomes in 3C1 ways.
And then, they can be arranged in 4!/2! ways, since there are totally 4 throws out of which 2 are repeated. So, Totally , we can do this in 6C3 * 3C1 * 4!/2! = [(4 ∗ 5 ∗ 6)/6] * 3 * 12 = 20 * 3 * 12 = 720 ways.
Card Pack  Selection
In how many ways can be select 5 cards from a card pack such that all 4 suits appear.
3024
2048
4056
2568Each suit has 13 cards and one card can be selected from each suit in 13C1 ways. For selecting 5 cards from a card pack we need to have two cards from one suit and 3 cards from the other three suits.
Suit which will have 2 cards can be selected in 4C1 ways and two cards can be selected from that suit in 13C2 ways. Overall 5 cards can be selected such that all 4 suits appear in 4C1 * 13C2 * 13C1
= 4 * 13 * 78
= 4056 ways.Rolling a Die
I roll a die 4 times. In how many outcomes will each subsequent throw be greater that the previous one?.
30
48
54
60If we want the outcome in each throw to be greater than the previous one, essentially we are looking at four different outcomes in each throw and the possibility of each outcome being greater than the previous is possible only in one combination.
So, we are looking at just selecting four outcomes out of 6 possible outcomes when we normally roll a die. This is equal to 6C4= 30 ways.3 Digit Number
Find 3 digit numbers such that product of their digits is a natural number less than 5.
11
15
13
17For the product of a 3 digit number to be lesser than 5, it should comprise of either 1, 2 ,3 or 4 in a certain way.
Let’s start with product = 1 => this is possible in only one way (111).
Product =2 => Possible in 3 ways(211, 112 and 121).
Product = 3=> Possible in 3 ways(311, 113 and 131).
Product = 4 => Possible in 3 ways(411, 114, 141, 221, 212 and 122).
Total = 1+3+3+6 =13 numbers.3 Digit Number  Sum of Digits
Find all 3 digit numbers such that sum of their digits is a whole number less than 5.
18
20
19
17For the sum of the digits of a 3 digit number to be a whole number less than 5 – it can take the values – 0, 1 , 2, 3 or 4.
For sum =0, there are no such numbers.
Sum=1, Possible in 1 way(100).
Sum=2, Possible in 3 ways (110,101 and 200)
Sum=3, Possible in 6 ways (111, 210, 201, 120, 102 and 300)
Sum=4, Possible in 10 ways (121, 112, 211, 220, 202, 301, 310, 103, 130 and 400)
Total = 1+3+6+10 = 20 numbers are possible.Sum of Rearrangements
What is sum of all rearrangements of the 4digit number 3214?
66660
55554
60048
65024Total number of rearrangements = 4! Ways = 24.
Each of the four digits is likely to appear in the units place , therefore  th of 24 = 6 numbers will have 2 in the units place, 6 will have 1 in the units place and so on..
Therefore, sum of units place = 6*(2+3+1+4) = 60
Sum of tens place = 6 * (20+30+10+40) = 600.
Sum of hundreds place = 6 * 1000 =6000
Sum of thousands place = 6 * 10000 =60000. Therefore, sum of all rearrangements of 3214 = 66660.Sum of Rearrangements
What is sum of all rearrangements of the 4digit number 3321?
29999
27777
28888
29997Each of the four digits is likely to appear in the units place , but the digit 3 will appear twice as that of 2 and 1.
Therefore, sum of units place = 3 * 2 + 3 * 1 + 6 * 3 = 27.
Sum of tens place = 270
Sum of hundreds place = 2700
Sum of thousands place =27000
Sum of all arrangements of 3321 = 29997.Forming Triangles
Of 22 points on a plane, 8 are on a straight line, 7 are on another straight line and 10 are on a third straight line. How many triangles can be drawn by connecting some three points from these 22?
22C3
22C3  (8C3 + 7C3 +10C3)
22C3 + (8C3 + 7C3 +10C3)
8C3 + 7C3 +10C3From the 22 points on a plane we can form 22C3 triangles but it is given that 8 are on one straight line, 7 are on another straight line and 10 more are on another straight line, so we can form triangles on joining points which are on straight lines so we have to subtract (8C3+ 7C3 +10C3) from the total.
Hence, we can form 22C3  (8C3+ 7C3 +10C3) triangles.
Selection and Probability
A bag contains 4 red and 3 black balls. A second bag contains 2 red and 3 black balls. One bag is selected at random. If from the selected bag one ball is drawn, then what is the probability that the ball drawn is red?
39/70
41/70
29/70
17/35Let Red balls be 'r' and brown balls be 'b'
P(r) = p(b1) * p(r) + p(b2) * p(r)
P(R) = 1/2 ∗ 4/7 + 1/2 ∗ 2/5
P(R) = 17/35MANANA Rearrangment
In how many ways can we rearrange the letters of the word MANANA such that no two A’s are adjacent to each other?
3 ! * 5C3
4 ! * 4C3
3 ! * 4C3
5 ! * 4C3MANANA has 6 letters, of which 3 are A's
Now, let us place the letters that are not As on a straight line. We have MNN. These can be arranged in 3! ways.
Now let us create slots between these letters to place the As in.
In order to ensure that no two As are adjacent to each other, let us create exactly one slot between any two letters.
M __N __ N
Additionally, let us add one slot at the beginning and end as well as the As can go there also.
__ M __N __ N __
Now, out of these 4 slots, some 3 can be A. That can be selected in 4C3 ways.
So, total number of words = 3 ! * 4C3 waysI between 2 A's
How many ways are there for arranging letters of the word AMAZING such that the ‘I’ appears between the two ‘A’s?
5 ! ways
7 ! ways
8 ! ways
4 ! waysConsider AIA as one component as I has to appear between 2 A’s
Thus we have MZNG(AIA)
This can be arranged in 5! waysRoom Allocation
In how many ways can 6 boys be allotted into 5 rooms such that no room is empty and all 6 boys are accommodated?
6 * 5 ! ways
7 * 5 ! ways
3 * 3 ! ways
15 * 5 ! waysWe can distribute boys in 2111 fashion , that is we can put two boys in one room and the other rooms will have one boy each.We can pick two boys out of the 6 in 6C2 ways.And these two boys can be allotted to any one of the rooms in 5 ways. The remaining rooms can be filled in 4 * 3 * 2 * 1 ways.
SO, Totally the number of ways is 6C2 * 5! = 15 * 5 ! ways.
3 Digit numbers > 500
How many 3digit numbers greater than 500 contain the digit 9 appearing at least once?
191
176
153
189509, 519... 999 all these numbers have atleast one 9 in them
These put together gives 50 numbersNow 590,591,..599 atleast has one 9 , but 599 is already included in the first list. Hence 9 numbers.
Similarly for 600900 series, all put together we get 45 numbersAll numbers from 900 to 999 have a 9 in them but 990999 are already accounted and also 909,919..999 are accounted.
Hence 81 numbers will have 9 atleast once.Put together totally 176 numbers have atleast one 9 in them between 500999.