Combinatorics
Question 1 
If the ordinary generating function of a sequence is , then a_{3}  a_{0} is equal to ________.
15  
16  
17  
18 
Question 2 
Which one of the following is a closed form expression for the generating function of the sequence {a_{n}}, where a_{n} = 2n+3 for all n = 0, 1, 2, …?
3/(1x)^{2}  
3x/(1x)^{2}  
2x/(1x)^{2}  
3x/(1x)^{2} 
Question 3 
The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is _________.
271  
272  
273  
274 
Let A = number divisible by 3
B = numbers divisible by 5
C = number divisible by 7
We need to find “The number of integers between 1 and 500 that are divisible by 3 or 5 or 7" i.e., A∪B∪C
We know,
A∪B∪C = A+B+CA∩BA∩CB∩C+A∩B
A = number of integers divisible by 3
[500/3 = 166.6 ≈ 166 = 166]
B = 100
[500/5 = 100]
C = 71
[500/7 = 71.42]
A∩B = number of integers divisible by both 3 and 5 we need to compute with LCM (15)
i.e.,⌊500/15⌋ ≈ 33
A∩B = 33
A∩C = 500/LCM(3,7) 500/21 = 23.8 ≈ 28
B∩C = 500/LCM(5,3) = 500/35 = 14.48 ≈ 14
A∩B∩C = 500/LCM(3,5,7) = 500/163 = 4.76 ≈ 4
A∪B∪C = A+B+CA∩BA∩CB∩C+A∩B∩C
= 166+100+71332814+4
= 271
Question 4 
Let a_{n} be the number of nbit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for a_{n}?
a_{n} = a_{(n1)} + 2a_{(n2)}  
a_{n} = a_{(n1)} + a_{(n2)}  
a_{n} = 2a_{(n1)} + a_{(n2)}  
a_{n} = 2a_{(n1)} + 2a_{(n2)} 
If n=1, we have {0,1}
# Occurrences = 2
If n=2, we have {00,01,10}
# Occurrences = 3
If n=3, we have {000,001,010,100,101}
# Occurrences = 5
It is evident that a_{3} = a_{1} + a_{2}
Similarly, a_{n} = a_{n1} + a_{n2}
Question 5 
The coefﬁcient of x^{12} in (x^{3} + x^{4} + x^{5} + x^{6} + ...)^{3} is _________.
10  
11  
12  
13 
⇒ [x^{3}(1 + x + x^{2} + x^{3} + ...)]^{3}
= x^{9}(1 + x + x^{2} + x^{3} + ...)^{3}
First Reduction:
As x^{9} is out of the series, we need to find the coefficient of x^{3} in (1 + x + x^{2} + ⋯)^{3}
Here, m=3, k=3, the coefficient
= ^{5}C_{3} = 5!/2!3! = 10
Question 6 
Consider the recurrence relation a_{1} = 8, a_{n} = 6n^{2} + 2n + a_{n1}. Let a_{99} = K × 10^{4}. The value of K is ___________.
198  
199  
200  
201 
Replace a_{(n1)}
⇒ a_{n} = 6n^{2} + 2n + 6(n1)^{2} + 2(n1) + 6(n2)^{2} + 2(n2) + ⋯ a_{1}
Given that a_{1} = 8, replace it
⇒ a_{n} = 6n^{2} + 2n + 6(n1)^{2} + 2(n1) + 6(n2)^{2} + 2(n2) + ⋯8
= 6n^{2} + 2n + 6(n1)^{2} + 2(n1) + 6(n2)^{2} + 2(n2) + ⋯ + 6(1)^{2} + 2(1)
= 6(n^{2} + (n1)^{2} + (n2)^{2} + ⋯ + 2^{2} + 1^{2}) + 2(n + (n1) + ⋯1)
Sum of n^{2} = (n(n+1)(2n+1))/6
Sum of n = (n(n+1))/2
= 6 × (n(n+1)(2n+1))/6 + 2×(n(n+1))/2
= n(n+1)[1+2n+1]
= n(n+1)[2n+2]
= 2n(n+1)^{2}
Given a_{99} = k×10^{4}
a_{99} = 2(99)(100)^{2} = 198 × 10^{4}
∴k = 198
Question 7 
The number of divisors of 2100 is ______.
36  
37  
38  
39 
= 2^{2}+3×5^{2}×7 (i.e., product of primes)
Then the number of divisions of 2100 is
(2+1)∙(1+1)∙(2+1)∙(1+1) i.e., (3)(2)(3)(2) i.e., 36.
Question 8 
The number of 4 digit numbers having their digits in nondecreasing order (from left to right) constructed by using the digits belonging to the set {1, 2, 3} is _____.
15  
16  
17  
18 
1 1 1 1
1 1 1 2
1 1 1 3
1 1 2 2
1 1 2 3
1 1 3 3
1 2 2 2
1 2 2 3
1 2 3 3
1 2 3 3
1 3 3 3
2 2 2 2
2 2 2 3
2 2 3 3
2 3 3 3
3 3 3 3
Hence, total 15 4digit no. are possible.
Question 9 
A pennant is a sequence of numbers, each number being 1 or 2. An npennant is a sequence of numbers with sum equal to n. For example, (1,1,2) is a 4pennant. The set of all possible 1pennants is {(1)}, the set of all possible 2pennants is {(2), (1,1)}and the set of all 3pennants is {(2,1), (1,1,1), (1,2)}. Note that the pennant (1,2) is not the same as the pennant (2,1). The number of 10pennants is ________.
89  
90  
91  
92 
Single two: 211111111 ⇒ 9!/8!1! = 9 pennants
Two twos: 22111111 ⇒ 8!/6!2! = 28
Three twos: 2221111 ⇒ 7!/3!4! = 35
Four twos: 222211 ⇒ 6!/4!2! = 15
Five twos: 22222 ⇒ 1
Total = 89 pennants.
Question 10 
The number of distinct positive integral factors of 2014 is _________.
0.26  
0.27  
8  
0.29 
= 2' × 19' × 53'
Now number of distinct integral factors of 2014 will be,
(1+1)×(1+1)×(1+1) = 2×2×2 = 8
Question 11 
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i,j) then it can move to either (i+1,j) or (i,j+1).
How many distinct paths are there for the robot to reach the point (10,10) starting from the initial position (0,0)?
2^{20}  
2^{10}  
None of the above 
So now we have 10 u's and 10 r's, i.e.,
uuuuuuuuuurrrrrrrrrr
So, finally the no. of arrangements of above sequences is,
Question 12 
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i,j) then it can move to either (i+1,j) or (i,j+1).
Suppose that the robot is not allowed to traverse the line segment from (4,4) to (5,4). With this constraint, how many distinct paths are there for the robot to reach (10,10) starting from (0,0)?
2^{9}  
2^{19}  
So, no. of paths possible if line segment from (4,4) to (5,4) is taken is,
= paths possible from (0,0) to (4,4) * paths possible from (5,4) to (10,10)
= {uuuurrrr} * {uuuuuurrrrr}
Hence, the final answer is
Question 13 
Given a set of elements N = {1, 2, ..., n} and two arbitrary subsets A⊆N and B⊆N, how many of the n! permutations π from N to N satisfy min(π(A)) = min(π(B)), where min(S) is the smallest integer in the set of integers S, and π(S) is the set of integers obtained by applying permutation π to each element of S?
(nA ∪ B) A B  
(A^{2}+B^{2})n^{2}
 
