Combinatorics practice problems - RACE 1 - Easy

 Q1 - There are nine students (5 boys & 4 girls) in the class. In how many ways:
(1) Three distinct books can be distributed between two boys and one girl.
A: 5C2 * 4C1 * 3! = 240

(2) Three distinct books can be distributed between three students in which at least one is boy.
A: 3! * [5C1*4C2 + 5C2 * 4C1 + 5C3] = 480

(3) One book of Maths, two books of Physics and three books of Chemistry can be distributed (No student can get more than one book in same subject & books are distinct).
A: 9C1 * 9C2 * 9C3 * 3! * 2! = 326592
Explanation:
We have to choose 1 kid for Maths, 2 for Physics, 3 for Chemistry.
Now let's say you gave 2 physics books to K1,K2. So 2! for counting number of ways.
Similarly if Chemistry books C1,C2,C3 were given to K1,K2,K3 then again there are 3! different ways to do that.

Q2 - How many arithmetic progressions with 10 terms are there, whose first term is in the set {1, 2, 3, 4} and whose common difference is in the set {3, 4, 5, 6, 7} ?
A: 5*4 = 20

Q3 - How many of the four digit numbers are there whose at least one digit is even?
A: 8375
Solution:
Total 4 digit numbers = 9*10*10*10 = 9000
No even digit(all odd) = 5^4 = 625
9000 - 625 = 8375

Q4 - Mr. Rahul goes to an ATM to withdraw cash but he forgets his four digit ATM PIN. Find his maximum number of unsuccessful attempts to withdraw cash?
A: 9999 = 10^4 - 1

Q5 - Find the number of all five digit numbers whose product of digit is divisible by 5.
A: 
Total 5 digit numbers - all those 5 digit numbers which have neither 5 nor 0
= 9*10^4 - 8^5
= 57232

Q6 - Out of seven consonants and four vowels, how many words of six letters can be formed by taking at least four consonants (Assume that each ordered group of letter is a word). Each letter can be used exactly once.
A :
6! * [7C4*4C2 + 7C5*4C1 + 7C6*4C0]
= 6! * 301

Q7 - Out of 5 boys and 3 girls find the number of 4 member committees which can be formed if

(i) No restriction.
8C4 = 8*7*6*5/4*3*2 = 70

(ii) Committee contains at least 2 girls
3C2 * 5C2 + 3C3*5C1 = 35

(iii) Committee contains at least 2 boys and 1 girl.
5C2*3C2 + 5C3*3C1 = 60

(iv) Committee contains at most 3 boys.
3C3*5C1 + 3C2*5C2 + 3C1*5C3 = 5 + 30 + 30 = 65

(v) Committee contains boys in majority
5C4*3C0 + 5C3*3C1 = 5 + 30 = 35

Q8 - How many 4 digit numbers are there, without repetition of digits, if each number is divisible by 5?
Case 1: Last digit 0.
9*8*7

Case 2: Last digit 5
8*8*7

Total = 56*17 = 952

Q9 - Find the number of 6 digit numbers whose last two digits are even. (Repetition of digits are not allowed)
Solution:

Case 1: One of the last 2 digits is 0.
4 ways to choose the other digit.
2! to arrange.
Rest of the 4 digits: 8*7*6*5 = 1680
Total: 1680*4*2 = 13440

Case 2: 0 is not in last 2 digits.
4C2*2! = 12 ways to arrange last 2 digits.
For rest of the digits: 7*7*6*5 = 1470
Total: 1470*12 = 8820*2 = 16000 + 1640 = 17640

Finally: 13440 + 17640 = 31080

Q10 - Find the number of 5 digit numbers which can be formed such that (repetition allowed) :

(i) Total numbers
9*10^4 = 90,000

(ii) Number is even
Case 1: Last digit 0: 9*10^3 = 9000
Case 2: Last digit non zero: 4*9*10^3 = 36,000
Total: 45,000

(iii) Number contains the digit '3'
Total: 90,000
Reduce: Numbers containing no '3' = 8*9^4 = 52488
90,000 - 52,488 = 37,512

(iv) The number is palindrome
9*10*10*1*1 = 900

(v) No two consecutive digits are same
9*9*9*9*9 = 9^5 = 59049

Q11 - There are 'm' apples and 'n' oranges to be placed in a line such that the two extreme fruits being both oranges. Find the number of arrangements if

