Combinatorics - Rajesh Balasubramanian - CAT 100th Percentile - CAT 2011, 2012 and 2014 - Part (2/2)
Director, 2IIM Online CAT Preparation | IIT Madras | IIM Bangalore | CAT 100th percentile - CAT 2011, 2012 and 2014.
In how many ways can letters the word ATTITUDE be rearranged such that no two Ts are adjacent to each other?
ATTITUDE 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?
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
Rearrangement of Letters - Probability:
If all the rearrangements of the word AMAZON are considered, what is the probability that M will feature between the 2As?
For 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 one-third 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 3-digit number that is a multiple of 7; what is the probability that it will be a multiple of 5?
N 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/64
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?
he 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/3
Rolling 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?
If 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.
Each 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?.
If 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.
For 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.
For 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 4-digit number 3214?
Total 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 4-digit number 3321?
Each 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.
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 - (8C3 + 7C3 +10C3)
22C3 + (8C3 + 7C3 +10C3)
8C3 + 7C3 +10C3
From 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?
Let 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/35
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 ! * 4C3
MANANA 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 ways
I 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 ! ways
Consider AIA as one component as I has to appear between 2 A’s
Thus we have MZNG(AIA)
This can be arranged in 5! ways
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 ! ways
We can distribute boys in 2-1-1-1 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 3-digit numbers greater than 500 contain the digit 9 appearing at least once?
509, 519... 999 all these numbers have atleast one 9 in them
These put together gives 50 numbers
Now 590,591,..599 atleast has one 9 , but 599 is already included in the first list. Hence 9 numbers.
Similarly for 600-900 series, all put together we get 45 numbers
All numbers from 900 to 999 have a 9 in them but 990-999 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 500-999.