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

rajesh_balasubramanian
Director, 2IIM Online CAT Preparation  IIT Madras  IIM Bangalore  CAT 100th percentile  CAT 2011, 2012 and 2014.
When a die is rolled thrice, in how many outcomes will we have the product of the throws and sum of the throws to be even numbers?
The product has to be even => There should be at least one even number.
The sum has to be even => There are either 3 even numbers or 2 odd numbers, and 1 even number.
So, both conditions put together, there are two possibilities – all three throws being even, there being 2 odd throws and 1 even throw.
Scenario I: All three even: 3 × 3 × 3 = 27 possibilities
Scenario II: Two odd and one even, the two odd slots can be selected in 3C2 = 3 ways. After these have been selected, the number of options for each throw is 3. Number of ways = 3 × 3 × 3 ×3 = 81 waysSo, overall number of ways = 27 + 81 = 108 ways.
A string of n consecutive even natural numbers has 23 multiples of 14 in it. How many of the following could be true?
(1) n = 157
(2) Of these n numbers, exactly 80 are multiples of 4.
(3) Of these n numbers, more than 50 are multiples of 3.Let us start with a simple example. Let us say we list down even numbers starting from 2.
So, our sequence reads {2, 4, 6, 8, 10,……..2n}.
Now, this list should have 23 multiples of 14. So, the smallest value 2n could take for this to be true is 14 × 23, which is 322.
So, if our sequence ran from {2, 4, 6, 8, ….322} it would have 23 multiples of 14 in it – all multiples from 14 to 322. In this case, the value of n would be 161.
However, we can see that a sequence running from {2, 4, 6,…334} would also have 23 multiples of 14 in it, and so would a sequence that runs as {14, 16, 18,….322}.
We can arguably have a sequence that starts and ends with a multiple of 14 – this type of sequence would have 155 elements (161 – 6). Or, have a sequence that starts with a number that is of the type 14n + 2 and ends with a number of the type 14K –2 (so that we include maximum number of non–multiples of 14 in the list); this type of sequence will have 167 elements (161 + 6). So, n can range from 155 to 167.
Now, to the statements n = 157, n can range from 155 to 167, so this could be true.
 Of these n numbers, exactly 80 are multiples of 4. If there are 160 consecutive even numbers, exactly 80 would be divisible by 4. So, this could be true.
 Of these n numbers, more than 50 are multiples of 3. If we take 150 consecutive even numbers, 50 will be multiples of 3. N is definitely more than 150. So, there will definitely be more than 50 multiples of 3.