n!(A∩B/A∪B)  
Two arbitrary subsets A⊆N and B⊆N.
Out of n! permutations π from N to N, to satisfy
min(π(A)) = min (π(B))
*) π(S) is the set of integers obtained by applying permutation π to each element of S.
If min(π(A)) =min (π(B)), say y = π(x) is the common minimum.
Since the permutation π is a 1to1 mapping of N,
x ∈ A∩B
∴ A∩B cannot be empty.
⇒ y = π(x)
= π(A∩B) is the minimum of π(A∪B) is the minimum of π(A) and π(B) are to be same.
You can think like
*) If the minimum of π(A) and π(B) are same [min π(A)] = min [π(B)]
then min(π(A∩B)) = min(π(A∪B))
∴ Total number is given by n! A∩B/A∪B
*) Finally
Considering all possible permutations, the fraction of them that meet this condition π(A∩B) / π(A∪B)
[The probability of single permutation].
Ex: N = {1, 2, 3, 4} A = {1, 3} B = {1, 2, 4}
Since π is one to one mapping
π(A∩B) = A∩B
∴ π(A) = {1, 2}
π(B) = {1, 4, 3}
π(A∩B) = {1}
π(A∪B) = {1, 2, 3, 4}
4! × 1/4 = 6
Question 14 
Let , where x<1. What is g(i)?
i  
i+1  
2i  
2^{i} 
Put g(i) = i+1
S = 1 + 2x + 3x^{2} + 4x^{3} + .....
Sx = 1x + 2x^{2} + 3x^{3} + 4x^{4} + ......
S  Sx = 1 + x + x^{2} + x^{3} + .....
[Sum of infinite series in GP with ratio < 1 is a/1r]
S  Sx = 1/(1x)
S(1x) = 1/(1x)
S = 1/(1x)^{2}
Question 15 
Mala has a colouring book in which each English letter is drawn two times. She wants to paint each of these 52 prints with one of k colours, such that the colourpairs used to colour any two letters are different. Both prints of a letter can also be coloured with the same colour. What is the minimum value of k that satisfies this requirement?
9  
8  
7  
6 
Each is printed twice the no. of letters = 26×2 = 52
If Mala has k colours, she can have k pairs of same colours.
She also can have ^{k}C_{2} different pairs in which each pair is having different colours.
So total no. of pairs that can be coloured = k+^{k}C_{2}
k+^{k}C_{2} ≥ 26
k+k(k1)/2 ≥ 26
k(k+1)/2 ≥ 26
k(k+1) ≥ 52
k(k+1) ≥ 7*8
k≥7
Question 16 
n couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of different gatherings possible at the party is
i) Both husband and wife comes
ii) Only wife comes
iii) Both are not come
The no. of different gatherings possible at party is
= 3 * 3 * 3 * 3 * ... n times
= 3^{n}
Question 17 
m identical balls are to be placed in n distinct bags. You are given that m ≥ kn, where, k is a natural number ≥1. In how many ways can the balls be placed in the bags if each bag must contain at least k balls?
. So option (B) is correct.
Question 18 
(a) In how many ways can a given positive integer n ≥ 2 be expressed as the sum of 2 positive integers (which are not necessarily distinct). For example, for n = 3, the number of ways is 2, i.e., 1+2, 2+1. Give only the answer without any explanation.
(b) In how many ways can a given positive integer n ≥ 3 be expressed as the sum of 3 positive integers (which are not necessarily distinct). For example, for n = 4, the number of ways is 3, i.e., 1+2+1, 2+1+1. Give only the answer without any explanation.
(c) In how many ways can a given positive integer n ≥ k be expressed as the sum of k positive integers (which are not necessarily distinct)? Give only the answer without explanation.
Theory Explanation is given below. 
Question 19 
How many 4digit even numbers have all 4 digits distinct?
2240  
2296  
2620  
4536 
If last digit is (2, 4, 6, 8)
Total possibilities = 504 + 1792 = 2296
Question 20 
The minimum number of cards to be dealt from an arbitrarily shuffled deck of 52 cards to guarantee that three cards are from some same suit is
3  
8  
9  
12 
No. of suits = 4(P)
Apply pigeon hole principal.
Then number of pigeons = n
floor [(n1)/P] + 1 = 3
floor [(n1)/P] = 2
floor [(n1)] = 8
floor (n) = 8 + 1
n ≥ 9
Minimum no. of cards, n = 9
Question 21 
The number of binary strings of n zeroes and k ones that no two ones are adjacent is
^{n1}C_{k}  
^{n}C_{k}  
^{n}C_{k+1}  
None of the above 
XOXOXOXOXOXOX
n+1 gaps can be possible, where 1's can be placed so that no two one's are adjacent. So, no. of ways in which k 1's can be placed in n+1 gaps are,
^{n+1}C_{k}
Question 22 
Two girls have picked 10 roses, 15 sunflowers and 15 daffodils. What is the number of ways they can divide the flowers amongst themselves?
1638  
2100  
2640  
None of the above 
^{n+r1}C_{r1}
So for 10 roses,
^{10+21}C_{21} = ^{11}C_{1} = 11
For 15 sunflowers,
^{15+21}C_{21} = ^{16}C_{1} = 16
For 15 daffodils,
^{15+21}C_{21} = ^{16}C_{1} = 16
∴ The final answer is,
11×16×16 = 2816
Question 23 
The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L’s are indistinguishable, is _______.
12 
― ― ― ― ―
Given: L I L A C
The derangement formula ⎣n!/e⎦ cannot be directly performed as there are repeated characters.
Let’s proceed in regular manner:
The L, L can be placed in other ‘3’ places as
(1) Can be arranged such that A, I, C be placed in three positions excluding ‘C’ being placed at its own position, which we get only 2×2×1 = 4 ways.
Similarly (2) can be filled as A, I, C being placed such that 4th position is not filled by A, so we have 2×2×1 = 4 ways. Similarly with (3).
Totally, we get 4+4+4 = 12 ways.
Question 24 
Choose the correct alternatives (More than one may be correct).
The number of ways in which 5 A's, 5 B's and 5 C's can be arranged in a row is:15!/(5!)^{3}  
15!  
(15/5)  
15!(5!3!) 
Question 25 
The exponent of 11 in the prime factorization of 300! is
27  
28  
29  
30 
Question 26 
In how many ways can b blue balls and r red balls be distributed in n distinct boxes?
C(n+b1, b) = (n+b1)!/ (n1)!b!
No. of red distributed to n boxes is
(n+r1, r) = (n+r1)!/ (n1)!r!
Total no. of ways = (n+b1)!/(n1)!b! * (n+r1)!/(n1)!r!
= (n+b1)!(n+r1)!/(n1)!b!(n1)!r!
Question 27 
Consider the sequence <x_{n}>, n>= 0 defined by the recurrence relation x_{n + 1} = c . x_{n}^{2} 2, where c > 0.
Suppose there exists a nonempty, open interval (a, b) such that for all x_{0} satisfying a < x_{0} < b, the sequence converges to a limit. The sequence converges to the value?
2  
Then,
x_{1} = c ⋅ (x_{0})^{2}  2 = 1 ⋅ (1)^{2}  2 = 1
x_{2} = c ⋅ (x_{1})^{2}  2 = 1 ⋅ (1)^{2}  2 = 1
So, the value converges to 1, which is equal to
Exactly, only (B) is answer. As all the term of x converges to 1.
Question 28 
Consider the sequence <x_{n}>, n>= 0 defined by the recurrence relation x_{n + 1} = c. x_{n}^{2} 2, where c > 0.
For which of the following values of c, does there exist a nonempty open interval (a,b) such that the sequence x_{n}, converges for all x_{0} satisfying a < x_{0}
 (i) 0.25