(i) Fruits of same species are different.
A. Pick 2 oranges to be placed at edges: nC2.
B. Arrange these 2 oranges: 2!

C. Remaining 'm' apples and 'n-2' oranges.
We have to pick 'm' places for apples from m+n-2 places: (m+n-2)C(m).
D. Arrange apples and oranges: (m)! (n-2)!

Finally: nC2 * 2!* (m+n-2)C(m) *  (m)! (n-2)!

(ii) Fruits of same species are alike.
Two ends are fixed with oranges.
Remaining 'm' apples and 'n-2' oranges.
We have to pick 'm' places for apples from m+n-2 places.
(m+n-2)C(m)

Q12 - Find the number of different six digit numbers that can be formed by using all the digits 0,1,1,2,2,2.
Case 1: First digit 0: 5!/(2!3!) = 10 -> Invalid shouldn't be added in final answer
Case 2: First digit 1: 5!/(3!) = 20
Case 3: First digit 2: 5!/(2!2!) = 30
 
Total: (20 + 30) = 50

Another way:
Find total ways and reduce the ones with 0 at the beginning.
6!/(3!2!) - 5!/(3!2!) = 50

Q13 - Let 5 letter words are formed using the letters of the word 'CALCULUS'. Then

(i) Find the total number of all such possible words.
Total letters: 8, 2C,2U,2L,1A,1S
Each letter different: 5!
2 Same, 3 different: 3C1*4C3*(5!/2!)
2 Same,2 Same, 1 different: 3C2*3C1*(5!/2!2!)
Total: 120 + 720+ 270 = 1110

(ii) Find the total number of words with exactly one alike pair of letters.
2 Same, 3 different: 3C1*4C3*(5!/2!) = 720

(iii) Find the total number of words with exactly two alike pair of letters
2 Same,2 Same, 1 different: 3C2*3C1*(5!/2!2!) = 270

Q14 - If the letters of the following words are arranged as in a dictionary, then find rank of the words
(i) Random (ii) Banana
Random:
A: 5!, D: 5!, M: 5!, N: 5!, O:5!
RAD: 3!
RAM: 3!
RAND.MO
RAND.OM
5*5! + 2*3! + 2 = 720 + 12 + 2 = 614

Banana:
3A,1B,2N
A: 5!/(2!2!)
BAA: 3!/2!
BANA.AN
BANA.NA

30 + 3 + 2 = 35

Q15 - How many four digit natural numbers not exceeding the number 4321 can be formed using the digits 1, 2, 3, 4, if repetition is allowed?
Starting with 1,2,3: 3*4^3 = 192
Starting with 41,42: 2*4^2 = 32
Starting with 431 : 4 
Then: 4321
Total: 192 + 32 + 4 + 1 = 229

Q16 - If repetition of digits is not allowed then find the sum of all four digit numbers which can be formed using the digits 0,1,2,3.
Total such numbers: 3*3*2*1 = 18
1023
1032
1203
1230
1302
1320
2013
2031
2103
2130
2301
2310
3012
3021
3102
3120
3201
3210
Total1: 6*(1000+2000+3000) = 36000
Total2: 4*(100+200+300) = 2400
Total3: 4*(10+20+30) = 240
Total4: 4*(6) = 24
Final: 38664

Q17 - If repetition of digits is allowed then find the sum of all four digit numbers which can be formed using the digits 6,7,8,9.
Total numbers: 4^4 = 256
First digit will be split in 6,7,8,9, each of them appearing 64 times. Similarly for each digit.
64*(6+7+8+9)*(1000+100+10+1)
= 64*30*1111
= 1920*1111
 = 2133120

Q18 - If the number of diagonals of polygon is 35, then find the number of sides of the polygon.
Solution:
Number of diagonals in n sided polygon = nC2 - n = Number of ways to choose 2 vertices - number of sides
n*(n-1)/2 - n = 35 => n^2 - 3n = 70 => n^2 - 3n - 70 = 0 => n = -7,10 => n = 10
Answer: 10

Q19 - There are 10 points on a plane of which 5 points are collinear. Also, no three of the remaining 5 points are collinear. Then find

(i) The maximum number of straight line joining these points
First 5 points: 1 line, each of them connects with other 5: 5*5. Total 1 + 25 = 26
Then for remaining 5 points, lines among themselves: 5C2 = 10
Total: 26 + 10 = 36