So, all three statements are true
The product of the digits of a 5–digit number is 1800. How many such numbers are possible?
1800 = 2^3 × 3^2 × 5^2. From this it is clear that two digits have to be 5. The remaining three digits multiply to give 72.
72 can be written as a product of 3 digits in the following ways.
1 × 8 × 9
2 × 4 × 9
2 × 6 × 6
3 × 3 × 8
3 × 4 × 68 9 5 5: Number of numbers = 5!/2! = 60
2 4 9 5 5: Number of numbers = 5!/2! = 60
2 6 6 5 5: Number of numbers = 5!/2!2! = 30
3 3 8 5 5: Number of numbers = 5!/2!2! = 30
3 4 6 5 5: Number of numbers = 5!/2! = 60Total number of numbers = 60 × 3 + 30 × 2 = 240
The sum of three distinct positive integers is 16. How many values can a x b x c take?
a + b + c = 16
Let the smallest value be a.
If a = 1, b + c = 15. This can be done in 6 ways –2 + 13, 3 + 12, 4 + 11, 5 + 10, 6 + 9, 7 + 8
If a = 2, b + c = 14. This can be done in 4 ways – 3 + 11, 4 + 10, 5 + 9, 6 + 8
If a = 3, b + c = 13. This can be done in 3 ways – 4 + 9, 5 + 8, 6 + 7
If a = 4, b + c = 12. This can be done in 1 way – 5 + 7 a cannot be 5 or more as we have assumed a to be the smallest number.
Totally, there are 6 + 4 + 3 + 1 = 14 ways.
a × b × c is distinct for all of these ways. So, we do not have to worry about that. 14 different products can be formed.Product of 3 distinct positive numbers is 120. How many such sets are possible?
Again, let us take a × b × c = 120. a < b < c. In all of these questions, it helps to count with a pattern.
Let a = 1, b × c = 120. 120 = 2^3 × 3 × 5, which has 16 factors. Or, 120 can be written as a product of two natural numbers b × c in 8 ways. Of these 8 ways, one will be 1 × 120. Subtracting this one way, we have 7 pairs with a = 1.
a = 2; b × c = 60; b, c > 2
3 × 20
4 × 15
5 × 12
6 × 10
4 options
a = 3, b × c = 40 ; b, c > 3
4 × 10
5 × 8
a = 4, b × c = 30 ; b, c > 4
5 × 6
Totally there are 7 + 4 + 2 + 1 = 14 options.Set A has element {a, b, c, d, e} Set B = {1, 2, 3}. How many onto functions exist from set A to set B such that f(a) = 1.
First let us compute the number of onto functions from Set A to Set B.
Step I: Number of functions from Set A to Set B = 3^5 = 243. Each element in Set A has 3 options which it can be mapped to. So, the total number of sets = 3^5.
Step II: Let us calculate the number of ways in which a function can be not onto.
This can happen in two scenarios.Scenario I: Elements in Set A are mapped to exactly 1 element in Set B. This can be done in 3 ways. All elements to either 1, 2 or 3.
Scenario II: Elements in Set A are mapped to exactly 2 of the elements in Set B, for instance {a, b, c, d, e} mapped to {1, 2}. Now, this can happen in 2^5 ways. But within this 2^5 ways, we would count the two ways where all elements are mapped to 1 and all elements are mapped to 2 as well (the instances that have already been accounted for in Scenario I). So, the number of ways in which a function can be mapped from {a, b, c, d, e} to {1, 2} such that both 1 and 2 have some element mapped to them = 2^5 – 2 = 30.
The function could have been defined from Set A to {1, 2} or {2, 3} or {1, 3}. So, total number of possibilities = 30 × 3 = 90.
Total number of non–onto functions = 90 + 3 = 93. Total number of onto functions = 243 – 93 = 150.
Exactly one–third of these will have f(a) = 1. Or, there are 50 onto functions possible such that f(a) = 1.Set A has elements {a, b, c, d, e, f}. How many subsets of A have element ‘a’, do not have element b and have an even numbers of elements?
A subset should have element a and it should have an even number of elements. So, it can have 2, 4 or 6 elements. But since it cannot have b, it can have only either 2 or 4 elements.
2–element subsets: There are 4 ways of doing this. Apart from a the subset can have c, d, e or f.
4–element subsets: Apart from ‘a’ the subset should have some 3 of c, d, e or f or 4C3 subsets.
Totally 4 + 4 = 8 subsets are possible.How many rearrangements of the word EDUCATION are there where no two consonants are adjacent to each other?
Place the 5 vowels – AEIOU. This can be done in 5! ways.
Now, create one slot between every two vowels and one before all the vowels and one after all the vowels
__ E __ U __ A I __ O
Of these 6 slots, some 4 have to be taken by consonants. This can be done in 6C4 ways. Then the consonants can be arranged in 4! ways.
So, total number of outcomes = 5! × 6C4 × 4!Consider 24 points of which 7 lie on a straight line and 8 are on a different straight line. No other set of 3 points are collinear. How many triangles can be considered out of these 24 points?
Four scenarios are possible.
Scenario I: All 3 points of the triangle are from the 9 non–collinear points. 9C3 = 84
Scenario II: 2 points are from the 9 non–collinear points and 1 from the remaining 15. 9C2 × 15C1 = 540
Scenario III: 2 points from one of the two lines and 1 point from among the 9 non–collinear points.
8C2 × 16C1 or 7C2 × 17C1 = 448 + 357 = 805
Scenario IV: 1 point each from the two lines that contain collinear points and 1 point from among the 9 non–collinear points. 8C1 × 7C1 × 9C1 = 504
Total scenarios = 84 + 540 + 805 + 504 = 1933The same answer can be obtained as 24C3 – 7C3 – 8C3, which is obviously the far more elegant method. But what is the joy in doing only by the elegant methods!
How many numbers with distinct digits are possible, the product of whose digits is 28?
Two digit numbers: The two digits can be 4 and 7: Two possibilities 47 and 74
Three–digit numbers: The three digits can be 1, 4 and 7: 3! or 6 possibilities
We cannot have three digits as (2, 2, 7) as the digits have to be distinct.
We cannot have numbers with 4 digits or more without repeating the digits.
So, there are totally 8 numbers.