(ii) 0.35
(iii) 0.45
(iv) 0.5
(i) Only  
(i) and (ii) only  
(i), (ii) and (iii) only  
(i), (ii), (iii) and (iv) 
From the recurrence we should have c(x_{n})^{2}  x_{n}  2 < 0
For all the above values of c we have above equation as negative.
Question 30 
Given,
(Assume x1,x2,x3 as a,b,c)
Question 31 
32  
128  
160  
192 
→ Number of bit strings of length 8 that end with 00: 26 = 64.
→ Number of bit strings of length 8 that start with 1 and end with 00: 25 = 32.
→ Applying the subtraction rule, the number is 128+64−32 = 160
Question 32 
9  
8  
7  
6 
Each is printed twice the no. of letters = 26×2 = 52
If Mala has k colours, she can have k pairs of same colours.
She also can have^{ k} C _{2} different pairs in which each pair is having different colours.
So total no. of pairs that can be coloured = k+ ^{ k } C _{2}
k+ ^{k} C _{2} ≥ 26
k+k(k1)/2 ≥ 26
k(k+1)/2 ≥ 26
k(k+1) ≥ 52
k(k+1) ≥ 7*8
k≥7
Question 33 
6  
23  
61  
72  
91 
Question 34 
12  
7  
144  
264 
The number of bus lines between b and c =3
The number of possible combinations between a and c going through b are 4 * 3 = 12.
if you're talking about round trip, he has 12 possible ways to get there and 12 possible ways to get back, so the total possible ways is 12 * 12 = 144.
Question 35 
a _{r} =(3) ^{r} +(1)^{ r}  
2a _{r} =(2)^{ r} /3 (1)^{ r}  
a_{ r} =3^{ r+1} (1)^{ r}  
a _{r} =3(2)^{ r} (1)^{ r} 
For r =2, a _{2}= a_{ 21} +2a_{ 22} =a _{1} +2a_{ 0} =7+2*2=7+4=11
For r=3,a_{ 3}= a_{ 31} +2a_{ 32} =a_{ 2} +2a_{ 1} =11+2*7=11+14=25
From the above options , Substitute the r values 0,1,2,3 then option D gives the solution to recurrence relation.
Question 36 
How many ways are there to arrange the nine letters of the word ALLAHABAD?
4560
 