(ii) The maximum number of triangles formed joining these points.
Total triangles - when all 3 vertices are from first 5
10C3 - 5C3 = 120-10 =110

Q20 - The sides AB, BC and CA of a triangle ABC have 3, 4 and 5 interior points, respectively, on them. Find the number of triangle that can be constructed using these interior points.

Case 1: 1 vertex from each side: 3C1 * 4C1 * 5C1 = 60
Case 2: 2 vertices from 1, 1 from another: 3C2 * 9C1 + 4C2*8C1 + 5C2*7C1 = 27 + 48 + 70 = 145
Total: 205

Q21 - Let each side of smallest square of chess board is one unit in length.
(i) Find the total number of rectangles on the chess board

Simple solution:
There are 9 vertical and 9 horizontal lines.
We need to choose 2 from each.
9C2*9C2 = 36*36 = 1296.

Another Solution:
Find all combinations of AxB rectangles where A != B and A < B. Then double them.
A = 1
1x2: 7 in each row. 8 rows. 7*8 = 56.
1x3: 6*8
...
1x8: 1*8
Total where width is 1 = 8(1+2..7) = 8*7*8/2 = 224
A = 2
2x3: 7 ways to select consecutive row pairs. 6 such in each pair. = 7*6
2x4: 7*5
....
2x8: 7*1
Total with width 2 = 7(1+2...6) = 7*6*7/2 = 147
A = 3: 6*5*6/2 = 90
A = 4: 5*4*5/2 = 50
A = 5: 4*3*4/2 = 24
A = 6: 3*2*3/2 = 9
A = 7: 2*1*2/2 = 2

Sum them and multiply by 2 = 2*(2+9+24+50+90+147+224) = 2*(546) = 1092
Add to it the total squares computed below: 204
Total: 1296

(ii) Find the total number of squares on the chess board

8x8 chessboard.
Possible squares 1x1,2x2...8x8
1x1: 64
2x2: Choose 2 consecutive rows and keep shifting right => 7 * 7
3x3: Choose 3 consecutive rows and keep shifting right => 6*6
......
8x8 : 1
Finally: 1^2 + 2^2 + 3^2 ... 8^2 = 1+4+9+16+25+36+49+64 = 5+25+25+49+100 = 204

Q22 - Determine the number of paths from the origin to the point (5,6) in the cartesian plane.

(i) If paths consist only of steps going 1 unit North and 1 unit East.
So we have to make strings(words) made up of 5 E's and 6 N's.
For e.g. EEEEENNNNNN
11!/(5!6!) = 462

(ii) Which always pass through the point (2,1) in paths consisting only of steps going 1 unit North and 1 unit East.
First make a string with 2 E's and 1N and then 3E's and 5N's.
3!/2! * 8!/(3!5!) = 168

(iii) Which never pass through the point (2,1) in paths consisting only of steps going 1 unit North and 1 unit East.
It's simply (i) - (iii) above. 462 - 168 = 294

23. Let $X = \{1, 2, 3, \ldots, 12\}$. Find the number of ordered pairs $\{A, B\}$ such that $A \subseteq X, B \subseteq X$.

(i) $A \ne B$

(ii) $A \cap B = \{2, 3, 5, 7, 8\}$

(iii) $A \ne B$ and $A \cap B = \{2, 3, 5, 7, 8\}$

---

Solution:
(i) So all possible values of A = all possible subsets of X. Same for B.
Number of possible subsets of X = 2^12. Why? Because each element can or cannot be there in the subset.
So 2^12 possibilities for both A,B.
Total 2^12 * 2^12 = 4^12.
Reduce those cases when A = B. It means once A is fixed, only 1 way to choose B.
So 4^12  - 2^12 is the final answer.

(ii) So 2,3,5,7,8 are present in both A and B.
Remaining elements can either be in A or in B but not in both. Else the intersection won't hold true.
So each of the remaining elements can have 3 states: Either in A, Or in B, Or in neither.
3^7 is the final answer.

(iii) To answer this let's subtract from (ii) when A = B. Now if A = B then A = B = A intersection B.
It means we can't add or remove any element from their intersection. So there is only 1 possibility.
So (ii) - 1 = 3^7 - 1

Q24 - Using 6 different flags, how many different signals can be made by using at least 3 flags, arranging one above the other?

Solution:
6C3*3! + 6C4*4! + 6C5*5! + 6C6*6! = 120 + 15*24 + 720 + 720 = 20 + 1440 + 360 = 1920

