Combinatorics

Question 1
The number of bit strings of length 8 that will either start with 1 or end with 00 is?
A
32
B
128
C
160
D
192
       Engineering-Mathematics       Combinatorics       ISRO CS 2014
Question 1 Explanation: 
→ Number of bit strings of length 8 that start with 1: 27 = 128.
→ 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
Mala has a colouring book in which each english letter is drawn two times. She wants to point each of these 52 prints with one of k colours, such that the colour-pairs used to colour ay 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?
A
9
B
8
C
7
D
6
       Engineering-Mathematics       Combinatorics       Nielit Scientist-B IT 4-12-2016
Question 2 Explanation: 
No. of letters from A-Z is = 26
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(k-1)/2 ≥ 26
k(k+1)/2 ≥ 26
k(k+1) ≥ 52
k(k+1) ≥ 7*8
k≥7
Question 3
There are four bus lines between A and B; And three bus lines between B and C The number of way a person roundtrip by bus from A to C by way of B will be
A
12
B
7
C
144
D
264
       Engineering-Mathematics       Combinatorics       Nielit Scientist-B IT 22-07-2017
Question 3 Explanation: 
The number of bus lines between a and b =4
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
The solution of the recurrence relation a​ r​ =a​ r-1​ +2a​ r-2​ with a​ 0​ =2,a​ 1​ =7
A
a​ r​ =(3)​ r​ +(1)​ r
B
2a​ r​ =(2)​ r​ /3 -(1)​ r
C
a​ r​ =3​ r+1​ -(-1)​ r
D
a​ r​ =3(2)​ r​ -(-1)​ r
       Engineering-Mathematics       Combinatorics       Nielit Scientific Assistance IT 15-10-2017
Question 4 Explanation: 
Given the recurrence relation a​ r​ =a​ r-1​ +2a​ r-2 and a​ 0​ =2,a​ 1​ =7.
For r =2, a​ 2=​ a​ 2-1​ +2a​ 2-2​ =a​ 1​ +2a​ 0​ =7+2*2=7+4=11
For r=3,a​ 3=​ a​ 3-1​ +2a​ 3-2​ =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?

A
4560
B
4000
C
7560
D
7500
       Engineering-Mathematics       Combinatorics       JT(IT) 2018 PART-B Computer Science
Question 5 Explanation: 
Step-1: There are 4A, 2L, 1H, 1B and 1D.
Step-2: Total number of alphabets! / alphabets are repeating using formula (n!) / (r1! r2!..).
Step-3: 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?

A
64
B
255
C
160
D
128
       Engineering-Mathematics       Combinatorics       JT(IT) 2018 PART-B Computer Science
Question 6 Explanation: 
Use the subtraction rule.
1. Number of bit strings of length eight that start with a 1 bit: 27 = 128
2. Number of bit strings of length eight that end with bits 00: 26 = 64
3. Number of bit strings of length eight that start with a 1 bit and end with bits 00: 25 = 32
The number is 128+64+32 = 160
Question 7

What is the solution of the recurrence relation an = 6an-1 - 9an-2 with initial conditions a0=1 and a1=6?

A
an = 3n + 3n2
B
an = 3n + n3n
C
an = 3n + 3nn
D
an = n3 + n3n
       Engineering-Mathematics       Combinatorics       JT(IT) 2018 PART-B Computer Science
Question 7 Explanation: 
→ Let c1, c2, ..., ck be real numbers.
→ Suppose that the characteristic equation rk −c1rk−1 −···−ck = 0 has k distinct roots r1, r2, ..., rk.
→ Then, a sequence {an} is a solution of the recurrence relation: an = c1an−1 + c2an−2 + ··· + ckan−k
→ if and only if an = α1rn1 + α2rn2 + ··· + αk rnk for n = 0,1,2,..., where α1, α2, ..., αk are constants.
→ r2 − 6r + 9 = 0 has only 3 as a root.
→ So the format of the solution is an = α13n + α2n3n.
→ Need to determine α1 and α2 from initial conditions:
a0 = 1 = α1
a1 = 6 = α13 + α23
Solving these equations we get α1=1 and α2=1
Therefore, an = 3n + n3n.
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?

A
24
B
12
C
25
D
13
       Engineering-Mathematics       Combinatorics       JT(IT) 2018 PART-B Computer Science