4000
 
7560
 
7500

Step2: Total number of alphabets! / alphabets are repeating using formula (n!) / (r1! r2!..).
Step3: Repeating letters are 4A's and 2L's
= 9! / (4!2!)
= 7560
Question 37 
How many bit strings of length eight (either start with a 1 bit or end with the two bits 00) can be formed?
64  
255  
160  
128 
1. Number of bit strings of length eight that start with a 1 bit: 2^{7} = 128
2. Number of bit strings of length eight that end with bits 00: 2^{6} = 64
3. Number of bit strings of length eight that start with a 1 bit and end with bits 00: 2^{5} = 32
The number is 128+64+32 = 160
Question 38 
What is the solution of the recurrence relation a_{n} = 6a_{n1}  9a_{n2} with initial conditions a_{0}=1 and a_{1}=6?
a_{n} = 3^{n} + 3n^{2}
 
a_{n} = 3^{n} + n3^{n}
 
a_{n} = 3^{n} + 3n^{n}
 
a_{n} = n^{3} + n3^{n}

→ Suppose that the characteristic equation r^{k} −c_{1}r^{k}−1 −···−c_{k} = 0 has k distinct roots r_{1}, r_{2}, ..., r_{k}.
→ Then, a sequence {a_{n}} is a solution of the recurrence relation: a_{n} = c_{1}a_{n−1} + c_{2}a_{n−2} + ··· + c_{k}a_{n−k}
→ if and only if a_{n} = α_{1}r^{n}_{1} + α_{2}r^{n}_{2} + ··· + α_{k} r^{n}_{k} for n = 0,1,2,..., where α_{1}, α_{2}, ..., α_{k} are constants.
→ r^{2} − 6r + 9 = 0 has only 3 as a root.
→ So the format of the solution is a_{n} = α_{1}3^{n} + α_{2}n3^{n}.
→ Need to determine α_{1} and α_{2} from initial conditions:
a_{0} = 1 = α_{1}
a_{1} = 6 = α_{1}3 + α_{2}3
Solving these equations we get α_{1}=1 and α_{2}=1
Therefore, a_{n} = 3^{n} + n3^{n}.
Question 39 
What is the minimum number of students in a class to be sure that three of them are born in the same month?
24  
12  
25  
13 
Question 40 
a_{ r} =(3)_{ r} +(1)_{ r}  
2a _{r} =(2)^{ r} /3 (1)^{ r}  
a_{ r} =3^{ r+1} (1)^{ r}  
a _{r} =3(2)_{ r} (1)_{ r} 
● For r =2, a _{2}= a _{21} +2a_{ 22} =a _{1} +2a_{ 0} =7+2*2=7+4=11 ● For r=3,a 3= a 31 +2a 32 =a 2 +2a 1 =11+2*7=11+14=25
● From the above options ,Substitute the r values 0,1,2,3 then option D gives the solution to recurrence relation.
Question 41 
How many 3 digit numbers are there with all different odd digits?
16  
48  
54  
60 
• But for every hundreds, maximum of 4 tens is possible (avoiding the duplicate of digit used in hundreds)
• And each of these 4 tens, maximum of 3 units is possible (avoiding the duplicate of digits used in tens)
• 5 * 4 * 3 = 60
Question 42 
In how many ways can a committee of 4 people be chosen from a group of 12?
495  
595
 
395
 
295

C(n,r) = C(12,4)
= 12! / [(4!(12−4)!)]
= 495
Hence, a committee of 4 people be selected from a group of 12 people in 495 ways.
Question 43 
The sum of n terms of 1/(1*2) + 1/(2*3) + 1/(3*4) + ... is
(n+1)/n
 
n/(n+1)
 
n/(2n+1)
 
(2n+1)/n