Q25 - Number of words that can be formed with the letters of the word 'STRANGE' which neither starts with S nor ends with E, is:
Solution:
Total: 7!
Starting with 'S': 6!
Ending with 'E': 6!
Starting with 'S', ending with 'E': 5!
7! - (6! + 6! - 5!) = 5! - 2.6! + 7! = 5!(1 - 12 + 42) = 120*31 = 10*(310+62) = 3720

Q26 - Eight cards bearing number 1,2,3,4,5,6,7,8 are well shuffled. Then in how many cases the top 2 cards will form a pair of twin prime numbers?
Twin prime numbers: Prime numbers with gap of 1. For e.g. 3,5 or 5,7
So only 4 choices for top 2 cards: 3,5 or 5,3 or 5,7 or 7,5
Answer: 4*6! = 4*720 = 2880

Q27 - 8 chairs are numbered from 1 to 8. Two women & 3 men wish to occupy one chair each. First the women choose the chairs from amongst the chairs marked 1 to 4 and then men select from the remaining chairs. The number of possible arrangements is:
4C2*2!*6C3*3! = 6*2*20*6 = 1440

Q28 - A rack has 5 different pair of shoes. The number of ways in which 4 shoes can be selected from it so that there will be no complete pair is:

5C4*2C1*2C1*2C1*2C1 = 80

Q29: Passengers are to travel by a double decker bus which can accommodate 13 in the upper deck and 7 in the lower deck. The number of ways that they can travel if 5 refuse to sit in the upper deck and 8 refuse to sit in the lower deck, is (arrangement of passenger on seats is not necessary):
Total passengers: 20
Remaining passengers: 7
Remaining seats in lower deck: 2
Remaining seats in upper deck: 5
So we need to choose 2 passengers out of 7 to go on lower deck: 7C2 = 21

Q30 - The number of ways of choosing a committee of two women and three men from five women and six men, if Mr. A refuses to serve on the committee if Mr. B is a member and Mr. B can only serve if Miss C is the member of the committee is:
Case 1: Mr. B is not a member: 5C3*5C2 = 100
Case 2: Mr. B is a member => Miss C is also there, Mr. A is not a member.
 = 4C2 * 4C1 = 24
Total: 124

Q31 - The total number of ways of selecting 3 numbers from the set of first 50 natural numbers such that their sum is divisible by 3 are:
Group by mod 3.
1: 17
2: 17
0: 16

4 cases:
000: 16C3
111: 17C3
222: 17C3
012: 16C1 * 17C1 * 17C1

Add them to get the answer.

Q32 - There are 2 women participating in a chess tournament. Every participant played 2 games with the other participants. The number of games that the men played between themselves exceeded by 66 as compared to the number of games that the men played with the women. Then the number of participants & the total numbers of games played in the tournament are respectively:
MM = MW + 66
Let's there are n men.
MM = nC2*2 = n*(n-1)
MW = n.2.2 = 4n
n^2 - n = 4n + 66
=> n^2 - 5n - 66 = 0
=> (n - 11)(n+6) = 0
=> n = 11
Cross check:
MM = 11C2*2 = 110
MW = 11*2*2 = 44
WW = 2
Diff = 66
Final answer: 13,156

Q33 - Out of 16 players of a cricket team , 4 are bowlers and 2 are wicket keepers. A team of 11 players is to be chosen so as to contain at least 3 bowlers and at least 1 wicket keeper. The number of ways in which the team can be selected, is:
Solution: 
3B1W8Ba: 4C3*2C1*10C7 =  960
3B2W7Ba: 4C3*2C2*10C6 = 840
4B1W7Ba: 4C4*2C1*10C6 = 420
4B2W6Ba: 4C4*2C2*10C5 = 252 

Total: 2472

Q34 - A word has 4 identical letters and some different letters. If the total number of words that can be formed with the letters of the word is 210, then the number of different letters in the word is:
Solution:
(n+4)!/4! = 210
(n+4)! = 4!*210 = 4!*5*6*7 = 7!
=> n = 3

Q35 - There are 6 periods in a working day of a school. Number of ways in which 5 subjects can be arranged if each subject is allotted at least one period and no period remains vacant, is:
Solution:
Let's say the 5 subjects are A,B,C,D,E
Let's say first we choose A for the extra period.
6!/2! ways to arrange these 6 letters.
And this will happen 5 times - once for each subject.
So 5*6!/2! = 1800