Question 8 Explanation: 
With the help of Pigeonhole principle we can get the solution. The idea is that if you n items and m possible containers. If n > m, then at least one container must have two items in it. So, total 13 minimum number of students.
Question 9
The solution of the recurrence relation a​ r​ =a​ r-1​ +2a​ r-2​ with a​ 0​ =2,a​ 1​ =7
A
a​ r​ =(3)​ r​ +(1)​ r
B
2a​ r​ =(2)​ r​ /3 -(1)​ r
C
a​ r​ =3​ r+1​ -(-1)​ r
D
a​ r​ =3(2)​ r​ -(-1)​ r
       Engineering-Mathematics       Combinatorics       Nielit Scientific Assistance CS 15-10-2017
Question 9 Explanation: 
● Given the recurrence relation a​ r​ =a​ r-1​ +2a​ r-2 and a​ 0​ =2,a​ 1​ =7.
● For r =2, a​ 2=​ a​ 2-1​ +2a​ 2-2​ =a​ 1​ +2a​ 0​ =7+2*2=7+4=11 ● For r=3,a​ 3=​ a​ 3-1​ +2a​ 3-2​ =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?

A
16
B
48
C
54
D
60
       Engineering-Mathematics       Combinatorics       JT(IT) 2016 PART-B Computer Science
Question 10 Explanation: 
• Three digit odd numbers implies the numbers would only be made of digits 1 , 3 , 5 , 7 , 9 With repetition of digits we would have had 5 * 5 * 5 = 125
• 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?

A
495
B
595
C
395
D
295
       Engineering-Mathematics       Combinatorics       JT(IT) 2016 PART-B Computer Science
Question 11 Explanation: 
As the order of people does not matter, it is C4 12
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

A
(n+1)/n
B
n/(n+1)
C
n/(2n+1)
D
(2n+1)/n
       Engineering-Mathematics       Combinatorics       JT(IT) 2016 PART-B Computer Science
Question 12 Explanation: 
Sum upto n terms = 1/(1*2) + 1/(2*3) + 1/(3*4) + ........ + 1/(n*(n+1))
where
1st term = 1/(1*2)
2nd term = 1/(2*3)
3rd term = 1/(3*4)
.
.
.
.
n-th term = 1/(n*(n+1))
n-th term = 1/(n*(n+1))
i.e. the k-th term is of the form 1/(k*(k+1))
which can further be written as k-th 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/n-1 - /1n) + (1/n - 1/n+1)
= (1 - 1/2) + (1/2 - 1/3) + (1/3 - 1/4) + ......... + (1/n-1 - 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)?

A
125
B
145
C
146
D
136
       Engineering-Mathematics       Combinatorics       JT(IT) 2016 PART-B Computer Science
Question 13 Explanation: 
A) numbers divisible by 2: 200/2 = 100
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:

A
8
B
14
C
13
D
5
       Engineering-Mathematics       Combinatorics       JT(IT) 2016 PART-B Computer Science
Question 14 Explanation: 
11=1*1=1 which is a factor of 11
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:

A
(1/2) - log(√2)3
B
1 + log(√2)3
C
3/2
D
1/2 + log(√2)3
       Engineering-Mathematics       Combinatorics       JT(IT) 2016 PART-B Computer Science
Question 15 Explanation: 
The sum of the series: (1/2) + (1/3) + (1/4) - (1/6) + (1/8) + (1/9) + (1/16) - (1/12) + ... + α is 1 + log(√2)3.
Question 16
Consider a 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 Then what shall be the set of values of the sequence F​ 00​ ?
A
(1, 110, 1200)
B
(1, 110, 600, 1200)
C
(1, 2, 55, 110, 600, 1200)
D
(1, 55, 110, 600, 1200)
       Engineering-Mathematics       Combinatorics       UGC NET CS 2017 Jan -paper-2
Question 16 Explanation: 
Given data,
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) + 100) / 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
How many multiples of 6 are there between the following pairs of numbers ?
0 and 100 and –6 and 34
A
16 and 6
B
17 and 6
C
17 and 7
D
16 and 7
       Engineering-Mathematics       Combinatorics       UGC NET CS 2017 Jan -paper-2
Question 17 Explanation: 
Method-1:
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
Method-2: 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
Which of the following arguments are not valid ?
(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
(a) and (c)
B
(b) and (c)
C
(a), (b) and (c)
D
(a) and (b)
       Engineering-Mathematics       Combinatorics       UGC NET CS 2015 Dec- paper-2
Question 19
How many strings of 5 digits have the property that the sum of their digits is 7?
A
66
B
330
C
495
D
99
       Engineering-Mathematics       Combinatorics       UGC NET CS 2015 Jun- paper-2
Question 19 Explanation: 
→ From the given question, there should be string with 5 digits and sum of that digits should be 7
→ 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+r-1),(r-1))
→ From the given data n=7,r=5 then We have to fine C(11,4) which is equal to 330
Question 20
In how many ways can 15 indistinguishable fish be placed into 5 different ponds, so that each pond contains at least one fish ?
A
1001
B
3876
C
775
D
200
       Engineering-Mathematics       Combinatorics       UGC NET CS 2015 Jun- paper-2