where
1st term = 1/(1*2)
2nd term = 1/(2*3)
3rd term = 1/(3*4)
.
.
.
.
nth term = 1/(n*(n+1))
nth term = 1/(n*(n+1))
i.e. the kth term is of the form 1/(k*(k+1))
which can further be written as kth term = 1/k  1/(k+1)
So, sum upto n terms can be calculated as:
(1/1  1/1+1) + (1/2  1/2+1) + (1/3  1/3+1) + ......... + (1/n1  /1n) + (1/n  1/n+1)
= (1  1/2) + (1/2  1/3) + (1/3  1/4) + ......... + (1/n1  1/n) + (1/n  1/n+1)
= 1  1/n+1
= ((n+1)  1)/n+1
= n/n+1
Question 44 
How many integers are between 1 and 200 which are divisible by any one of the integers 2,3 and 5(Hint: use set operation)?
125  
145  
146  
136 
B) numbers divisible by 3: 200/3 = 66
C) numbers divisible by 5: 200/5 = 40
Counting twice:
AB) numbers divisible by 6: 200/6 = 33
AC) numbers divisible by 10: 200/10 = 20
BC) numbers divisible by 15: 200/15 = 13
Counting 3 times:
ABC) numbers divisible by 30: 200/30 = 6
Total of numbers = A + B + C  AB  AC  BC + ABC = 100 + 66 + 40  33  20 13 + 6 = 146
Question 45 
The number of two digit numbers divisible by the product of digits is:
8  
14  
13  
5 
12=1*2=2 which is a factor of 12
15=1*5=5 which is a factor of 15
24=2*4=8 which is a factor of 24
36=3*6=12 which is a factor of 36
Question 46 
The sum of the series: (1/2) + (1/3) + (1/4)  (1/6) + (1/8) + (1/9) + (1/16)  (1/12) + ... + α is:
(1/2)  log(√2)^{3}
 
1 + log(√2)^{3}
 
3/2  
1/2 + log(√2)^{3}

Question 47 
F _{00} (n) = ((10 ∗ F _{00} (n – 1) + 100)/ F _{00} (n – 2)) for n ≥ 2 Then what shall be the set of values of the sequence F_{ 00} ?
(1, 110, 1200)  
(1, 110, 600, 1200)  
(1, 2, 55, 110, 600, 1200)  
(1, 55, 110, 600, 1200) 
Sequence F _{00} defined as
F _{00} (0) = 1,
F _{00} (1) = 1,
F _{00} (n) = ((10 ∗ F _{00} (n – 1) + 100)/ F _{00} (n – 2)) for n ≥ 2
Let n=2
F _{00} (2) = (10 * F _{00} (1) + 100) / F _{00} (2 – 2)
= (10 * 1 + 100) / 1
= (10 + 100) / 1
= 110
Let n=3
F _{00} (3) = (10 * F _{00} (2) + 100) / F _{00} (3 – 2)
= (10 * 110 + 100) / 1
= (1100 + 100) / 1
= 1200
Similarly, n=4
F _{00} (4) = (10 * F _{00} (3) + 1_{00}) / F _{00} (4 – 2)
= (12100) / 110
= 110
F _{00} (5) = (10 * F _{00} (4) + 100) / F _{00} (5 – 2)
= (10*110 + 100) / 1200
= 1
The sequence will be (1, 110, 1200,110, 1).
Question 48 
0 and 100 and –6 and 34
16 and 6  
17 and 6  
17 and 7  
16 and 7 
0 and 100 → Counting sequentially:
0,6,12,18,24,30,36,42,48,54,60,66,72,78,84,90,96 Total=17
–6 and 34 → Counting sequentially: 6,0,6,12,18,24,30
Total=7
Method2: 0 and 100 → Maximum number is 100. Divide ⌊100/6⌋ = 16+1 =17
Here, +1 because of 0.
–6 and 34 → Maximum number is 34. Divide ⌊34/6⌋ = 5+1+1 =7
Here, +1 because of 0 and +1 for 6
Question 49 
(a) “If Gora gets the job and works hard, then he will be promoted. If Gora gets promotion, then he will be happy. He will not be happy, therefore, either he will not get the job or he will not work hard”.
(b) “Either Puneet is not guilty or Pankaj is telling the truth. Pankaj is not telling the truth, therefore, Puneet is not guilty”.
(c) If n is a real number such that n >1, then n^{ 2} >1. Suppose that n^{ 2} >1, then n >1.
(a) and (c)  
(b) and (c)  
(a), (b) and (c)  
(a) and (b) 
Question 50 
66  
330  
495  
99 
→ There is no specification about positive,negative digits and also repetition of digits.
→ We are assuming the positive digits which is greater than or equal to 0.
→ The starting digit of the string should not be zero. We will also consider the repetition of digits.
→ Example of such strings are 70000,61000,60100,60010..,
→ The possible number of strings are C((n+r1),(r1))
→ From the given data n=7,r=5 then We have to fine C(11,4) which is equal to 330
Question 51 
1001  
3876  
775  
200 
→ From the given question, n=15, r=5 We need to calculate C(14,4) and it’s value is 1001.
Question 52 
“ x ≥ 6, if x ^{2} ≥ 5 and its proof as:
If x ≥ 6, then x 2 = x.x ≥ 6.6 = 36 ≥ 25
Which of the following is correct w.r.to the given proposition and its proof?
(a)The proof shows the converse of what is to be proved.
(b)The proof starts by assuming what is to be shown.
(c)The proof is correct and there is nothing wrong.
(a) only  
(c) only  
(a) and (b)  
(b) only 
Question 53 
2  
20  
11  
None of these 
→ If you pick shoes from one to ten individual shoes, there may be chance of getting same individual shoes.
→ There is no guarantee that getting one proper pair from 10 individual shoes.
→ If You pick 11 shoes, then there may chance of 10 individual shoes of same type and one individual shoe of another type. So we will get at least one proper pair shoe from 11 individual shoes.
Question 54 
pigeon hole principle  
recursion  
divide and conquer technique  
iteration 
→ The proofs of these lemmas typically require counting arguments such as the pigeonhole principle.
→ Hence, the logic of pumping lemma is a good example of the pigeonhole principle.
Question 55 
50, 50, 14, 5  
51, 51, 15, 7  
52, 52, 14, 5  
51, 51, 14, 5 
Question 56 
64  
128  
265  
None of the above 
 Total number of bits=8
 Beginning with either 111 or 101
 Total number of strings=?