Q36 - The sum of all the six digit numbers formed using the digits 2, 3, 3, 4, 4, 4 is:
Total: 6!/2!3! = 60
2 at each position: 5!/2!3! = 10 times
3 at each position: 5!/3! = 20 times
4 at each position: 5!/2!2! = 30 times
First digit sum: 10^5*(2*10 + 3*20 + 4*30) = 10^5*(200)
Similarly for all digits => 200*(111111) = 22222200

Q37: 
Number of words that can be formed using the letters of the word "ENGINEERING" and starts as well as end with a vowel, is:
Solution:
Total letters: 11
3E, 2G, 2I, 3N, 1R
Vowels: 3E, 2I
Others: 2G, 3N, 1R

Starts with E, ends with E: 9!/2!2!3!
Starts with E, ends with I: 9!/2!2!3!
Starts with I, ends with E: 9!/2!2!3!
Starts with I, ends with I: 9!/3!2!3!

Total: (9!/2!2!3!3!)(3!*3 + 2!) = 9!*20/(2.2.6.6) = 9!.5/6.6 = 8!*5/4 = 7!*10 = 50400

Q38 - 

How many nine digit numbers can be formed using the digits 2,2,3,3,5,5,6,6,6 so that the odd digits occupy even places?

Solution:
Total 9 digits:
Even: 2,2 6,6,6
Odd: 3,3 5,5
4 even places, 5 odd places.
Arranging odd on even: 4!/2!2!
Rest: 5!/2!3!
Multiply both: 5!4!/48 = 120*12*2/48 = 60

Q39 - 
Number of ways in which 5 A's and 6 B's can be arranged in a row such that the arrangement is a palindrome, is:
Solution:
A has to be in the middle.
And remaining letters split equally on either side.
So 2A's and 3B's on each side.
5!/2!3! = 10

Q40 - 
The number of words of 4 letters that can be formed using the letters of the word "PARALLELOPIPED" is
Solution:
Total letters: 14
3P, 2A, 1R, 3L, 2E, 1O, 1I, 1D

1R, 1O, 1I, 1D, 2A, 2E, 3P, 3L
4 letter word ways:
All 4 distinct: 8C4 * 4! = 8.7.6.5 = 56*30 = 1680
2 Same, 2 different: 4C1*7C2*4!/2! = 24*7*6 = 1008
2 Same, 2Same: 4C2 * 4!/2!.2! = 36
3 Same, 1 different: 2C1*7C1*4!/3! = 56
Total: 2780

Q41 - There are balls available in 3 different colors (at least four of each color). Balls are all alike except of the color.
'm' denotes the number of arrangements of four balls if no arrangement consists of all balls of same color. 'n' denotes the corresponding figure when every arrangement consists of balls of each color, then the value of (m – n) is equal to:

Solution:
n = 3C1*4!/2! = 36
m = total - 3(all balls of same color)
total = 3^4 = 81
m = 78
m - n = 78 - 36 = 42

Q42 - If all words formed using the letters of the word "CORONA" are arranged alphabetically, then 348th word of the sequence is:
Total 6 letters.
1A,1C,1N,2O,1R
Total words: 6!/2! = 360
So we should proceed in reverse order.
Starting with R: 5!/2! = 60
So it starts with R.
RO: 4! = 24
ROO:3! = 6
RON:3! = 6
Just previous word is the answer.
ROCONA

Q43 - Consider the five points comprising of the vertices of a square and the intersection point of its diagonals. Number of triangles can be formed using these points, is:
Solution:
Total possible: 5C3 = 10
But 2 have to be removed from this.
Let's say O is the intersection of diagonals in ABCD.
Then AOC are collinear and hence not valid triangle. Similarly BOD.

Q44 - There are six line segments of length 2, 3, 4, 5, 6, 7 units, the number of triangles that can be formed by these line segments is:
Solution:
2,3,4
2,4,5
2,5,6
2,6,7

3,4,5
3,4,6
3,5,6
3,5,7
3,6,7

4,5,6
4,5,7
4,6,7

5,6,7
Total: 13

Q45 -  The maximum number of points of intersection of 6 different circles and 4 different lines are:
Circle X Circle = 6C2*2 = 30
Line X Line = 4C2 = 6
Circle X Line = 6*4*2 = 48
Total: 84