Question 20 Explanation: 
→ We know that if we have “n” identical items which will be distributed in “r” distinct groups where each must get at least one then the number of way is C(n−1,r−1)
→ From the given question, n=15, r=5 We need to calculate C(14,4) and it’s value is 1001.
Question 21
Consider a proposition given as :
“ 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
(a) only
B
(c) only
C
(a) and (b)
D
(b) only
       Engineering-Mathematics       Combinatorics       UGC NET CS 2015 Jun- paper-2
Question 21 Explanation: 
The proof which is described in the question is wrong because for a given “x” value , x​ 2​ >=5 but in the proof they mentioned 36>=25 which is wrong.
Question 22
Minimum number of individual shoes to be picked up from a dark room ( containing 10 pair of shoes) if we have to get at least one proper pair :
A
2
B
20
C
11
D
None of these
       Engineering-Mathematics       Combinatorics       UGC NET CS 2005 june-paper-2
Question 22 Explanation: 
→ There are 10 pair of shoes available in the dark room which means 20 individual shoes are available in the room.
→ 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
The logic of pumping lemma is a good example of :
A
pigeon hole principle
B
recursion
C
divide and conquer technique
D
iteration
       Engineering-Mathematics       Combinatorics       UGC NET CS 2006 June-Paper-2
Question 23 Explanation: 
→ A pumping lemma (or) pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of times, with the resulting string remaining in that language.
→ 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
How many cards must be chosen from a deck to guarantee that at least I. two aces of two kinds are chosen. II. two aces are chosen. III. two cards of the same kind are chosen. IV. two cards of two different kinds are chosen.
A
50, 50, 14, 5
B
51, 51, 15, 7
C
52, 52, 14, 5
D
51, 51, 14, 5
       Engineering-Mathematics       Combinatorics       UGC NET CS 2014 June-paper-2
Question 25
The number of eight-bit strings beginning with either 111 or 101 is______.
A
64
B
128
C
265
D
None of the above
       Engineering-Mathematics       Combinatorics       UGC NET CS 2013 Sep-paper-2
Question 25 Explanation: 
Given data,
-- Total number of bits=8
-- Beginning with either 111 or 101
-- Total number of strings=?
Step-1: First consider 111 as beginning numbers. It look like

Possibility to get combinations are 25 =32 Step-2: Second consider 101 as beginning numbers. It look like

Possibility to get combinations are 25 =32 Step-3: Total number of strings are 32+32
=64
Question 26
Find the number of ways to paint 12 offices so that 3 of them will be green, 2 of them pink, 2 of them yellow and the rest ones white.
A
55,440
B
1,66,320
C
4.790E+08
D
39,91,680
       Engineering-Mathematics       Combinatorics       UGC NET CS 2013 Sep-paper-2
Question 26 Explanation: 
Given data,
-- Total number of offices=12
-- Colours are Green=3, Pink=2, Yellow=2 and White=5
white= 12-7
= 5
-- Total number of ways to paint 12 offices=?
Step-1: Total number of offices are 12 then we get maximum 12!
12!=479001600
Step-2: Green=3, Pink=2, Yellow=2 and White=5
maximum possibilities of individual colours are
= 3! * 2! * 2! * 5!
= 2880
Step-3: Total number of ways to paint 12 offices= (12! / (3! * 2! * 2! * 5!))
= 479001600 / 2880
= 166320
Question 27
The number of bit strings of length eight that will either start with a 1 bit or end with two bits 00 shall be
A
32
B
64
C
128
D
160
       Engineering-Mathematics       Combinatorics       UGC NET CS 2012 Dec-Paper-2
Question 27 Explanation: 
→ Number of bit strings of length 8 that start with 1: 27 = 128.
→ 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
Suppose that someone starts with a chain letter. Each person who receives the letter is asked to send it on to 4 other people. Some people do this, while some do not send any letter. How many people have seen the letter, including the first person, if no one receives more than one letter and if the chain letter ends after there have been 100 people who read it but did not send it out ? Also find how many people sent out the letter ?
A
122 & 22
B
111 & 11
C
133 & 33
D
144 & 44
       Engineering-Mathematics       Combinatorics       UGC NET CS 2012 Dec-Paper-2