Step1: First consider 111 as beginning numbers. It look like
Possibility to get combinations are 2^{5} =32 Step2: Second consider 101 as beginning numbers. It look like
Possibility to get combinations are 2^{5} =32 Step3: Total number of strings are 32+32
=64
Question 57 
55,440  
1,66,320  
4.790E+08  
39,91,680 
 Total number of offices=12
 Colours are Green=3, Pink=2, Yellow=2 and White=5
white= 127
= 5
 Total number of ways to paint 12 offices=?
Step1: Total number of offices are 12 then we get maximum 12!
12!=479001600
Step2: Green=3, Pink=2, Yellow=2 and White=5
maximum possibilities of individual colours are
= 3! * 2! * 2! * 5!
= 2880
Step3: Total number of ways to paint 12 offices= (12! / (3! * 2! * 2! * 5!))
= 479001600 / 2880
= 166320
Question 58 
32  
64  
128  
160 
→ Number of bit strings of length 8 that end with 00: 26 = 64.
→ Number of bit strings of length 8 that start with 1 and end with 00: 25 = 32.
→ Applying the subtraction rule, the number is 128+64−32 = 160
Question 59 
122 & 22  
111 & 11  
133 & 33  
144 & 44 
→ The root represents the person who first sends out the letter, and the children of any vertex represent the 4 people that the related person sent letters.
→ From the question, total people are 100, The total number of people who received the letter can be found by computing the number total number of vertices in the rooted tree.
3n+1=100
n=100⅓
=33
The number of people who read it but did not send it out is 100+33=133
The number of people sent out the letter is 33
Question 60 
(p(n, r)(n + 1)) / (n + 1 – r)  
(p(n, r) (n + 1)) / (n – 1 + r)  
(p(n, r) (n – 1)) / (n + 1 – r)  
(p(n, r) (n + 1)) / (n + 1 + r) 
Question 61 
2^{n}  
3^{n}  
5^{n}  
7^{n} 
Any integer composed of 3^{n} identical digits.
For example n=1, 3^{n}= 3^{1}=3 which means three identical digits (111,222,333,444 and so on)
n=2, 3^{2} =9 which means nine identical digits (111111111, 222222222 and so on)
The above numbers are is divisible by 3
111 is divisible by 3.
222, 333 and 444 are multiple of 3
Question 62 
1 890 x ^{5} y^{ 5}  
6 1236 x ^{5} y^{ 5}  
3 77810 x^{ 5} y^{ 5}  
6 2136 x ^{5} y^{ 5} 
Question 63 
x = 3 , a = 3 , n = 5  
x = 2 , a = 3 , n = 4  
x = 2 , a = 3 , n = 5  
x = 3 , a = 2 , n = 5 
Question 64 
^{100}P_{2}  
^{100}C_{2}  
2^{100}  
3^{100} 
 Total number of questions=100
 Total possibilities for each question=3 (Note: BLANK or TRUE or FALSE)
Step1: 1 question= 3 possibilities.
Question 65 
405/16  
405/16  
405/128  
None of the above 
Question 66 
2  
3  
5  
8 
Solving this problem by 2 methods:
1. Venn diagram
2. Mathematical substitution.
In this problem, we are using Mathematical substitution method.
Step1: According to condition, we can perform least common multiple(LCM) of 2,5 and 7=70
Step2: Total number of integers= ⌊250/70⌋
= 3
Note: Divisible numbers are 70,140 and 210.
Question 67 
5.75  
2.95  
1.4875  
5 
Step1: (13 / 4 * 3) % 5 + 1
Step2: (3.25*3)%5+1
Step3: 9.75%5+1
Step4: 4.75+1
Step5: 5.75
Note: ( ) having highest precedence then *,/ and % have same precedence order.
Question 68 
Between 12,000 and 25,000  
Between 30,000 and 60,000  
Between 75,000 and 99,999  
More than 100,000 
Question 69 
Descriptive Explanation 
To solve the above question, consider an illustrative scenario where k is 2. Given that the graph has two connected components, what is the maximum number of edges possible. Let the first connected component be G_{ 1} with n_{ 1} vertices and the other be G _{2} with n_{ 2} vertices. Further assume that n _{1} ≥ n_{ 2} . Note that there are no edges between a vertex from G _{1} and a vertex from G _{2} . Therefore, each vertex in G _{2} can be connected by an edge to at most n _{2} − 1 vertices. If a vertex from G_{ 2} is moved to G _{1} , then this vertex can potentially be part of n 1 edges. Since n_{ 1} ≥ n_{ 2} , moving vertices from G_{ 2} to G_{ 1} would increase the number of edges. The maximum number of edges would be obtained when n 2 is 1 and n _{1} = n − 1.
Coming back to our original question: suppose the graph is made of k connected components, then the maximum number of edges is obtained when one of the components has n − (k − 1) vertices and the other components have 1 vertex each.
Hence the maximum number of edges possible is ^{n−k+1} C _{2} .
Question 70 
Descriptive Explanation 
(b) Minimum 0 rupees, by preparing 1 roti and doing nothing else. Maximum 2 _{P +1} rupees: she can first make one roti and sell it to get 2 rupees. She can then make P trips to the kitchen, doubling her money with every trip.
Question 71 
Descriptive Explanation 
We can create a twodimensional with nk entries, and fill them in according to the above recurrence. The desired answer is given by N (t, 0) + N (t, 1) + · · · + N (t, k).
We need to fill in nk entries, and we add at most n numbers to compute each entry. Since adding two numbers is assumed to take unit time, we can add n numbers in O(n) time. Thus the overall time taken by the algorithm is O(n ^{2} k).
Question 72 
7  
11  
13  
15 
 Set of positive integers=8
 A pair of numbers having the same remainder when divided by=?
