Combinatorics
Question 1 
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 2 
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 3 
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 4 
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 5 
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 6 
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 7 
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 8 
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 9 
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 10 
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 11 
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 12 
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 13 
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 14 
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 15 
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 16 
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 17 
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 18 
(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 19 
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 20 
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 21 
“ 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 22 
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 23 
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 24 
50, 50, 14, 5  
51, 51, 15, 7  
52, 52, 14, 5  
51, 51, 14, 5 
Question 25 
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 26 
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 27 
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 28 
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 29 
(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 30 
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 31 
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 32 
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 33 
^{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 34 
405/16  
405/16  
405/128  
None of the above 
Question 35 
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 36 
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 37 
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 38 
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.