Question 28 Explanation: 
→ Notice that since every person who sends out the letter sends it to exactly 4 other people, and no two people receive the letter twice, this situation can be modeled using a full rooted 4-ary tree.
→ 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
If n and r are non-negative integers and n ≥ r, then p(n + 1, r) equals to
A
(p(n, r)(n + 1)) / (n + 1 – r)
B
(p(n, r) (n + 1)) / (n – 1 + r)
C
(p(n, r) (n – 1)) / (n + 1 – r)
D
(p(n, r) (n + 1)) / (n + 1 + r)
       Engineering-Mathematics       Combinatorics       UGC NET CS 2013 Dec-paper-2
Question 30
Any integer composed of 3n identical digits divisible by
A
2n
B
3n
C
5n
D
7n
       Engineering-Mathematics       Combinatorics       UGC NET CS 2011 June-Paper-2
Question 30 Explanation: 
Identical digits means similar(same) digits.
Any integer composed of 3n identical digits.
For example n=1, 3n= 31=3 which means three identical digits (111,222,333,444 and so on)
n=2, 32 =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
The middle term in the expansion of ( x/3 + 9 y )10
A
1 890 x 5 y 5
B
6 1236 x 5 y 5
C
3 77810 x 5 y 5
D
6 2136 x 5 y 5
       Engineering-Mathematics       Combinatorics       NIELIT Junior Teachnical Assistant_2016_march
Question 32
The second, third and fourth terms in the binomial expansion (x + a ) and 240, 720 and 1080 respectively. Then, x , a and n are :
A
x = 3 , a = 3 , n = 5
B
x = 2 , a = 3 , n = 4
C
x = 2 , a = 3 , n = 5
D
x = 3 , a = 2 , n = 5
       Engineering-Mathematics       Combinatorics       NIELIT Junior Teachnical Assistant_2016_march
Question 33
A test contains 100 true/false questions. How many different ways can a student answer the questions on the test, if the answer may be left blank also.
A
100P2
B
100C2
C
2100
D
3100
       Engineering-Mathematics       Combinatorics       UGC NET CS 2013 June-paper-2
Question 33 Explanation: 
Given data,
-- Total number of questions=100
-- Total possibilities for each question=3 (Note: BLANK or TRUE or FALSE)
Step-1: 1 question= 3 possibilities.

Question 34
The coefficient of x 2 in the expansion of is
A
-405/16
B
405/16
C
405/128
D
None of the above
       Engineering-Mathematics       Combinatorics       NIELIT Technical Assistant_2016_march
Question 35
The number of integers between 1 and 250 that are divisible by 2, 5 and 7 is
A
2
B
3
C
5
D
8
       Engineering-Mathematics       Combinatorics       UGC NET CS 2010 Dec-Paper-2
Question 35 Explanation: 
Here, we have to find all possible integers between 250 which was divisible by 2,5 and 7.
Solving this problem by 2 methods:
1. Venn diagram
2. Mathematical substitution.
In this problem, we are using Mathematical substitution method.
Step-1: According to condition, we can perform least common multiple(LCM) of 2,5 and 7=70
Step-2: Total number of integers= ⌊250/70⌋
= 3
Note: Divisible numbers are 70,140 and 210.
Question 36
The value of the following expression (13 / 4 * 3) % 5 + 1 is
A
5.75
B
2.95
C
1.4875
D
5
       Engineering-Mathematics       Combinatorics       UGC NET CS 2010 Dec-Paper-2
Question 36 Explanation: 
(13 / 4 * 3) % 5 + 1
Step-1: (13 / 4 * 3) % 5 + 1
Step-2: (3.25*3)%5+1
Step-3: 9.75%5+1
Step-4: 4.75+1
Step-5: 5.75
Note: ( ) having highest precedence then *,/ and % have same precedence order.
Question 37
In a set of 8 positive integers, there always exists a pair of numbers having the same remainder when divided by :
A
7
B
11
C
13
D
15
       Engineering-Mathematics       Combinatorics       UGC NET CS 2008-june-Paper-2
Question 37 Explanation: 
Given data,
-- Set of positive integers=8
-- A pair of numbers having the same remainder when divided by=?
Step-1: 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.
Option-A: Total number of possible remainders, divided by 7 is 0,1,2,3,4,5,6.
These numbers are less than 8 only.
Option-B,C and D: Total number of possible remainders,
divided by 11, 13, 15 is greater than 8
Question 38
The logic of pumping lemma is an example of __________.
A
iteration
B
recursion
C
the divide and conquer principle
D
the pigeonhole principle
       Engineering-Mathematics       Combinatorics       UGC NET CS 2017 Nov- paper-3
Question 38 Explanation: 
→ A pumping lemma (or) pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of times, with the resulting string remaining in that language.
→ 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.
There are 38 questions to complete.
PHP Code Snippets Powered By : XYZScripts.com