Step1: This problem, we can use pigeonhole principle.
Pigeonhole Principle: If there are ‘X’ positive integers to be placed in ‘Y’ possible remainder where Y < X, then there is at least one possible remainder which receives more than one positive integer.
OptionA: Total number of possible remainders, divided by 7 is 0,1,2,3,4,5,6.
These numbers are less than 8 only.
OptionB,C and D: Total number of possible remainders,
divided by 11, 13, 15 is greater than 8
Question 73 
Descriptive Explanation 
The proof by induction on n.
The base cases n = 1, 2 are easy to see by inspection.
For the inductive step, let n ≥ 3. If the graph G has no edges then there is nothing to prove. Otherwise, take an edge {x, y}, and consider the graph G' on 2(n − 1) vertices obtained by deleting both the vertices {x, y} from G.
By the inductive hypothesis, G' has at most (n − 1) ^{2} edges. Since graph G is triangle free and {x, y} is an edge in G, there is no vertex v in G' such that both {v, x} and {v, y} are edges in G. So the number of edges with one endpoint in the set {x, y} and the other in the set of vertices of G 0 is at most the number of vertices in G' , namely 2(n − 1).
Now the set of edges of G consists of (i) all the edges in G' , plus (ii) the one edge {x, y}, plus (iii) the at most 2(n − 1) edges with exactly one endpoint in {x, y}. So the number of edges of G is at most (n − 1) ^{2} + 1 + 2(n − 1) ≤ n^{ 2} .
Question 74 
260  
340  
720  
1440 
Question 75 
M < 25  
25 ≤ M < 40  
40 ≤ M < 55  
M ≥ 55 
Question 76 
Vinay is taller than Avinash and Abhay is taller than Bharat.  
Avinash is taller than Vinay  
Abhay is shorter than Vinay.  
None of the above. 
The minimal extra information we need to decide the tallest is a comparison between Avinash and Vinay.
(a) decides the tallest but is not minimal since it gives an extra condition.
(b) decides that Avinash is tallest, so (b) is the correct answer.
(c) does not decide the tallest.
(d) (none of the above) is wrong since (b) is a valid answer.
Question 77 
Explanation 
Question 78 
iteration  
recursion  
the divide and conquer principle  
the pigeonhole principle 
→ The proofs of these lemmas typically require counting arguments such as the pigeonhole principle.
→ Hence, the logic of pumping lemma is a good example of the pigeonhole principle.
Question 79 
70  
165  
^{8} C _{4}  
^{8} P _{4}T 
= C(8+41,8)
= ^{11} C _{8}
= 11! / (8!(118)!)
= 165
Question 80 
Max Z=2x_{1}  x_{2} + 2x_{3}
Subject to the constraints
2x_{1} + x_{2} ≤ 10
x_{1} + 2x_{2}  2x_{3} ≤ 20
x_{1} + 2x_{3} ≤ 5
x_{1}, x_{2}, x_{3} ≥ 0
What shall be the solution of the LPP after applying first iteration of the Simplex Method?
x_{1}=5/2, x_{2}=0, x_{3}=0, Z=5  
x_{1}=0, x_{2}=0, x_{3}=5/2, Z=5  
x_{1}=0, x_{2}=5/2, x_{3}=0, Z= 5/2
 
x_{1}=0, x_{2}=0, x_{3}=10, Z=20 
Question 81 
9  
13  
17  
42 
Question 82 
1  
2  
5  
7  
8 
Question 83 
Maximize z = x_{1} + x_{2}
Subject to the constraints:
The solution of the above LPP is:
x_{1}=750, x_{2}=750, z=1500  
x_{1}=500, x_{2}=100, z=1500  
x_{1}=1000, x_{2}=500, z=1500  
x_{1}=900, x_{2}=600, z=1500 
Question 84 
160  
166  
157  
67 
Question 85 
((2y/5) + (x/3)) + ((x/5) + (2y/3))
Will be equal to
8  
16  
18  
20 
Question 86 
120  
80  
420  
6045 
Committee members=6,
Mens=6
Women=4
Equal numbers of men and women are= ?
3 men out of 6, 3 women out of 4
⇒ ^{6}C_{3} * ^{4}C_{3} ways
⇒ 20 * 4
⇒ 80
Note: There are 3 possibilities to consider an equal number of men and women.
Choose 4 men and 4 women then we get ^{6}C^{4} * ^{4}C_{4} ways = 15
Choose 2 men and 2 women then we get ^{6}C_{2} * ^{4}C^{2 ways = 90 Choose 3 men and 3 women then we get 6C3 * 4C3 ways = 80}
Question 87 
2416  
6720  
1680  
4096 
Question 88 
Pigeonhole principle states that if A→B and A>B then _______
f is not onto
 
f is not oneone  
f is neither oneone nor onto
 
f may be oneone 
Question 89 
Two girls have picked 10 roses, 15 sunflowers and 14 daffodils. What is the number of ways they can divide the flowers amongst themselves?
1,638  
2,640  
2,100  
None of the given options 
So for roses = C(10+21,21) = 11
For sunflowers = C(15+21,21) = 16
For daffodils = C(14+21,21) = 15
So final answer is = 11*16*15 = 2640
Question 90 
10 C_{1} + 9 C_{2}  
2^{10}  
10 C_{2}  
10 1 
2*2*2*2*2*2*2*2*2*2 = 2^{10}
Question 91 
2240  
2296  
2620  
4536 
Case3: Last digit contains ‘0’,
= 9 × 8 × 7
= 504
Case2: Last digit does not contains ‘0’,
= 8 × 8 × 7 × ^{4}C_{1}
= 1792
∴ Answer is = 1792 + 504 = 2296
Question 92 
1958  
1956  
16  
64 
where,
1 ≤ n ≤ 6
when n=1,
^{6}C_{1} × ∠1 = 6
when n=2,
^{6}C_{6} × ∠2 = 30
when n=3,
^{6}C_{3} × ∠3 = 120
when n=4,
^{6}C_{4} × ∠4 = 360
when n=5,
^{6}C_{5} × ∠5 = 720
when n=6,
^{6}C_{6} × ∠6 = 720
Total no. of ways
= 6 + 30 + 120 + 360 + 720 + 720
= 1956
Question 93 
18  
20  
52  
54  
60 
Question 94 
10  
32  
100  
999  
None of the above 
Question 95 
00  
13  
30  
33  
73 
Question 96 
199  
683  
1365  
3^{10} − 2^{10}  
3^{10} 
Question 97 
3^{35}  
3^{50} − 2^{50}  
(35 2)  
(50 15)*3^{35}  
(37 2) 
Question 98 
11! / (5! 2! 2!)  
11! / (5! 4!)  
11! 5! 2! 2!  
11!  
11! 5! 4! 
Question 99 
2Z+6  
3Z+6  
2Z+8  
3Z+8  
3Z+4 
Question 100 
s_{4k} is even, for any k ≥ 0  
s_{4k+1} is odd, for any k ≥ 0  
s_{4k+2} is odd, for any k ≥ 0  
s_{n} is a multiple of 3, for only finitely many values of n  
s_{4k+3} is even, for any k ≥ 0 
Question 101 
a  
b  
c  
d  
e 
Question 102 
2^{n}  
n^{2}  
none of the above 
Question 103 
F_{n} = F_{n1} + F_{n2}. Then which of the following statements is FALSE?
a  
b  
c  
d  
e 
Question 104 
(a) they have no repeated prime factors;
(b) for all primes p ≥ 2, p divides the number if and only if p − 1 divides the number.
The number of such numbers is
0  
5  
100  
Infinite  
None of the above 
Question 105 
23  
91  
60  
49  
None of the above 
Question 106 
a  
b  
c  
d  
e 
Question 107 
6  
4  
3  
8 
For minimum number of multiplications, lets modify above equation,
p(x)= c0 + x(c1 + c2x + c3 x^2)
=c0+x(c1+x(c2+c3x)
=c0+x*(c1+x*(c2+c3*x)
Hence minimum number of multiplications required is 3
Question 108 
a  
b  
c  
d  
e 
Question 109 
(i) Repetition is not allowed and the order of picking matters?
(ii) Repetition is allowed and the order of picking does not matter?
a  
b  
c  
d  
e 
Question 110 
14  
27  
30  
39  
None of the above 
Now to guarantee that three cards are from same suit,
⇒ Let's first draw 4 cards of different sizes.
⇒ Now again draw 4 cards of different suits. Now we have 8 cards of 2 cards from each suit.
⇒ Now take 1 card from any suit, which will guarantee that 3 cards are from the same suit.
So, in total 9 cards are required.
Question 111 
2450  
2500  
1225  
1250 
answer is P(50,2) = 2450
Question 112 
14600  
12600  
12800  
None of the above

Hence the no. of ways they can be arranged in a row,
=12600
Question 113 
24  
12  
6  
120 
Question 114 
4  
5  
6  
7 
Question 115 
12500  
6400  
11341  
None of these 
Question 116 
18,800  
13,800  
12,800  
14,800 
Question 117 
9!  
630  
315  
None of the above 
C(9,4)*C(5,3)*C(2,2) = 1260
Question 118 
Question 119 
Let n denote a positive integer. suppose a function L is defined recursively as follows (here ⌊k⌋ denotes the “floor” of k).
What does L find?
L= ⌊log _{2} n⌋  
L=(n^{2}/4)+1  
L=2^{n}  
None of the above 
Question 120 
4  
6  
7  
9 
Question 121 
Which statement about the difference is TRUE?
It is positive for infinitely many m ≥ 5 and negative for infinitely many m ≥ 5  
It is positive for all m ≥ 5, and is increasing as m increases  
It is negative for finitely many m ≥ 5 and is positive for infinitely many m  
It is positive for all m ≥ 5, and is decreasing as m increases  
It is negative for all m ≥ 5 