## Engineering-Mathematics

 Question 1
 A 1 B Limit does not exist C 53/12 D 108/7
Engineering-Mathematics       GATE 2019
Question 1 Explanation:
 Question 2

Let G be an arbitrary group. Consider the following relations on G:

      R1: ∀a,b ∈ G, aR1b if and only if ∃g ∈ G such that a = g-1bg
R2: ∀a,b ∈ G, aR2b if and only if a = b-1

Which of the above is/are equivalence relation/relations?
 A R2 only B R1 and R2 C Neither R1 and R2 D R1 only
Engineering-Mathematics       GATE 2019
Question 2 Explanation:
A relation between the elements of a set is symmetric, reflexive and transitive then such relation is called as equivalence relation.
Consider Statement R1:
Reflexive:
aR1a
⇒ a = g-1ag
Left multiply both sides by g
⇒ ga = gg-1ag
Right multiply both sides by g-1
⇒ gag-1 = gg-1agg-1
⇒ gag-1 = a [∴ The relation is reflexive]
Symmetric:
If aR1b, then ∃g ∈ G such that gag-1 = b then a = g-1bg, which is Correct.
⇒ So, given relation is symmetric.
Transitive:
The given relation is Transitive.
So, the given relation R1 is equivalence.
R2:
The given relation is not reflexive. So, which is not equivalence relation. Such that a ≠ a-1. So, only R1 is true.
 Question 3

Let X be a square matrix. Consider the following two statements on X.

I. X is invertible.
II. Determinant of X is non-zero.

Which one of the following is TRUE?
 A I implies II; II does not imply I. B II implies I; I does not imply II. C I and II are equivalent statements. D I does not imply II; II does not imply I.
Engineering-Mathematics       GATE 2019
Question 3 Explanation:
X is invertible means, that X is non-singular matrix.
That means we can also say that determinant of X is non-zero.
 Question 4

Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to

 A n! B 1 C (n-1)! D
Engineering-Mathematics       GATE 2019
Question 4 Explanation:
A Hamiltonian cycle is a closed loop on a graph where every node (vertex) is visited exactly once.
The total number of hamiltonian cycles in a complete graph are
(n-1)!/2, where n is number of vertices.
 Question 5

Let U = {1,2,...,n}. Let A = {(x,X)|x ∈ X, X ⊆ U}. Consider the following two statements on |A|.



Which of the above statements is/are TRUE?
 A Only II B Only I C Neither I nor II D Both I and II
Engineering-Mathematics       GATE 2019
Question 5 Explanation:
Let us consider U = {1, 2}
and given A = {(x, X), x∈X and X⊆U}
Possible sets for U = {Φ, {1}, {2}, {1, 2}}
if x=1 then no. of possible sets = 2
x=2 then no. of possible sets = 2
⇒ No. of possible sets for A = (no. of sets at x=1) + (no. of sets at x=2) = 2 + 2 = 4
Consider statement (i) & (ii) and put n=2

Statement (i) is true

Statement (i) and (ii) both are true. Answer: (C)
 Question 6

Suppose Y is distributed uniformly in the open interval (1,6). The probability that the polynomial 3x2 + 6xY + 3Y + 6 has only real roots is (rounded off to 1 decimal place) _____.

 A 0.3 B 0.9 C 0.1 D 0.8
Engineering-Mathematics       GATE 2019
Question 6 Explanation:
Given polynomial equation is
3x2 + 6xY + 3Y + 6
= 3x2 + (6Y)x + (3Y + 6)
whch is in the form: ax2 + bx + c
For real roots: b2 - 4ac ≥ 0
⇒ (6Y)2 - 4(3)(3Y + 6) ≥ 0
⇒ 36Y2 - 36Y - 72 ≥ 0
⇒ Y2 - Y - 2 ≥ 0
⇒ (Y+1)(Y-2) ≥ 0
Y = -1 (or) 2
The given interval is (1,6).
So, we need to consider the range (2,6).
The probability = (1/(6-1)) * (6-2) = 1/5 * 4 = 0.8
 Question 7
Consider the first order predicate formula φ:
∀x[(∀z z|x ⇒ ((z = x) ∨ (z = 1))) ⇒ ∃w (w > x) ∧ (∀z z|w ⇒ ((w = z) ∨ (z = 1)))]

Here 'a|b' denotes that 'a divides b', where a and b are integers. Consider the following sets:

     S1.  {1, 2, 3, ..., 100}
S2.  Set of all positive integers
S3.  Set of all integers

Which of the above sets satisfy φ?
 A S1 and S3 B S1, S2 and S3 C S2 and S3 D S1 and S2
Engineering-Mathematics       GATE 2019
Question 7 Explanation:
The first order logic gives the meaning that if z is a prime number then there exists another prime number in the set which is larger than it.
One of the case: If -7 is a number which is prime (either divided by -7 or 1 only). then there exists some number like -3 which is larger than -7 also satisfy the property ( either divided by -3 or 1 only).
So, S3 is correct
It's true for all integers too
 Question 8
Consider the following matrix:
The absolute value of the product of Eigen values of R is ______.
 A 12 B 17 C 10 D 8
Engineering-Mathematics       GATE 2019
Question 8 Explanation:
 Question 9
Let G be a group of 35 elements. Then the largest possible size of a subgroup of G other than G itself is ______.
 A 7
Engineering-Mathematics       Set-Theory       GATE 2020
Question 9 Explanation:
Lagrange’s Theorem:
If ‘H” is a subgroup of finite group (G,*) then O(H) is the divisor of O(G).
Given that the order of group is 35. Its divisors are 1,5,7,35.
It is asked that the size of largest possible subgroup other than G itself will be 7.
 Question 10
Let R be the set of all binary relations on the set {1,2,3}. Suppose a relation is chosen from R at random. The probability that the chosen relation is reflexive (round off to 3 decimal places) is _____.
 A 0.125
Engineering-Mathematics       Sets-And Relation       GATE 2020
Question 10 Explanation:
For a set with n elements,
The number of reflexive relations is 2^(n^2-n).
The total number of relations on a set with n elements is 2^ (n^2).
The probability of choosing the reflexive relation out of set of relations i s =  2^(n^2-n) /2^ (n^2) = 2^( n^2-n- n^2) = 2^(-n)
Given n=3, the probability will be 2^(-n) = ⅛ =  0.125
 Question 11
Consider the functions

Which of the above functions is/are increasing everywhere in [0,1]?
 A II and III only B III only C II only D I and III only
Engineering-Mathematics       Calculus       GATE 2020
Question 11 Explanation:
 Question 12
For n > 2, let a {0,1}n be a non-zero vector. Suppose that x is chosen uniformly at random from {0,1}n.
 A 0.5
Engineering-Mathematics       Probability       GATE 2020
Question 12 Explanation:
 Question 13
Graph G is obtained by adding vertex s to K3,4 and making s adjacent to every vertex of K3,4. The minimum number of colours required to edge-colour G is _____.
 A 7
Engineering-Mathematics       Graph-Theory       GATE 2020
Question 13 Explanation:
In k3x4 there are two sets with sizes 3,4. (its a complete bipartite graph).
The vertex in the set of size 3 has 4 edges connected to 4 vertices on other set. So, edge color of G is max(3,4) i.e. 4.
When a vertex is added to the graph with 7 vertices ( K 3x4 has 7 vertices), there would be 7 edges associated to that new vertex. As per the edge coloring “no two adjacent edges have same color).
As the new vertex with 7 edges need to be colored with 7 colors, the edge color of graph G is 7.
 Question 14
Which one of the following predicate formulae is NOT logically valid?
Note that W is a predicate formula without any free occurrence of x.
 A B C D
Engineering-Mathematics       Propositional-Logic       GATE 2020
Question 14 Explanation:

 Question 15
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 _______.
 A 12
Engineering-Mathematics       Combinatorics       GATE 2020
Question 15 Explanation:
There are 5 places
― ― ― ― ―
Given: L   I L A C
The derangements 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 16
Let A and B be two n×n matrices over real numbers. Let rank(M) and det(M) denote the rank and determinant of a matrix M, respectively. Consider the following statements,
I. rank(AB) = rank(A) rank(B)
II. det(AB) = det(A) det(B)
III. rank(A + B) ≤ rank(A) + rank(B)
IV. det(A + B) ≤ det(A) + det(B)
Which of the above statements are TRUE?
 A I and II only B I and IV only C III and IV only D II and III only
Engineering-Mathematics       Linear-Algebra       GATE 2020
Question 16 Explanation:
Rank(AB)≥Rank(A)+Rank(B)−n. So option I is wrong.
Rank is the number of independent rows(vectors) of a matrix. On product of two matrices, the combined rank is more than the sum of individual matrices (subrtraced with the order n)
det(AB) = det(A).det(b) as the magnitude remains same for the matrices after multiplication.
Note: We can just take a 2x2 matrix and check the options.
 Question 17
Consider a matrix  The largest eigenvalue of A is __________________
 A 3 B 4 C 5 D 6
Engineering-Mathematics       Linear-Algebra       Gate 2018
Question 17 Explanation:

Correction in Explanation:

⇒ (1 - λ)(2 - λ) - 2 = 0
⇒ λ2 - 3λ=0
λ = 0, 3
So maximum is 3.
 Question 18

Two people, P and Q, decide to independently roll two identical dice, each with 6 faces, numbered 1 to 6. The person with the lower number wins. In case of a tie, they roll the dice repeatedly until there is no tie. Define a trial as a throw of the dice by P and Q. Assume that all 6 numbers on each dice are equi-probable and that all trials are independent. The probability (rounded to 3 decimal places) that one of them wins on the third trial is __________.

 A 0.021 B 0.022 C 0.023 D 0.024
Engineering-Mathematics       Probability       Gate 2018
Question 18 Explanation:
When two identical dice are rolled
⇾ A person wins who gets lower number compared to other person.
⇾ There could be “tie”, if they get same number.
Favorable cases = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)}
Probability (tie) = 6/36 (when two dice are thrown, sample space = 6 × 6 = 36)
= 1/6
“Find the probability that one of them wins in the third attempt"
⇾ Which means, first & second time it should be tie and third time it should not be tie
⇾ P (tie) * P (tie) * P (not tie)
⇒ 1/6* 1/6 * (1 - 1/6)
⇒ (5/36×6) = 0.138/6 = 0.023
 Question 19
The chromatic number of the following graph is _______.

 A 1 B 2 C 3 D 4
Engineering-Mathematics       Graph-Theory       Gate 2018
Question 19 Explanation:
Chromatic number of the following graph is “3”
 Question 20
Let G be a finite group on 84 elements. The size of a largest possible proper subgroup of G is _________.
 A 41 B 42 C 43 D 44
Engineering-Mathematics       Set-Theory       Gate 2018
Question 20 Explanation:
Lagranges Theorem:
For any group ‘G’ with order ‘n’, every subgroup ‘H’ has order ‘k’ such that ‘n’ is divisible by ‘k’.
Solution:
Given order n = 84
Then the order of subgroups = {1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84}
As per the proper subgroup definition, it should be “42”.
 Question 21
Which one of the following is a closed form expression for the generating function of the sequence {an}, where a= 2n+3 for all n = 0, 1, 2, …?
 A 3/(1-x)2 B 3x/(1-x)2 C 2-x/(1-x)2 D 3-x/(1-x)2
Engineering-Mathematics       Combinatorics       Gate 2018
Question 21 Explanation:
 Question 22
The value of
 A 0.289 B 0.298 C 0.28 D 0.29
Engineering-Mathematics       Calculus       Gate 2018
Question 22 Explanation:
 Question 23

Assume that multiplying a matrix G1 of dimension p×q with another matrix G2 of dimension q×r requires pqr scalar multiplications. Computing the product of n matrices G1G2G3…Gn can be done by parenthesizing in different ways. Define GiGi+1 as an explicitly computed pair for a given parenthesization if they are directly multiplied. For example, in the matrix multiplication chain G1G2G3G4G5G6 using parenthesization(G1(G2G3))(G4(G5G6)), G2G3 and G5G6 are the only explicitly computed pairs.

Consider a matrix multiplication chain F1F2F3F4F5, where matrices F1, F2, F3, F4 and F5 are of dimensions 2×25, 25×3, 3×16, 16×1 and 1×1000, respectively. In the parenthesization of F1F2F3F4F5 that minimizes the total number of scalar multiplications, the explicitly computed pairs is/ are

 A F1F2 and F3F4 only B F2F3 only C F3F4 only D F1F2 and F4F5 only
Engineering-Mathematics       Linear-Algebra       Gate 2018
Question 23 Explanation:
→ As per above information, the total number of scalar multiplications are 2173.
→ Optimal Parenthesization is:
((F1(F2(F3 F4)))F5)
→ But according to the problem statement we are only considering F3, F4 explicitly computed pairs.
 Question 24

Consider the first-order logic sentence

φ ≡ ∃s∃t∃u∀v∀w∀x∀y ψ(s,t,u,v,w,x,y)

where ψ(s,t,u,v,w,x,y) is a quantifier-free first-order logic formula using only predicate symbols, and possibly equality, but no function symbols. Suppose φ has a model with a universe containing 7 elements.

Which one of the following statements is necessarily true?

 A There exists at least one model of φ with universe of size less than or equal to 3. B There exists no model of φ with universe of size less than or equal to 3. C There exists no model of φ with universe of size greater than 7. D Every model of φ has a universe of size equal to 7.
Engineering-Mathematics       Propositional-Logic       Gate 2018
Question 24 Explanation:
φ = ∃s∃t∃u∀v∀w∀x∀y ψ (s,t,u,v,w,x,y)
"∃" there exists quantifier decides whether a sentence belong to the model or not.
i.e., ~∃ will make it not belong to the model. (1) We have ‘7’ elements in the universe, So max. size of universe in a model = ‘7’
(2) There are three '∃' quantifiers, which makes that a model have atleast “3” elements. So, min. size of universe in model = ‘7’.
(A) is False because: (2)
(B) is true
(C) is false because of (1)
(D) is false, because these all models with size {3 to 7} not only ‘7’.
 Question 25

Consider Guwahati (G) and Delhi (D) whose temperatures can be classified as high (H), medium (M) and low (L). Let P(HG) denote the probability that Guwahati has high temperature. Similarly, P(MG) and P(LG) denotes the probability of Guwahati having medium and low temperatures respectively. Similarly, we use P(HD), P(MD) and P(LD) for Delhi.

The following table gives the conditional probabilities for Delhi’s temperature given Guwahati’s temperature.

Consider the first row in the table above. The first entry denotes that if Guwahati has high temperature (HG) then the probability of Delhi also having a high temperature (HD) is 0.40; i.e., P(HD ∣ HG) = 0.40. Similarly, the next two entries are P(MD ∣ HG) = 0.48 and P(LD ∣ HG) = 0.12. Similarly for the other rows.

If it is known that P(HG) = 0.2, P(MG) = 0.5, and P(LG) = 0.3, then the probability (correct to two decimal places) that Guwahati has high temperature given that Delhi has high temperature is _______ .

 A 0.6 B 0.61 C 0.62 D 0.63
Engineering-Mathematics       Linear-Algebra       Gate 2018
Question 25 Explanation:

The first entry denotes that if Guwahati has high temperature (HG ) then the probability that Delhi also having a high temperature (HD ) is 0.40.
P (HD / HG ) = 0.40
We need to find out the probability that Guwahati has high temperature.
Given that Delhi has high temperature (P(HG / HD )).

P (HD / HG ) = P(HG ∩ HD ) / P(HD )
= 0.2×0.4 / 0.2×0.4+0.5×0.1+0.3×0.01
= 0.60
 Question 26

Let N be the set of natural numbers. Consider the following sets,

P: Set of Rational numbers (positive and negative)
Q: Set of functions from {0, 1} to N
R: Set of functions from N to {0, 1}
S: Set of finite subsets of N

Which of the above sets are countable?

 A Q and S only B P and S only C P and R only D P, Q and S only
Engineering-Mathematics       Linear-Algebra       Gate 2018
Question 26 Explanation:
Set of rational numbers are countable. It is proved by various methods in literature.
Set of functions from {0,1} to N is countable as it has one to one correspondence to N.
Set of functions from N to {0,1} is uncountable, as it has one to one correspondence to set of real numbers between (0 and 1).
Set of finite subsets of N is countable.
 Question 27

Consider the following statements.

(I) P does not have an inverse
(II) P has a repeated eigenvalue
(III) P cannot be diagonalized

Which one of the following options is correct?

 A Only I and III are necessarily true B Only II is necessarily true C Only I and II are necessarily true D Only II and III are necessarily true
Engineering-Mathematics       Linear-Algebra       Gate 2018
Question 27 Explanation:

Though the multiple of a vector represents same vector, and each eigen vector has distinct eigen value, we can conclude that ‘p’ has repeated eigen value.
If the unique eigen value corresponds to an eigen vector e, but the repeated eigen value corresponds to an entire plane, then the matrix can be diagonalized, using ‘e’ together with any two vectors that lie in plane.
But, if all eigen values are repeated, then the matrix cannot be diagonalized unless it is already diagonal.
So (III) holds correct.
A diagonal matrix can have inverse, So (I) is false.
Then (II) and (III) are necessarily True.
 Question 28

Let G be a graph with 100! vertices, with each vertex labeled by a distinct permutation of the numbers 1, 2, …, 100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and z denote the number of connected components in G.

Then, y + 10z = ___________.

 A 109 B 110 C 111 D 112
Engineering-Mathematics       Graph-Theory       Gate 2018
Question 28 Explanation:
G is a graph with 100! vertices. Label of each vertex obtains from distinct permutation of numbers “1, 2, … 100”.
There exists edge between two vertices iff label of ‘u’ is obtained by swapping two adjacent numbers in label of ‘v’.
Example:
12 & 21, 23 & 34
The sets of the swapping numbers be (1, 2) (2, 3) (3, 4) … (99).
The no. of such sets are 99 i.e., no. of edges = 99.
As this is regular, each vertex has ‘99’ edges correspond to it.
So degree of each vertex = 99 = y.
As the vertices are connected together, the number of components formed = 1 = z
y + 102 = 99 + 10(1) = 109
 Question 29

Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are:

Note: The height of a tree with a single node is 0.
 A 4 and 15 respectively B 3 and 14 respectively C 4 and 14 respectively D 3 and 15 respectively
Engineering-Mathematics       Binary-Trees       Gate 2017 set-01
Question 29 Explanation:
T be a Binary Search Tree with 15 nodes.
The height of a tree with single node is 0.
Minimum possible height is when it is a complete binary tree.

Maximum possible height is when it is a skewed tree left/right.

So the minimum and maximum possible heights of T are: 3 and 14 respectively.
 Question 30
The statement (¬p) ⇒ (¬q) is logically equivalent to which of the statements below?
I. p ⇒ q
II. q ⇒ p
III. (¬q) ∨ p
IV. (¬p) ∨ q

 A I only B I and IV only C II only D II and III only
Engineering-Mathematics       Propositional-Logic       Gate 2017 set-01
Question 30 Explanation:
Method 1:
Construct Truth tables:
~p ⇒ ~q

II, III are equivalent to (~p) ⇒ (~q)
Method 2:
(I) p⇒q ≡ ~p∨q
(II) q⇒p ≡ ~q∨p
(III) (~q) ∨ p ≡ ~q∨p
(IV) (~p) ∨ p ≡ ~p∨q
Also, from question:
(~p) ⇒ (~q)
≡ p∨~q
So, (II) & (III) are equivalent to the statement given in question.
 Question 31

Consider the first-order logic sentence F: ∀x(∃yR(x,y)). Assuming non-empty logical domains, which of the sentences below are implied by F?

I. ∃y(∃xR(x,y))
II. ∃y(∀xR(x,y))
III. ∀y(∃xR(x,y))
IV. ¬∃x(∀y¬R(x,y))

 A IV only B I and IV only C II only D II and III only
Engineering-Mathematics       Prepositional-Logic       Gate 2017 set-01
Question 31 Explanation:
Lets convert the given first order logic sentence into some english sentence.
F: ∀x(∃yR(x,y)) (given)
: For all girls there exist a boyfriend
(x for girls and y for boys)
I: ∃y(∃xR(x,y))
: There exist some boys who have girlfriends.
(Subset of statement F, so True)
II: ∃y(∀xR(x,y))
: There exists some boys for which all the girls are girlfriend. (False)
III: ∀y(∃xR(x,y))
: For all boys exists a girlfriend. (False)
IV: ~∃x(∀y~R(x,y))
= ∀x(~∀y~R(x,y))
= ∀x(∃yR(x,y)) (∵ ~∀y=∃y, ~∃x=∀x)
(True)
 Question 32
Let c1, cn be scalars not all zero. Such that the following expression holds: where ai is column vectors in Rn. Consider the set of linear equations. Ax = B. where A = [a1.......an] and Then, Set of equations has
 A a unique solution at x = Jn where Jn denotes a n-dimensional vector of all 1 B no solution C infinitely many solutions D finitely many solutions
Engineering-Mathematics       Linear-Algebra       Gate 2017 set-01
Question 32 Explanation:
ai is a column vector
AX = B

As given that
and c1&cn ≠ 0
means c0a0 + c1a1 + ...cnan = 0, represents that a0, a1... an are linearly dependent.
So rank of 'A' = 0, (so if ‘B’ rank is = 0 infinite solution, ‘B’ rank>0 no solution) ⇾(1)
Another condition given here is, 'Σai = b',
so for c1c2...cn = {1,1,...1} set, it is having value 'b',
so there exists a solution if AX = b →(2)
From (1)&(2), we can conclude that AX = B has infinitely many solutions.
 Question 33

Let X be a Gaussian random variable with mean 0 and variance σ2. Let Y = max(X, 0) where max(a,b) is the maximum of a and b. The median of Y is __________.

 A 0 B 1 C 2 D 3
Engineering-Mathematics       Probability       Gate 2017 set-01
Question 33 Explanation:
Given that, Y = max(X,0),which means, Y is 0 for negative values of X and Y is X for positive values of X.
Median is a point, where the probability of getting less than median is 1/2 and probability of getting greater than median is 1/2.
From the given details, we can simply conclude that, median is 0. (0 lies exactly between positive and negative values)
 Question 34
The value of
 A is 0 B is -1 C is 1 D does not exist
Engineering-Mathematics       Calculus       Gate 2017 set-01
Question 34 Explanation:

If "x=1" is substituted we get 0/0 form, so apply L-Hospital rule

Substitute x=1
⇒ (7(1)6-10(1)4)/(3(1)2-6(1)) = (7-10)/(3-6) = (-3)/(-3) = 1
 Question 35

Let p, q and r be prepositions and the expression (p → q) → r be a contradiction. Then, the expression (r → p) → q is

 A a tautology B a contradiction C always TRUE when p is FALSE D always TRUE when q is TRUE
Engineering-Mathematics       Prepositional-Logic       Gate 2017 set-01
Question 35 Explanation:
Given that (p→q)→r is a contradiction.
So r = F and (p→q) = T.
We have to evaluate the expression
(r→p)→q
Since r = F, (r→p) = T (As F→p, is always true)
The final expression is T→q and this is true when q is true, hence option D.
 Question 36

Let u and v be two vectors in R2 whose Euclidean norms satisfy ||u||=2||v||. What is the value of α such that w = u + αv bisects the angle between u and v?

 A 2 B 1/2 C 1 D -1/2
Engineering-Mathematics       Linear-Algebra       Gate 2017 set-01
Question 36 Explanation:

Let u, v be vectors in R2, increasing at a point, with an angle θ.
A vector bisecting the angle should split θ into θ/2, θ/2
Means ‘w’ should have the same angle with u, v and it should be half of the angle between u and v.
Assume that the angle between u, v be 2θ (thus angle between u,w = θ and v,w = θ)
Cosθ = (u∙w)/(∥u∥ ∥w∥) ⇾(1)
Cosθ = (v∙w)/(∥v∥ ∥w∥) ⇾(2)
(1)/(2) ⇒ 1/1 = ((u∙w)/(∥u∥ ∥w∥))/((v∙w)/(∥v∥ ∥w∥)) ⇒ 1 = ((u∙w)/(∥u∥))/((v∙w)/(∥v∥))
⇒ (u∙w)/(v∙w) = (∥u∥)/(∥v∥) which is given that ∥u∥ = 2 ∥v∥
⇒ (u∙w)/(v∙w) = (2∥v∥)/(∥v∥) = 2 ⇾(3)
Given ∥u∥ = 2∥v∥
u∙v = ∥u∥ ∥v∥Cosθ
=2∙∥v∥2 Cosθ
w = u+αv
(u∙w)/(v∙w) = 2
(u∙(u+αv))/(v∙(u+αv)) = 2
(u∙u+α∙u∙v)/(u∙v+α∙v∙v) = 2a∙a = ∥a∥2
4∥v∥2+α∙2∙∥v∥2 Cosθ = 2(2∥v∥2 Cosθ+α∙∥v∥2)
4+2αCosθ = 2(2Cosθ+α)
4+2αCosθ = 4Cosθ+2α ⇒ Cosθ(u-v)+2α-4 = 0
4-2α = Cosθ(4-2α)
(4-2α)(Cosθ-1) = 0
4-2α = 0
 Question 37
Let A be m×n real valued square symmetric matrix of rank 2 with expression given below. Consider the following statements
(i)  One eigenvalue must be in [-5, 5].
(ii) The eigenvalue with the largest magnitude
must be strictly greater than 5.

Which of the above statements about engenvalues of A is/are necessarily CORRECT?
 A Both (I) and (II) B (I) only C (II) only D Neither (I) nor (II)
Engineering-Mathematics       Linear-Algebra       Gate 2017 set-01
Question 37 Explanation:
Let

be a real valued, rank = 2 matrix.

a2+b2+c2+d2 = 50
Square values are of order 0, 1, 4, 9, 16, 25, 36, …
So consider (0, 0, 5, 5) then Sum of this square = 0+0+25+25=50
To get rank 2, the 2×2 matrix can be

The eigen values are,
|A-λI| = 0 (The characteristic equation)

-λ(-λ)-25 = 0
λ2-25 = 0

So, the eigen values are within [-5, 5], Statement I is correct.
The eigen values with largest magnitude must be strictly greater than 5: False.
So, only Statement I is correct.
 Question 38

The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is _________.

 A 271 B 272 C 273 D 274
Engineering-Mathematics       Combinatorics       Gate 2017 set-01
Question 38 Explanation:

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|+C-|A∩B|-|A∩C|-|B∩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|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|
= 166+100+71-33-28-14+4
= 271
 Question 39

 A B C D
Engineering-Mathematics       Calculus       GATE 2017(set-02)
Question 39 Explanation:

 Question 40

Let p, q, r denote the statements “It is raining”, “It is cold”, and “It is pleasant”, respectively. Then the statement “It is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold” is represented by

 A (¬p ∧ r) ∧ (¬r → (p ∧ q)) B (¬p ∧ r) ∧ ((p ∧ q) → ¬r) C (¬p ∧ r) ∨ ((p ∧ q) → ¬r) D (¬p ∧ r) ∨ (r → (p ∧ q))
Engineering-Mathematics       Prepositional-Logic       GATE 2017(set-02)
Question 40 Explanation:
p: It is raining
q: It is cold
r: It is pleasant
“If it is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold.”
We can divide the statement into two parts with “Conjunction”.

i.e., ¬r→(p∧q) ⇾(2)
From (1) & (2), the given statement can be represented as
 Question 41
 A Nβ (1 - β) B Nβ C N (1 - β) D Not expressible in terms of N and β alone
Engineering-Mathematics       Probability       GATE 2017(set-02)
Question 41 Explanation:
For a discrete random variable X,
Given gy (z) = (1 - β + βz)N ⇾ it is a binomial distribution like (x+y)n
Expectation (i.e., mean) of a binomial distribution will be np.
The polynomial function ,
given
Mean of Binomial distribution of b(xj,n,p)=
The probability Mass function,

Given:
 Question 42

Consider the set X = {a,b,c,d e} under the partial ordering

R = {(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),(b,e),(c,c),(c,e),(d,d),(d,e),(e,e)}.

The Hasse diagram of the partial order (X,R) is shown below.

The minimum number of ordered pairs that need to be added to R to make (X,R) a lattice is _________.

 A 0 B 1 C 2 D 3
Engineering-Mathematics       Set-Theory       GATE 2017(set-02)
Question 42 Explanation:
R = {(a,a), (a,b), (a,c), (a,d), (a,e), (b,b), (b,c), (b,e), (c,c), (c,e), (d,d), (d,e), (e,e)}
As per the definition of lattice, each pair should have GLB, LUB.
The given ‘R’ has GLB, LUB for each and every pair.
So, no need to add extra pair.
Thus no. of required pair such that Hasse diagram to become lattice is “0”.
 Question 43

 A 2 B 3 C 4 D 5
Engineering-Mathematics       Matrices       GATE 2017(set-02)
Question 43 Explanation:

R2→R2+R1

The number of non-zero rows of P + Q = 2,
So Rank = 2
Note: “Rank” is the number of independent vectors.
Method-1:
Each vector is a row in matrix.
Echelon form of a matrix has no. of zeroes increasing each rows.
The total non-zero rows left give the rank.
Method-2:
Find determinant of matrix, for 3×5, if determinant is ‘0’, the max rank can be 2.
If determinant of any n×n is non-zero, then rows proceed with (n-1)×(n-1).
 Question 44

G is an undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. Then the maximum possible value of n is ___________.

 A 16 B 17 C 18 D 19
Engineering-Mathematics       Graph-Theory       GATE 2017(set-02)
Question 44 Explanation:
An undirected graph ‘G’ has ‘n’ vertices & 25 edges.
Degree of each vertex ≥ 3

|v| = 2|E|
The relation between max and min degree of graph are
m ≤ 2|E| / |v| ≤ M
Given minimum degree = 3
So, 3 ≤2 |E| / |v|
3|v| ≤ 2|E|
3(n) ≤ 2(25)
n ≤ 50/3
n ≤ 16.6
(n = 16)
 Question 45
P and Q are considering to apply for job. The probability that p applies for job is 1/4. The probability that P applies for job given that Q applies for the job 1/2 and The probability that Q applies for job given that P applies for the job 1/3.The probability that P does not apply for job given that Q does not apply for the job
 A B C D
Engineering-Mathematics       Probability       GATE 2017(set-02)
Question 45 Explanation:
Probability that ‘P’ applies for a job = 1/4 = P(p) ⇾ (1)
Probability that ‘P’ applies for the job given that Q applies for the job = P(p/q) = 1/2 ⇾ (2)
Probability that ‘Q’ applies for the job, given that ‘P’ applies for the job = P(p/q) = 1/3 ⇾ (3)
Bayes Theorem:
(P(A/B) = (P(B/A)∙P(A))/P(B) ; P(A/B) = P(A∩B)/P(B))
⇒ P(p/q) = (P(q/p)∙P(p))/p(q)
⇒ 1/2 = (1/3×1/4)/p(q)
p(q) = 1/12×2 = 1/(6) (P(q) = 1/6) ⇾ (4)
From Bayes,
P(p/q) = (P(p∩q))/(P(q))
1/2 = P(p∩q)/(1⁄6)
(p(p∩q) = 1/12)
We need to find out the “probability that ‘P’ does not apply for the job given that q does not apply for the job = P(p'/q')
From Bayes theorem,
P(p'/q') = (P(p'∩q'))/P(q') ⇾ (5)
We know,
p(A∩B) = P(A) + P(B) - P(A∪B)
also (P(A'∩B') = 1 - P(A∪B))
P(p'∩q') = 1 - P(p∪q)
= 1 - (P(p) + P(q) - P(p∩q))
= 1 - (P(p) + P(q) - P(p) ∙ P(q))
= 1 - (1/4 + 1/6 - 1/12)
= 1 - (10/24 - 2/24)
= 1 - (8/24)
= 2/3
(P(p'∩q') = 2/3) ⇾ (6)
Substitute in (5),
P(p'⁄q') = (2⁄3)/(1-P(q)) = (2⁄3)/(1-1/6) = (2⁄3)/(5⁄6) = 4/5
(P(p'/q') = 4/5)
 Question 46
 A 15 B 16 C 17 D 18
Engineering-Mathematics       Combinatorics       GATE 2017(set-02)
Question 46 Explanation:
 Question 47

If a random variable X has a Poisson distribution with mean 5, then the expectation E[(X + 2)2] equals _________.

 A 54 B 55 C 56 D 57
Engineering-Mathematics       Probability       GATE 2017(set-02)
Question 47 Explanation:
In Poisson distribution:
Mean = Variance
E(X) = E(X2) - (E(X))2 = 5
E(X2) = 5 + (E(X))2 = 5 + 25 = 30
So, E[(X + 2)2] = E[X2 + 4 + 4X]
= E(X2) + 4 + 4E(X)
= 30 + 4 + 4 × 5
= 54
 Question 48

If the characteristic polynomial of a 3 × 3 matrix M over R (the set of real numbers) is λ3 - 4λ2 + aλ + 30, a ∈ ℝ, and one eigenvalue of M is 2, then the largest among the absolute values of the eigenvalues of M is ________.

 A 5 B 6 C 7 D 8
Engineering-Mathematics       Linear-Algebra       GATE 2017(set-02)
Question 48 Explanation:
For a 3 × 3 matrix ‘M’, the characteristic equation |A – λI| is
λ3 - 4λ2 + aλ + 30 = 0 ⇾ (1)
One eigen value is ‘2’, so substitute it
23 - 4(2)2 + a(2) + 30 = 0
8 - 16 + 2a + 30 = 0
2a = -22
a = -11
Substitute in (1),
λ3 - 4λ2 - 11 + 30 = 0

So, (1) can be written as
(λ - 2)(λ2 - 2λ - 15) = 0
(λ - 2)(λ2 - 5λ + 3λ - 15) = 0
(λ - 2)(λ - 3)(λ - 5) = 0
λ = 2, 3, 5
Max λ=5
 Question 49

Let p,q,r,s represent the following propositions.

p: x ∈ {8,9,10,11,12}
q: x is a composite number
r: x is a perfect square
s: x is a prime number

The integer x≥2 which satisﬁes ¬((p ⇒ q) ∧ (¬r ∨ ¬s))  is _________.

 A 11 B 12 C 13 D 14
Engineering-Mathematics       Prepositional-Logic       2016 set-01
Question 49 Explanation:
Given,
~((p→q) ∧ (~r ∨ ~S))
⇒ first simplify the given statement by converging them to ∧, ∨
⇒ [~(p→q) ∨ (~(~r ∨ ~s)]
Demorgan’s law:
⇒ [~(~p ∨ q) ∨ (r ∧ s)]
∵ p→q ≡ ~p ∨ q
⇒ [(p ∧ ~q) ∨ (r ∧ s)]
p ∧ ~q is {8,9,10,11,12} ∧ {not a composite number} i.e. {11}
r ∧ s is {perfect square} ∧ {prime} i.e. no answer
So, the one and only answer is 11.
 Question 50

Let an be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for an?

 A an = a(n-1) + 2a(n-2) B an = a(n-1) + a(n-2) C an = 2a(n-1) + a(n-2) D an = 2a(n-1) + 2a(n-2)
Engineering-Mathematics       Combinatorics       2016 set-01
Question 50 Explanation:
an = number of n-bit strings, that do not have two consecutive 1’s.
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 a3 = a1 + a2
Similarly, an = an-1 + an-2
 Question 51

 A 4 B 3 C 2 D 1
Engineering-Mathematics       Calculus       2016 set-01
Question 51 Explanation:
 Question 52

A probability density function on the interval [a,1] is given by 1/x2 and outside this interval the value of the function is zero. The value of a is _________.

 A 0.7 B 0.6 C 0.5 D 0.8
Engineering-Mathematics       Probability       2016 set-01
Question 52 Explanation:
The property of probability density function is area under curve = 1
or

where (a, b) is internal and f(x) is probability density function.
Given,
f(x) = 1/x2 , a≤x≤1
The area under curve,

- 1 + 1/a = 1
1/a = 2
a = 0.5
 Question 53

Two eigenvalues of a 3 × 3 real matrix P are (2 + √-1) and 3. The determinant of P is __________.

 A 18 B 15 C 17 D 16
Engineering-Mathematics       Linear-Algebra       2016 set-01
Question 53 Explanation:
If an eigen value of a matrix is a complex number, then there will be other eigen value, which is conjugate of the complex eigen value.
So, For the given 3×3 matrix there would be 3 eigen values.
Given eigen values are : 2+i and 3.
So the third eigen value should be 2-i.
As per the theorems, the determinant of the matrix is the product of the eigen values.
So the determinant is (2+i)*(2-i)*3 = 15.
 Question 54

The coefﬁcient of x12 in (x3 + x4 + x5 + x6 + ...)3 is _________.

 A 10 B 11 C 12 D 13
Engineering-Mathematics       Combinatorics       2016 set-01
Question 54 Explanation:
Co-efficient of x12 in (x3 + x4 + x5 + x6+...)3
⇒ [x3(1 + x + x2 + x3 + ...)]3
= x9(1 + x + x2 + x3 + ...)3
First Reduction:
As x9 is out of the series, we need to find the co-efficient of x3 in (1 + x + x2 + ⋯)3

Here, m=3, k=3, the coefficient

= 5C3 = 5!/2!3! = 10
 Question 55

Consider the recurrence relation a1 = 8, an = 6n2 + 2n + an-1. Let a99 = K × 104. The value of K is ___________.

 A 198 B 199 C 200 D 201
Engineering-Mathematics       Combinatorics       2016 set-01
Question 55 Explanation:
an = 6n2 + 2n + a(n-1)
Replace a(n-1)

⇒ an = 6n2 + 2n + 6(n-1)2 + 2(n-1) + 6(n-2)2 + 2(n-2) + ⋯ a1
Given that a1 = 8, replace it
⇒ an = 6n2 + 2n + 6(n-1)2 + 2(n-1) + 6(n-2)2 + 2(n-2) + ⋯8
= 6n2 + 2n + 6(n-1)2 + 2(n-1) + 6(n-2)2 + 2(n-2) + ⋯ + 6(1)2 + 2(1)

= 6(n2 + (n-1)2 + (n-2)2 + ⋯ + 22 + 12) + 2(n + (n-1) + ⋯1)
Sum of n2 = (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 a99 = k×104
a99 = 2(99)(100)2 = 198 × 104
∴k = 198
 Question 56

A function f:N+ → N+, deﬁned on the set of positive integers N+, satisﬁes the following properties:

f(n) = f(n/2)           if n is even
f(n) = f(n+5)           if n is odd

Let R = {i|∃j: f(j)=i} be the set of distinct values that f takes. The maximum possible size of R is __________.

 A 2 B 3 C 4 D 5
Engineering-Mathematics       Set-Theory       2016 set-01
Question 56 Explanation:
f(n)= f(n⁄2)          if n is even
f(n)= f(n+5)        if n is odd

We can observe that

and f(5) = f(10) = f(15) = f(20)
Observe that f(11) = f(8)
f(12) = f(6) = f(3)
f(13) = f(9) = f(14) = f(7) = f(12) = f(6) = f(3)
f(14) = f(9) = f(12) = f(6) = f(3)
f(16) = f(8) = f(4) = f(2) = f(1) [repeating]
So, we can conclude that
‘R’ can have size only ‘two’ [one: multiple of 5’s, other: other than 5 multiples]
 Question 57

Consider the following experiment.

Step1. Flip a fair coin twice.
Step2. If the outcomes are (TAILS, HEADS) then output Y and stop.
Step4. If the outcomes are (TAILS, TAILS), then go to Step 1.

The probability that the output of the experiment is Y is (up to two decimal places) ________.

 A 0.33 B 0.34 C 0.35 D 0.36
Engineering-Mathematics       Probability       2016 set-01
Question 57 Explanation:
If a coin is flipped twice, the possible outcomes {HH, HT, TH, TT}
Stop conditions:
If outcome = TH then Stop [output 4] --------------- (1)
else
outcome = HH/ HT then Stop [output N] -------------- (2)
We get ‘y’ when we have (1) i.e., ‘TH’ is output.
(1) can be preceded by ‘TT’ also, as ‘TT’ will reset (1) again
Probability of getting y = TH + (TT)(TH) + (TT)(TT)(TH) + …
= 1/2 × 1/2 + 1/2 × 1/2 × 1/2 × 1/2 + ...
= (1/4)/(1-1/4)
= 1/3
= 0.33
 Question 58

Consider the following expressions:

(i) false
(ii) Q
(iii) true
(iv) P ∨ Q
(v) ¬Q ∨ P

The number of expressions given above that are logically implied by P ∧ (P ⇒ Q) is _________.

 A 4 B 5 C 6 D 7
Engineering-Mathematics       Propositional-Logic       GATE 2016 set-2
Question 58 Explanation:
The expression is logically implied by P ∧ (P → Q) means
(P ∧ (P → Q))→ expression is a tautology. So we have to find
How many tautological formulas are there for the given inputs.
(P ∧ (P → Q)) → True is always tautology
(P ∧ (P → Q)) → False is not a tautology
(P ∧ (P → Q)) → Q is a tautology
(P ∧ (P → Q)) → ¬Q ∨ P is a tautology
(P ∧ (P → Q)) → P ∨ Q is a tautology
So there are 4 expressions logically implied by (P ∧ (P → Q))
 Question 59

Let f(x) be a polynomial and g(x) = f'(x) be its derivative. If the degree of (f(x) + f(-x)) is 10, then the degree of (g(x) - g(-x)) is __________.

 A 9 B 10 C 11 D 12
Engineering-Mathematics       Calculus       GATE 2016 set-2
Question 59 Explanation:
If the degree of a polynomial is ‘n’ then the derivative of that function have (n – 1) degree.
It is given that f(x) + f(-x) degree is 10.
It means f(x) is a polynomial of degree 10.
Then obviously the degree of g(x) which is f’(x) will be 9.
 Question 60

The minimum number of colours that is sufﬁcient to vertex-colour any planar graph is ________.

 A 4 B 5 C 6 D 7
Engineering-Mathematics       Graph-Theory       GATE 2016 set-2
Question 60 Explanation:
The 4-colour theorem of the planar graph describes that any planar can atmost be colored with 4 colors.
Here it is asked about the sufficient number of colors, so with the worst case of 4 colors we can color any planar graph.
 Question 61

Consider the systems, each consisting of m linear equations in n variables.

I. If m < n, then all such systems have a solution
II. If m > n, then none of these systems has a solution
III. If m = n, then there exists a system which has a solution

Which one of the following is CORRECT?

 A I, II and III are true B Only II and III are true C Only III is true D None of them is true
Engineering-Mathematics       Linear-Algebra       GATE 2016 set-2
Question 61 Explanation:
i) If m In AX = B,
If R(A) ≠ R(A|B)
then there will be no solution.
ii) False, because if R(A) = R(A|B),
then there will be solution possible.
iii) True, if R(A) = R(A|B),
then there exists a solution.
 Question 62

Suppose that a shop has an equal number of LED bulbs of two different types. The probability of an LED bulb lasting more than 100 hours given that it is of Type 1 is 0.7, and given that it is of Type 2 is 0.4. The probability that an LED bulb chosen uniformly at random lasts more than 100 hours is _________.

 A 0.55 B 0.56 C 0.57 D 0.58
Engineering-Mathematics       Probability       GATE 2016 set-2
Question 62 Explanation:

The bulbs of Type 1, Type 2 are same in number.
So, the probability to choose a type is 1/2.
The probability to choose quadrant ‘A’ in diagram is
P(last more than 100 hours/ type1) = 1/2 × 0.7
P(last more than 100 hours/ type2) = 1/2 × 0.4
Total probability = 1/2 × 0.7 + 1/2 × 0.4 = 0.55
 Question 63

Suppose that the eigenvalues of matrix A are 1, 2, 4. The determinant of (A-1)T is _________.

 A 0.125 B 0.126 C 0.127 D 0.128
Engineering-Mathematics       Linear-Algebra       GATE 2016 set-2
Question 63 Explanation:
Determinant of a matrix is product of the eigen values.
Given that eigen values are 1, 2, 4.
So, its determinant is 1*2*4 = 8
The determinant of (A-1)T = 1/ AT = 1/|A| = 1/8 = 0.125
 Question 64

A binary relation R on ℕ × ℕ is deﬁned as follows: (a,b)R(c,d) if a≤c or b≤d. Consider the following propositions:

P: R is reﬂexive
Q: Ris transitive

Which one of the following statements is TRUE?

 A Both P and Q are true. B P is true and Q is false. C P is false and Q is true. D Both P and Q are false.
Engineering-Mathematics       Set-Theory       GATE 2016 set-2
Question 64 Explanation:
For every a,b ∈ N,
a≤c ∨ b≤d
Let a≤a ∨ b≤b is true for all a,b ∈ N
So there exists (a,a) ∀ a∈N.
It is Reflexive relation.
Consider an example
c = (a,b)R(c,d) and (c,d)R(e,f) then (a,b)R(e,f)
This does not hold for any (a>e) or (b>f)
eg:
(2,2)R(1,2) as 2≤2
(1,2)R(1,1) as 1≤1
but (2,2) R (1,1) is False
So, Not transitive.
 Question 65

Which one of the following well-formed formulae in predicate calculus is NOT valid?

 A (∀x p(x) ⇒ ∀x q(x)) ⇒ (∃x ¬p(x) ∨ ∀x q(x)) B (∃x p(x) ∨ ∃x q(x)) ⇒ ∃x (p(x) ∨ q(x)) C ∃x (p(x) ∧ q(x)) ⇒ (∃x p(x) ∧ ∃x q(x)) D ∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀x q(x))
Engineering-Mathematics       Propositional-Logic       GATE 2016 set-2
Question 65 Explanation:
For the formulae to be valid there should not be implication like T → F.
But in option (D), we can generate T → F.
Hence, not valid.
 Question 66

Consider a set U of 23 different compounds in a Chemistry lab. There is a subset S of U of 9 compounds, each of which reacts with exactly 3 compounds of U. Consider the following statements:

I. Each compound in U\S reacts with an odd number of compounds.
II. At least one compound in U\S reacts with an odd number of compounds.
III. Each compound in U\S reacts with an even number of compounds.

Which one of the above statements is ALWAYS TRUE?

 A Only I B Only II C Only III D None
Engineering-Mathematics       Set-Theory       GATE 2016 set-2
Question 66 Explanation:
There are set of ‘23’ different compounds.
U = 23
∃S ∋ (S⊂U)
Each component in ‘S’ reacts with exactly ‘3’ compounds of U,

If a component ‘a’ reacts with ‘b’, then it is obvious that ‘b’ also reacts with ‘a’.
It’s a kind of symmetric relation.>br> If we connect the react able compounds, it will be an undirected graph.
The sum of degree of vertices = 9 × 3 = 27
But, in the graph of ‘23’ vertices the sum of degree of vertices should be even because
(di = degree of vertex i.e., = no. of edges)
But ‘27’ is not an even number.
To make it an even, one odd number should be added.
So, there exists atleast one compound in U/S reacts with an odd number of compounds.
 Question 67

The value of the expression 1399(mod 17), in the range 0 to 16, is ________.

 A 4 B 5 C 6 D 7
Engineering-Mathematics       Modular-Arithmetic       GATE 2016 set-2
Question 67 Explanation:
Fermat’s theorem,
a(p-1) ≡ 1 mod p (p is prime)
From given question,
p = 17
a(17-1) ≡ 1 mod 17
a16 ≡ 1 mod 17
1316 ≡ 1 mod 17
Given:
1399 mod 17

133 mod 17
2197 mod 17
4
 Question 68
In the LU decomposition of the matrix
| 2  2 |
| 4  9 |
, if the diagonal elements of U are both 1, then the lower diagonal entry l22 of L is
 A 5 B 6 C 7 D 8
Engineering-Mathematics       Linear-Algebra       GATE 2015 (Set-01)
Question 68 Explanation:
A = LU

l11 = 2 -----(1)
l11u12 = 2
u12 = 2/2
u12 = 1 ----- (2)
l21 = 4 ----- (3)
l21u12+l22 = 9
l22 = 9 - l21u12 = 9 - 4 × 1 = 5
 Question 69
 A h(x)/g(x) B -1/x C g(x)/h(x) D x/(1-x)2
Engineering-Mathematics       Calculus       GATE 2015 (Set-01)
Question 69 Explanation:
g(x)= 1 – x, h(x)=x/x-1 -------- (2)
Replace x by h(x) in (1), replacing x by g(x) in (2),
g(h(x))=1-h(x)=1-x/x-1=-1/x-1
h(g(x))=g(x)/g(x)-1=1-x/-x
⇒ g(h(x))/h(g(x))=x/(x-1)(1-x)=(x/x-1)/1-x=h(x)/g(x)
 Question 70
Suppose L = {p, q, r, s, t} is a lattice represented by the following Hasse diagram: For any x, y ∈ L, not necessarily distinct, x ∨ y and x ∧ y are join and meet of x, y respectively. Let L3 = {(x,y,z): x, y, z ∈ L} be the set of all ordered triplets of the elements of L. Let pr be the probability that an element (x,y,z) ∈ L3 chosen equiprobably satisfies x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z). Then
 A pr = 0 B pr = 1 C 0 < pr ≤ 1/5 D 1/5 < pr < 1
Engineering-Mathematics       Set-Theory       GATE 2015 (Set-01)
Question 70 Explanation:
Total number of elements i.e., ordered triplets (x,y,z) in L3 are 5×5×5 i.e., 125 n(s) = 125
Let A be the event that an element (x,y,z)∈ L3 satisfies x ∨(y∧z) = (x∨y) ∧ (x∨z) Since q∨(r∧s) = q∨p = q
and (q∨r)∧(q∨s)=t∧t=t q∨(r∧s)≠(q∨r)∧(q∨s)
Therefore, (x,y,z) = (q,r,s),(q,s,r),(r,q,s),(r,s,q),(s,r,q),(s,q,r)
i.e., 3! = 6 elements will not satisfy distributive law and all other (x,y,z) choices satisfy distributive law
n(A) = 125-6 = 119
∴ required probability is 119/125
⇒ 1/5
 Question 71
Consider the following 2 × 2 matrix A where two elements are unknown and are marked by a and b. The eigenvalues of this matrix are –1 and 7. What are the values of a and b?
A = | 1  4 |
| b  a |
 A a=6,b=4 B a=4,b=6 C a=3,b=5 D a=5,b=3
Engineering-Mathematics       Linear-Algebra       GATE 2015 (Set-01)
Question 71 Explanation:
Given λ1=-1 and λ2=7 are eigen values of A
By properties,

⇒ 6=1+a and -7=a-4b
⇒ a=5 ⇒ -7=5-4b
⇒ b=3
 Question 72
Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source.  For x ∈ V , let d(x)denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u, v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u- d(v) ?
 A -1 B 0 C 1 D 2
Engineering-Mathematics       BFS       GATE 2015 (Set-01)
Question 72 Explanation:
In an undirected graph if (u, v) be the edge then (u, v) also the edge. So shortest path that can be obtained by the (u, v) of (u, v).
Then the difference between the d(u) and d(v) is not more than '1'.
In the option 'D' the difference is given as '2' it is not possible in the undirected graph.
 Question 73

 A -1 B -2 C -3 D -4
Engineering-Mathematics       Calculus       GATE 2015 (Set-01)
Question 73 Explanation:
 Question 74
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is _______________.
 A 24 B 25 C 26 D 27
Engineering-Mathematics       Graph-Theory       GATE 2015 (Set-01)
Question 74 Explanation:
By Euler’s formula,
|V|+|R|=|E|+2 ------(1) where |V|, |E|, |R| are respectively number of vertices, edges and faces (regions)
Given |V|=10 ------(2) and number of edges on each face is three
∴3|R|=2|E|⇒|R|=2/3|E| ------(3)
Substituting (2), (3) in (1), we get
10+2/3|E|=|E|+2⇒|E|/3=8⇒|E|=24
 Question 75
Consider the operations f(X, Y, Z) = X'YZ + XY' + Y'Z'  and  g(X′, Y, Z) = X′YZ + X′YZ′ + XY Which one of the following is correct?
 A Both {f} and {g} are functionally complete B Only {f} is functionally complete C Only {g} is functionally complete D Neither {f} nor {g} is functionally complete
Engineering-Mathematics       Set-Theory       GATE 2015 (Set-01)
Question 75 Explanation:
A function is functionally complete if (OR, NOT) or (AND, NOT) are implemented by it.
f(X,X,X)=X'XX'+XX'+X'X'
=0+0+X'
=X'
Similarly, f(Y,Y,Y)=Y' and f(X,Z,Z)=Z'
f(Y',Y',Z')=(Y')'Y'Z'+Y'(Y')'+(Y')'(Z')'
=YY'Z'+Y'Y+YZ
=0+0+YZ
=YZ
We have derived NOT and AND. So f(X,Y,Z) is functionally complete.
g(X,Y,Z)=X'YZ+X'YZ'+XY
g(X,X,X)=X'XX+X'XZ'+XX
=0+0+X
=X
Similarly, g(Y,Y,Y)=Y and g(Z,Z,Z)=Z
NOT is not derived. Hence, g is not functionally complete.
 Question 76

 A 0.99 B 1 C 2 D 3
Engineering-Mathematics       Calculus       GATE 2015 (Set-01)
Question 76 Explanation:

=2-1/1(2)+3-2/2(3)+4-3/3(4)+…+100-99/99(100)
=1/1-1/2+1/2-1/3+1/3…+1/98-1/99+1/99-1/100
=1-1/100
=99/100
=0.99
 Question 77
Let R be the relation on the set of positive integers such that aRb if and only if a and b are distinct and have a common divisor other than 1. Which one of the following statements about R is true?
 A R is symmetric and reflexive but not transitive B R is reflexive but not symmetric and not transitive C R is transitive but not reflexive and not symmetric D R is symmetric but not reflexive and not transitive
Engineering-Mathematics       Set-Theory       GATE 2015 -(Set-2)
Question 77 Explanation:
Reflexive:
In aRb, 'a' and 'b' are distinct. So it can never be reflexive.
Symmetric:
In aRb, if 'a' and 'b' have common divisor other than 1, then bRa, i.e., 'b' and 'a' also will have common divisor other than 1. So, yes symmetric.
Transitive:
Take (3, 6) and (6, 2) elements of R. For transitivity (3, 2) must be the element of R, but 3 and 2 don't have a common divisor. So not transitive.
 Question 78
Consider the following statements:
 A If a person is known to corrupt, he is kind B If a person is not known to be corrupt, he is not kind C If a person is kind, he is not known to be corrupt D If a person is not kind, he is not known to be corrupt
Engineering-Mathematics       Prepositional-Logic       GATE 2015 -(Set-2)
Question 78 Explanation:
Let p: candidate known to be corrupt
q: candidate will be elected
r: candidate is kind
then S1=p→~q
=q→~p (conrapositive rule)
and S2:r→q⇒r→~p (transitive rule)
i.e., If a person is kind, he is not known to be corrupt ∴ Option is C
 Question 79
 A 6 B 7 C 8 D 9
Engineering-Mathematics       Linear-Algebra       GATE 2015 -(Set-2)
Question 79 Explanation:
Characteristic equation is |4-λ 5 2 1-λ |=0
⇒ λ2-5λ-6=0⇒(λ-6)(λ+1)=0⇒λ=6,-1
∴ Larger eigen value is 6
 Question 80
The cardinality of the power set of {0, 1, 2, … 10} is _________
 A 2046 B 2047 C 2048 D 2049
Engineering-Mathematics       Set-Theory       GATE 2015 -(Set-2)
Question 80 Explanation:
Cardinality of the power set of {0, 1, 2, … , 10} is 211 i.e., 2048.
 Question 81
The number of divisors of 2100 is ______.
 A 36 B 37 C 38 D 39
Engineering-Mathematics       Combinatorics       GATE 2015 -(Set-2)
Question 81 Explanation:
Let N = 2100
=22+3×52×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 82
In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?
 A A tree has no bridges B A bridge cannot be part of a simple cycle C Every edge of a clique with size 3 is a bridge (A clique is any complete sub graph of a graph) D A graph with bridges cannot have a cycle
Engineering-Mathematics       Graph-Theory       GATE 2015 -(Set-2)
Question 82 Explanation:
Since, every edge in a tree is bridge
∴ (A) is false
Since, every edge in a complete graph kn(n≥3) is not a bridge ⇒
(C) is false
Let us consider the following graph G:

This graph has a bridge i.e., edge ‘e’ and a cycle of length ‘3’
∴ (D) is false
Since, in a cycle every edge is not a bridge
∴ (B) is true
 Question 83
Consider six memory partitions of sizes 200 KB, 400 KB, 600 KB, 500 KB, 300 KB and 250 KB, where KB refers to kilobyte. These partitions need to be allotted to four processes of sizes 357 KB, 210KB, 468 KB and 491 KB in that order. If the best fit algorithm is used, which partitions are NOT allotted to any process?
 A 200KBand 300 KB B 200KBand 250 KB C 250KBand 300 KB D 300KBand 400 KB
Engineering-Mathematics       Memory-Management       GATE 2015 -(Set-2)
Question 83 Explanation:

Since Best fit algorithm is used. So, process of size,
357KB will occupy 400KB
210KB will occupy 250KB
468KB will occupy 500KB
491KB will occupy 600KB
So, partitions 200KB and 300KB are NOT alloted to any process.
 Question 84
The number of onto function (surjective function) from set X = {1, 2, 3, 4} to set Y = {a, b, c} is ______.
 A 36 B 37 C 38 D 39
Engineering-Mathematics       Relations-and-Functions       GATE 2015 -(Set-2)
Question 84 Explanation:
Number of onto function from set X to set Y with |X| = m, |Y| = n is

m = 4, n = 3 ⇒ number of onto function is
 Question 85
Perform the following operations on the matrix (i) add the third row to the second row (ii) Subtract the third column from the first column The determinant of the resultant matrix is ____________
 A 0 B 1 C 2 D 3
Engineering-Mathematics       Linear-Algebra       GATE 2015 -(Set-2)
Question 85 Explanation:

Method 2: Determinant is unaltered by the operations (i) and (ii)
∴ Determinant of the resultant matrix = Determinant of the given matrix

(Since C1,C3 are proportional i.e., C3=15C1)
 Question 86
Which one of the following well formed formulae is a tautology?
 A ∀x ∃y R(x,y)↔ ∃y ∀x R(x,y) B (∀x [∃y R(x,y)→S(x,y)])→ ∀x∃y S(x,y) C [∀x ∃y (P(x,y)→R(x,y)]↔[∀x ∃y ( ¬ P(x,y)∨R(x,y)] D ∀x ∀y P(x,y)→ ∀x ∀y P(y,x)
Engineering-Mathematics       Propositional-Logic       GATE 2015 -(Set-2)
Question 86 Explanation:
Since P→R=¬P∨R
[∀x ∃y (P(x,y)→R(x,y)]↔[∀x ∃y ( ¬ P(x,y)∨R(x,y)] is a tautology.
 Question 87
A graph is self-complementary if it is isomorphic to its complement for all self-complementary graphs on n vertices, n is
 A A multiple of 4 B Even C Odd D Congruent to 0 mod 4, or, 1 mod 4
Engineering-Mathematics       Graph-Theory       GATE 2015 -(Set-2)
Question 87 Explanation:
An n vertex self-complementary graph has exactly half number of edges of the complete graph i.e., n(n-1)/4 edges. Since n(n – 1) must be divisible by 4, n must be congruent to 0 or 1 module 4.
 Question 88
The secant method is used to find the root of an equation f(x) = o. It is started from the two distinct estimates xa and xb for the root. It is an iterative procedure involving linear interpolation ti a root. The iteratio stops if f(xb) is very small and then xb is the solutins. The procedure is given below. Observe that there is an expression which is missing and is marked by?.  WHich is the suitable expression that is to be put in place of ? so that it follows all steps of the secant method? end if
 A xb – (fb–f(xa))fb /(xb–xa) B xa – (fa–f(xa))fa /(xb–xa) C xb – (xb–xa)fb /(fb–f(xa)) D xa – (xb–xa) fa /(fb–f(xa))
Engineering-Mathematics       Secant-Method       GATE 2015 -(Set-2)
Question 88 Explanation:
The solution for this question is direct formula of secant method. In numerical analysis, the secant method is a root-finding algorithm that uses a succession of roots of secant lines to better approximate a root of a function f. The secant method can be thought of as a finite difference approximation of Newton's method. However, the method was developed independently of Newton's method, and predates it by over 3,000 years.
The first two iterations of the secant method. The red curve shows the function f and the blue lines are the secants. For this particular case, the secant method will not converge.
 Question 89
Let f(x) = x -1(1/3)  and A denote the area of the region bounded bu f(x) and rhe X-axis, when x varies from -1 to1. Which of the followin statements is/are TRUE? I) f is continuous in [-1,1] II)f is not bounded in [-1,1] III) A is nonzero and finite
 A II only B III only C II and III only D I, II and III
Engineering-Mathematics       Calculus       GATE 2015 -(Set-2)
Question 89 Explanation:
Since f(0)→∞
∴ f is not bounced in [-1, 1] and hence f is not continuous in [-1, 1].

∴ Statement II & III are true.
 Question 90
Let X and Y denote the sets containing 2 and 20 distinct objects respectively and F denote the set of all possible functions defined from X to YY. Let f be randomly chosen from F. The probability of f being one-to-one is ______.
 A 0.95 B 0.96 C 0.97 D 0.98
Engineering-Mathematics       Relations-and-Functions       GATE 2015 -(Set-2)
Question 90 Explanation:
|X| = 2, |Y| = 20
Number of functions from X to Y is 202 i.e., 400 and number of one-one functions from X to Y is 20P2 i.e., 20×19 = 380
∴ Probability of a function f being one-one is 380/400 i.e., 0.95
 Question 91

In a room there are only two types of people, namely Type 1 and Type 2. Type 1 people always tell the truth and Type 2 people always lie. You give a fair coin to a person in that room, without knowing which type he is from and tell him to toss it and hide the result from you till you ask for it. Upon asking, the person replies the following:

“The result of the toss is head if and only if I am telling the truth.”

Which of the following options is correct?

 A The result is head B The result is tail C If the person is of Type 2, then the result is tail D If the person is of Type 1, then the result is tail
Engineering-Mathematics       Prepositional-Logic       GATE 2015(Set-03)
Question 91 Explanation:
We do not know the type of person from whom those words are coming from and so we can have two cases.
Case 1:
The person who speaks truth. This definitely implies that result of toss is Head.
Case 2:
The person who lies. In this the reality will be the negation of the statement.
The negation of (x⇔y) is exactly one of x or y holds. "The result of the toss is head if and only if I am telling the truth". So here two possibilities are there,
→ It is head and lie spoken.
→ It is not head and truth spoken.
Clearly, the second one cannot speaks the truth. So finally it is head.
Hence, option (A).
 Question 92

Suppose U is the power set of the set S = {1, 2, 3, 4, 5, 6}. For any T ∈ U, let |T| denote the number of element in T and T' denote the complement of T. For any T, R ∈ U, let T \ R be the set of all elements in T which are not in R. Which one of the following is true?

 A ∀X ∈ U (|X| = |X'|) B ∃X ∈ U ∃Y ∈ U (|X| = 5, |Y| = 5 and X ∩ Y = ∅) C ∀X ∈ U ∀Y ∈ U (|X| = 2, |Y| = 3 and X \ Y = ∅) D ∀X ∈ U ∀Y ∈ U (X \ Y = Y' \ X')
Engineering-Mathematics       Set-Theory       GATE 2015(Set-03)
Question 92 Explanation:
As X and Y are elements of U, so X and Y are subsets of S.
(A) False. Consider X = {1,2}. Therefore, X' = {3,4,5,6}, |X| = 2 and |X'| = 4.
(B) False. Because for any two possible subsets of S with 5 elements should have atleast 4 elements in commonc. Hence X∩Y cannot be null.
(C) False. Consider X = {1,4}, Y= {1,2,3} then X\Y = {4} which is not null.
(D) True. Take any possible cases.
 Question 93
The number of 4 digit numbers having their digits in non-decreasing order (from left to right) constructed by using the digits belonging to the set {1, 2, 3} is _____ .
 A 15 B 16 C 17 D 18
Engineering-Mathematics       Combinatorics       GATE 2015(Set-03)
Question 93 Explanation:
Just try to write all the four digit numbers containing the digits 1, 2 and 3 only, in decreasing order.
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 4-digit no. are possible.
 Question 94
In the given matrix, one of the eigenvalues is 1. the eigenvectors corresponding to the eigenvalue 1 are
⎡ 1 -1  2 ⎤
⎢ 0  1  0 ⎥
⎣ 1  2  1 ⎦
 A {α(4,2,1) | α≠0, α∈R} B {α(-4,2,1) | α≠0, α∈R} C {α(2,0,1) | α≠0, α∈R} D {α(-2,0,1) | α≠0, α∈R}
Engineering-Mathematics       Linear-Algebra       GATE 2015(Set-03)
Question 94 Explanation:
X be an eigen vector corresponding to eigen value λ =1, then
AX = λX ⇒ (A - I)X = 0

⇒ -y+2z = 0 and x+2y = 0
⇒ y = 2z and x/(-2) = y
∴ x/(-2) = y = 2z ⇒ x/(-4) = y/2 = z/1 = α(say)

∴ Eigen vectors are {α(-4,2,1 | α≠0, α∈R}
 Question 95

Consider a machine with a byte addressable main memory of 220 bytes, block size of 16 bytes and a direct mapped cache having 212 cache lines. Let the addresses of two consecutive bytes in main memory be (E201F)16 and (E2020)16. What are the tag and cache line address (in hex) for main memory address (E201F)16?

 A E, 201 B F, 201 C E, E20 D 2, 01F
Engineering-Mathematics       Cache       GATE 2015(Set-03)
Question 95 Explanation:
Block size is of 16 bytes, so we need 4 offset bits. So the lowest 4 bit is offset bits.
ac No. of cache lines in cache is 212 bytes which needs 12 bits. So next lower 12 bits are line indexing bits.
And the remaining top 4 bits are tag bits (out of 20). So answer is (A).
 Question 96
If for non-zero x
 A B C D
Engineering-Mathematics       Calculus       GATE 2015(Set-03)
Question 96 Explanation:
Given,
af(x) + bf(1/x) = 1/x - 25 ------ (1)
Put x = 1/x,
af(1/x) + bf(x) = x - 25 ----- (2)
Multiply equation (1) with 'a' and Multiply equation (2) with 'b', then
abf(1/x) + a2 = a/x - 25a ----- (3)
abf(1/x) + b2 = bk - 25b ----- (4)
Subtract (3) - (4), we get
(a2 - b2) f(x) = a/x- 25a - bx + 25b
f(x) = 1/(a2 - b2) (a/x - 25a - bx +25b)
Now from equation,

Hence option (A) is the answer.
 Question 97
The velocity v (in kilometer/minute) of a motorbike which starts from rest, is given at fixed intervals of time t(in minutes) as follows:
t   2  4  6  8  10  12  14  16 18 20
v  10  18 25 29 32  20  11  5  2  0
The approximate distance (in kilometers) rounded to two places of decimals covered in 20 minutes using Simpson’s 1/3rd rule is _________.
 A 309.33 B 309.34 C 309.35 D 309.36
Engineering-Mathematics       Simpson\'s-1/3rd-rule       GATE 2015(Set-03)
Question 97 Explanation:
Let ‘S’ be the distance covered in 20 minutes, then by simpson’s 1/3rd rule,
∵v = velocity
= 2/3[(0+0)+4(10+25+32+11+2)+2(18+29+20+5)]
= 309.33 km
(Here length of each of the subinterval is h = 2)
 Question 98
If the following system has non-trivial solution,
  px + qy + rz = 0
qx + ry + pz = 0
rx + py + qz = 0
then which one of the following options is True?
 A p-q+r = 0 or p = q = -r B p+q-r = 0 or p = -q = r C p+q+r = 0 or p = q = r D p-q+r = 0 or p = -q = -r
Engineering-Mathematics       Linear-Algebra       GATE 2015(Set-03)
Question 98 Explanation:
For non-trivial solution the value of determinant should be zero.
 Question 99
Let R be a relation on the set of ordered pairs of positive integers such that ((p,q),(r,s)) ∈ R if and only if p - s = q - r. Which one of the following is true about R?
 A Both reflexive and symmetric B Reflexive but not symmetric C Not reflexive but symmetric D Neither reflexive nor symmetric
Engineering-Mathematics       Set-Theory       GATE 2015(Set-03)
Question 99 Explanation:
Since p-q ≠ q-p
∴(p,q) R (p,q)
⇒ R is not reflexive.
Let (p,q) R (r,s) then p-s = q-r
⇒ r-q = s-p
⇒ (r,s) R (p,q)
⇒ R is symmetric.
 Question 100
Let G = (V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G?
 A G1=(V,E1) where E1={(u,v)|(u,v)∉E} B G2=(V,E2 )where E2={(u,v)│(u,v)∈E} C G3=(V,E3) where E3={(u,v)|there is a path of length≤2 from u to v in E} D G4=(V4,E) where V4 is the set of vertices in G which are not isolated
Engineering-Mathematics       Graph-Theory       GATE 2014(Set-01)
Question 100 Explanation:
G(V, E) is a directed graph.
→ It strongly connected.
(A) G1=(V,E1) where E1={(u,v)|(u,v)∉E}
If (u, v) does not belong to the edge set ‘E’, then it indicates there are no edges. So, it is not connected.
(B) G2=(V,E2 )where E2={(u,v)│(u,v)∈E}
Given that ‘G’ is directed graph, i.e., it has path from each vertex to every other vertex.
Though direction is changed from (u, v) to (v, u), it is still connected component same as ‘G’.
(C) G3=(V,E3) where E3={(u,v)|there is a path of length≤2 from u to v in E}
This can also be true.
eg:

Both from each vertex to other vertex is also exists. So it is also strongly connected graph.
(D) G4=(V4,E) where V4 is the set of vertices in G which are not isolated.
If ‘G’ has same ‘x’ no. of isolated vertices, one strongly connected component
then no. of SCC = x + 1
G4 contain only ‘1’ component, which is not same as G.
 Question 101
The value of the dot product of the eigenvectors corresponding to any pair of different eigenvalues of a 4-by-4 symmetric positive definite matrix is _____________________.
 A 0 B 1 C 2 D 3
Engineering-Mathematics       Linear-Algebra       GATE 2014(Set-01)
Question 101 Explanation:
For real symmetric matrix, the eigen values are orthogonal to each other. So their dot product will be zero.
The finite dimensional spectral theorem says that any symmetric matrix whose entries are real can be diagonalized by an orthogonal matrix.
 Question 102
Let the function
 A I only B II only C Both I and II D Neither I nor II
Engineering-Mathematics       Calculus       GATE 2014(Set-01)
Question 102 Explanation:
Rolle’s theorem:
Rolle’s theorem states that for any continuous, differentiable function that has two equal values at two distinct points, the function must have a point on the function where the first derivative is zero. The technical way to state this is: if f is continuous and differentiable on a closed interval [a,b] and if f(a) = f(b), then f has a minimum of one value c in the open interval [a, b] so that f'(c) = 0.
We can observe that, sin, cos are continuous, but, Tan is not continuous at π/2. As the mentioned interval does not contain π/2, we can conclude that it is continuous.
As per Rolls theorem both statement 1 and statement 2 are true.
 Question 103
The function f(x) = x sinx satisfies the following equation: f ''(x) + f(x)+ tcosx = 0. The value of t is __________.
 A -2 B -3 C -4 D -5
Engineering-Mathematics       Calculus       GATE 2014(Set-01)
Question 103 Explanation:
f(x) = x Sinx
f ’(x) = x(Sinx)’ + Sin(x)(x’)
= xCosx + Sinx ---------①
f ’’(x) = x (Cosx)’ + Cos (x)’+ Cos x
= -x Sinx + 2Cosx -----------②
Given: f ’’(x) + f(x) + t Cosx = 0
Replace ① & ②,
-xSinx + 2Cosx + xSinx + tCosx = 0
2Cosx + tCosx = 0
t = -2
 Question 104
A function f(x) is continuous in the interval [0,2]. It is known that f(0) = f(2) = -1 and f(1) = 1. Which one of the following statements must be true?
 A There exists a y in the interval (0,1) such that f(y)=f(y+1) B For every y in the interval (0,1),f(y)=f(2-y) C The maximum value of the function in the interval (0,2) is 1 D There exists a y in the interval (0, 1) such that f(y)=-f(2-y)
Engineering-Mathematics       Calculus       GATE 2014(Set-01)
Question 104 Explanation:
Consider this function as sum of two functions as, g(y) = f(y) -f(y+1)
Since function f is continuous in [0, 2], therefore g would be continuous in [0, 1]
g(0) = -2, g(1) = 2
Since g is continuous and goes from negative to positive value in [0,1]. Therefore at some point g would be 0 in (0,1).
g=0 ⇒ f(y) = f(y+1) for some y in (0,1).
Apply similar logic to option D, Let g(y) = f(y) + f(2 - y)
Since function f is continuous in [0, 2], therefore g would be continuous in [0, 1] (sum of two continuous functions is continuous)
g(0) = -2, g(1) = 2
Since g is continuous and goes from negative to positive value in [0, 1]. Therefore at some point g would be 0 in (0, 1).
There exists y in the interval (0, 1) such that:
g=0 ⇒ f(y) = -f(2 – y)
 Question 105
Four fair six-sided dice are rolled. The probability that the sum of the results being 22 is X⁄1296. The value of X is ___________.
 A 10 B 11 C 12 D 13
Engineering-Mathematics       Probability       GATE 2014(Set-01)
Question 105 Explanation:
Each dice can result from {1, 2, 3, 4, 5, 6}
To get ‘22’ as Sum of four outcomes
x1 + x2 + x3 + x4 = 22
The maximum Sum = 6+6+6+6 = 24 which is near to 22
So, keeping three 6’s, 6+6+6+x = 22
x = 4 combination① = 6 6 6 4
Keeping two 6’s, 6+6+x1+x2 = 22
x1+x2 = 10 possible x’s (5, 5) only
combination② = 6 6 5 5
No. of permutation with 6664 = 4!/ 3! = 4
“ “ “ 6655 = 4!/ 2!2! = 6
Total = 4+6 = 10 ways out of 6×6×6×6 = 1296
Pnb (22) = 10/1296 ⇒ x = 10
 Question 106
A pennant is a sequence of numbers, each number being 1 or 2. An n-pennant is a sequence of numbers with sum equal to n. For example, (1,1,2) is a 4-pennant. The set of all possible 1-pennants is {(1)}, the set of all possible 2-pennants is {(2), (1,1)}and the set of all 3-pennants 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 10-pennants is ______________.
 A 89 B 90 C 91 D 92
Engineering-Mathematics       Combinatorics       GATE 2014(Set-01)
Question 106 Explanation:
No twos: 1111111111⇒ 1 pennant
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 107
Let S denote the set of all functions  f:{0,1}→ {0,1}. Denote by N the number of functions from S to the set {0,1}. The value of loglog2N is ______.
 A 16 B 17 C 18 D 19
Engineering-Mathematics       Relations-and-Functions       GATE 2014(Set-01)
Question 107 Explanation:
The number of functions from A to B where size of A=|A| and size of B=|B| is |B||A|
{0,1}4={0,1}×{0,1}×{0,1}×{0,1}=16
|S|=216
N=2|S|
loglogN=loglog2|S|=log |S| =log216=16
 Question 108
Consider an undirected graph where self-loops are not allowed. The vertex set of G is {(i,j): 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a,b) and (c,d) if |a - c| ≤ 1 and |b - d| ≤ 1. The number of edges in this graph is __________.
 A 506 B 507 C 508 D 509
Engineering-Mathematics       Graph-Theory       GATE 2014(Set-01)
Question 108 Explanation:
The total number of vertices in the graph is 12*12=144. The vertices are allowed to connect in both horizontal and vertical directions which are separated by at most 1 distance.
If we observe the graph, it looks like a 12 by 12 grid. Each corner vertex has a degree of 3 and we have 4 corner vertices. 40 external vertices of degree 5 and remaining 100 vertices of degree 8.
From Handshaking theorem, sum of the degrees of the vertices is equal to the 2*number of edges in the graph.
⇒ (4*3) + (40*5) + (100*8) = 2*E
⇒ 1012=2*E
⇒ E=506
 Question 109
An ordered -tuple (d1, d2, ..., dn) with d1 ≥ d2 ≥ ... dn is called graphic if there exists a simple undirected graph with n vertices having degrees d1, d2, ..., dn respectively. Which of the following 6-tuples is NOT graphic?
 A (1, 1, 1, 1, 1, 1) B (2, 2, 2, 2, 2, 2) C (3, 3, 3, 1, 0, 0) D (3, 2, 1, 1, 1, 0)
Engineering-Mathematics       Graph-Theory       GATE 2014(Set-01)
Question 109 Explanation:
This can be checked by Havel-hakimi theorem:
A) (1, 1, 1, 1, 1, 1)

Yes, it is a graph.
We will see that option (C) is not graphic.
 Question 110
Which one of the following propositional logic formulas is TRUE when exactly two of p, q, and r are TRUE?
 A ((p↔q)∧r)∨(p∧q∧∼r) B (∼(p↔q )∧r)∨(p∧q∧∼r) C ((p→q)∧r)∨(p∧q∧∼r) D (∼(p↔q)∧r)∧(p∧q∧∼r)
Engineering-Mathematics       Prepositional-Logic       GATE 2014(Set-01)
Question 110 Explanation:
Method 1: construct the tables for all options and check with T, T, F combinations.
Method2: directly check with one of {TTF, TFT, FTT} options.
As there are two T’s in each option, replace them and check with the third value.
Eg: Place p=q= T
(∼(p↔q)∧r)∨(p∧q∧∼r)
=(∼(T↔T)∧r)∨(T∧T∧∼r)
=(∼(T)∧r)∨(T∧∼r)
=(F∧r)∨(T∧∼r)
=(F)∨(∼r)
=∼r
This is true for r=F.
Similarly with p=r=T and q=F.
q=r=T and p=F
 Question 111
The security system at an IT office is composed of 10 computers of which exactly four are working. To check whether the system is functional, the officials inspect four of the computers picked at random (without replacement). The system is deemed functional if at least three of the four computers inspected are working.  Let the probability that the system is deemed functional be denoted by p. Then 100p =_____________.
 A 11.9 B 11.91 C 11.92 D 11.93
Engineering-Mathematics       Probability       Gate 2014 Set -02
Question 111 Explanation:
There are 10 systems.
Out of which ‘4’ are chosen at random without replaced and created.
If at least three of them are working then system is deemed functional
i.e., there should be only ‘one’ non-working system in set of ‘4’.
It is possible with combination
W – W – W – N,
W – W – N – W,
W – N – W – W,
N – W – W – W.
For W – W – W – N, the probability = (choosing working out of 10) × (choosing working out of 9) × (choosing working out of 8) × (choosing non-working out of 7)
=4/10×3/9×2/8×1/7
where 4/10 ⇒ 4 working out of 10
3/9 ⇒ 3 working are remaining out of ‘9’ as ‘1’ is already taken
For ‘4’ Sum combinations
Total probability =4×[4/10×3/9×2/8×1/7]=600/5040
We need 100p ⇒100×600/5040=11.90
 Question 112
Each of the nine words in the sentence "The quick brown fox jumps over the lazy dog" is written on a separate piece of paper. These nine pieces of paper are kept in a box. One of the pieces is drawn at random from the box. The expected length of the word drawn is _____________. (The answer should be rounded to one decimal place.)
 A 3.9 B 4 C 4.1 D 4.2
Engineering-Mathematics       Probability       Gate 2014 Set -02
Question 112 Explanation:
"The quick brown fox jumps over the lazy dog"
There are ‘9’ words in this sentence.
No. of characters in each word
The (3)
quick (5)
brown (5)
fox (3)
jumps (5)
over (4)
the (3)
lazy (4)
dog (3)
Each word has equal probability.
So expected length = 3×1/9+5×1/9+5×1/9+3×1/9+5×1/9+ 4×1/9+3×1/9+4×1/9+3×1/9
=35/9
=3.9
 Question 113
The maximum number of edges in a bipartite graph on 12 vertices is ______.
 A 36 B 37 C 38 D 39
Engineering-Mathematics       Graph-Theory       Gate 2014 Set -02
Question 113 Explanation:
Max. no. of edges possible in bipartite graph, only if vertices are equal in each set i.e., 12/2 = 6 in each set.

Total no. of edges = 6×6 = 36
 Question 114
 A 0 B 1 C 2 D 3
Engineering-Mathematics       Linear-Algebra       Gate 2014 Set -02
Question 114 Explanation:
 Question 115
A non-zero polynomial f(x) of degree 3 has roots at x = 1, x = 2 and x = 3.  Which one of the following must be TRUE?
 A f(0)f(4) < 0 B f(0)f(4) > 0 C f(0) + f(4) > 0 D f(0) + f(4) < 0
Engineering-Mathematics       Calculus       Gate 2014 Set -02
Question 115 Explanation:
Roots of polynomial of degree ‘3’ are 1, 2, 3
Polynomial will be
f(x) = (x-1)(x-2)(x-3)
f(0) = -1 × -2 × -3 = -6
f(4) = 3 × 2 × 1 = 6
f(0)∙f(4) = - 36
f(0) + f(4) = 6 - 6 = 0
Option (A) is correct.
 Question 116
In the Newton-Raphson method, an initial guess of x0 = 2 is made and the sequence x0, x1, x2 … is obtained for the function
0.75x3 – 2x2 – 2x + 4 = 0

Consider the statements
(I) x3 = 0.
(II) The method converges to a solution in a finite number of iterations.
Which of the following is TRUE?
 A Only I B Only II C Both I and II D Neither I nor II
Engineering-Mathematics       Newton-Raphson-Method       Gate 2014 Set -02
Question 116 Explanation:
Note: Numerical methods are not in GATE CS syllabus.
 Question 117
The product of the non-zero eigenvalues of the matrix
1 0 0 0 1
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
1 0 0 0 1
is ______
 A 6 B 7 C 8 D 9
Engineering-Mathematics       Linear-Algebra       Gate 2014 Set -02
Question 117 Explanation:
Characteristic equation for matrix ‘A’ is
AX = λX

x1 + x5 = λx1 ---------- (1)
x1 + x5 = λx5 ---------- (2)
(1) + (2) ⇒ 2(x1 + x5) = λ(x1 + x5) ⇒ λ1 = 2
x2 + x3 + x4 = λ∙x2 -------- (4)
x2 + x3 + x4 = λ∙x3 -------- (5)
x2 + x3 + x4 = λ∙x4 -------- (6)
(4)+(5)+(6) = 3(x2 + x3 + x4) = λ(x2 + x3 + x4 ) ⇒ λ2 =3
Product = λ1 × λ2 = 2×3 = 6
 Question 118
The probability that a given positive integer lying between 1 and 100 (both inclusive) is NOT divisible by 2, 3 or 5 is ______ .
 A 0.259 to 0.261 B 0.260 to 0.262 C 0.261 to 0.263 D 0.262 to 0.264
Engineering-Mathematics       Probability       Gate 2014 Set -02
Question 118 Explanation:
Let A = divisible by 2, B = divisible by 3 and C = divisible by 5, then
n(A)=50, n(B)=33, n(C)=20
n(A∩B)=16, n(B∩C)=6, n(A∩C)=10
n(A∩B∩C)=3
P(A∪B∪C)=P(A)+P(B)+P(C)-P(A∩B)-P(B∩C) -P(A∩C)+P(A∩B∩C)=74/100
∴ Required probability is P(A∩B∩C)=1-P(A∪B∪C)=0.26
 Question 119
The number of distinct positive integral factors of 2014 is _________
 A 0.26 B 0.27 C 8 D 0.29
Engineering-Mathematics       Combinatorics       Gate 2014 Set -02
Question 119 Explanation:
First lets find prime factorization of 2014
= 2' × 19' × 53'
Now number of distinct integral factors of 2014 will be,
(1+1)×(1+1)×(1+1) = 2×2×2 = 8
 Question 120
Consider the following relation on subsets of the set S of integers between 1 and 2014. For two distinct subsets U and V of S we say U < V if the minimum element in the symmetric difference of the two sets is in U. Consider the following two statements:
S1: There is a subset of S that is larger than every other subset.
S2: There is a subset of S that is smaller than every other subset.
Which one of the following is CORRECT?
 A Both S1 and S2 are true B S1 is true and S2 is false C S2 is true and S1 is false D Neither S1 nor S2 is true
Engineering-Mathematics       Set-Theory       Gate 2014 Set -02
Question 120 Explanation:
Given: S = {1, 2, 3, …, 2014}
U⊂S, V⊂S
Let U = {1, 2, 3}
V = {2, 3, 4}
Symmetric difference:
(U – V) ∪ (V – U) = {1} ∪ {4} = {1, 4}
The minimum element in the symmetric difference is 1 and 1∈U.
S1: Let S = Universal set = {1, 2, … 2014}
This universal set is larger than every other subset.
S2: Null set is smaller than every other set.
Let U = { }, V = {1}
Symmetric difference = ({ } – {1}) ∪ ({1} – { }) = { } ∪ {1} = {1}
So, U < V because { } ∈ U.
 Question 121
A cycle on n vertices is isomorphic to its complement. The value of n is _____.
 A 5 B 6 C 7 D 8
Engineering-Mathematics       Graph-Theory       Gate 2014 Set -02
Question 121 Explanation:
Complement of a graph means, we need to remove the existing edges from the graph and place the new edges which were not earlier among the actual graph.
In a cycle of n vertices, each vertex is connected to other two vertices. So each vertex degree is 2.
When we complement it, each vertex will be connected to remaining n-3 vertices ( one is self and two other vertices in actual graph).
As per given question,
n-3 =2
n=5
Cycle of 5 vertices is

Complement of the above graph1 is

Graph1 and Graph2 are complement each other.
So, the value of n is 5.
 Question 122
Which one of the following Boolean expressions is NOT a tautology?
 A ((a ⟶ b) ∧ (b ⟶ c)) ⟶ (a ⟶ c) B (a ⟷ c) ⟶ (∽ b ⟶ (a ∧ c)) C (a ∧ b ∧ c) ⟶ (c ∨ a) D a ⟶ (b ⟶ a)
Engineering-Mathematics       Prepositional-Logic       Gate 2014 Set -02
Question 122 Explanation:
A:
((a → b) ∧ (b → c)) → (a → c)
If (a → b) is false with a = T, b = F,
then (F ∧ (b → c)) → (a → c)
F → (a → c)
which is True for any (a → c)
This is tautology.
B:
(a ⟷ c) ⟶ (∽b ⟶ (a ∧ c))
For (a ⟷ c) be True and
∽b → (a ∧ c) should be False
Let a = c = F
(F → F) → (∽b (F ∩ F))
T → (∽b → F)
This is False for b = F
So, this is not True.
C:
(a ∧ b ∧ c) ⟶ (c ∨ a)
(c ∨ a) is False only for a = c = F
if (c ∨ a) is False
(F ∧ b ∧ F) → F
F → F which is Tautology
True always.
D:
a ⟶ (b ⟶ a)
a ⟶ (~b ∨ a)
(~a ∨ a) ∨ ~b = T ∨ ~b = T which is tautology
 Question 123
Consider the following statements: P:Good mobile phones are not cheap Q:Cheap mobile phones are not good L:P implies Q M:Q implies P N:P is equivalent to Q Which one of the following about L, M, and N is CORRECT?
 A Only L is TRUE. B Only M is TRUE. C Only N is TRUE. D L, M and N are TRUE.
Engineering-Mathematics       Prepositional-Logic       Gate 2014 Set -03
Question 123 Explanation:
In the given statements observe that "not cheap" & cheap, "good & not good" are used.
So, given statement can be sub divided such that we can utilize the negation of this atomic statements.
Suppose, X is Good mobile and Y is cheap then
P: (Good(x) → ~cheap(x)) → (~good(x) ∨ ~cheap(x))
Q: cheap(x) → ¬good(x) ⟺ ((¬cheap(x) ∨ good(x)) ⟺ ¬good(x) ∨ ¬cheap(x))
All these are contra positive.
All L, M, N are true.
 Question 124
Let X and Y be finite sets and f: X→Y be a function. Which one of the following statements is TRUE?
 A For any subsets A and B of X, |f(A ∪ B)| = |f(A)|+|f(B)| B For any subsets A and B of X, f(A ∩ B) = f(A) ∩ f(B) C For any subsets A and B of X, |f(A ∩ B)| = min{ |f(A)|,f|(B)|} D For any subsets S and T of Y, f -1 (S ∩ T) = f -1 (S) ∩ f -1 (T)
Engineering-Mathematics       Set-Theory       Gate 2014 Set -03
Question 124 Explanation:
The function f: x→y.
We need to consider subsets of 'x', which are A & B (A, B can have common elements are exclusive).
Similarly S, T are subsets of 'y'.

To be a function, each element should be mapped with only one element.
(a) |f(A∪B)|=|f(A)|+|f(B)|
|{a,b,c}|∪|{c,d,e}| = |{a,b,c}| + |{c,d,e}|
|{a,b,c,d,e}| = 3+3
5 = 6 FALSE
(d) To get inverse, the function should be one-one & onto.
The above diagram fulfills it. So we can proceed with inverse.
f-1 (S∩T )=f-1 (S)∩f-1 (T)
f-1 (c)=f-1 ({a,b,c})∩f-1 ({c,d,e})
2={1,2,3}∩{2,4,5}
2=2 TRUE
 Question 125
Let G be a group with 15 elements. Let L be a subgroup of G. It is known that L ≠ G and that the size of L is at least 4.  The size of L  is __________.
 A 5 B 6 C 7 D 8
Engineering-Mathematics       Set-Theory       Gate 2014 Set -03
Question 125 Explanation:
Lagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order (number of elements) of every subgroup H of G divides the order of G.
So, 15 is divided by {1, 3, 5, 15}.
As minimum is 4 and total is 15, we eliminate 1,3,15.
 Question 126
Which one of the following statements is TRUE about every n × n matrix with only real eigenvalues?
 A If the trace of the matrix is positive and the determinant of the matrix is negative, at least one of its eigenvalues is negative. B If the trace of the matrix is positive, all its eigenvalues are positive. C If the determinant of the matrix is positive, all its eigenvalues are positive. D If the product of the trace and determinant of the matrix is positive, all its eigenvalues are positive.
Engineering-Mathematics       Linear-Algebra       Gate 2014 Set -03
Question 126 Explanation:
The sum of the n eigenvalues of A is the same as the trace of A (that is, the sum of the diagonal elements of A).
• The product of the n eigenvalues of A is the same as the determinant of A. •
A: Yes, for sum to be negative there should be atleast one negative number.
B: There can be one small negative number and remaining positive, where sum is positive.
C: Product of two negative numbers is positive. So, there no need of all positive eigen values.
D: There is no need for all eigen values to be positive, as product of two negative numbers is positive.
 Question 127
If V1 and V2 are 4-dimensional subspaces of a 6-dimensional vector space V, then the smallest possible dimension of V1∩V2   is ______.
 A 2 B 3 C 4 D 5
Engineering-Mathematics       Set-Theory       Gate 2014 Set -03
Question 127 Explanation:
In a 6 dimensional vector space, sub space of 4 dimensional subspaces V1, V2 are provided. Then the V1∩V2?
For eg: a two dimensional vector space have x, y axis. For dimensional vector space, it have x, y, z axis.
In the same manner, 6 dimensional vector space has x, y, z, p, q, r (assume).
Any subspace of it, with 4 dimensional subspace consists any 4 of the above. Then their intersection will be atmost 2.
[{x,y,z,p} ∩ {r,q,p,z}] = #2
V1 ∩ V2 = V1 + V2 - V1 ∪ V2 = 4+4+(-6) = 2
 Question 128
 A 4 B 5 C 6 D 7
Engineering-Mathematics       Calculus       Gate 2014 Set -03
Question 128 Explanation:
The graph x.Sinx from 0 to 2π is

We have |xSinx|,

We can observe that it is positive from 0 to π and negative in π to 2π.
To get positive value from π to 2π we put ‘-‘ sign in the (π, 2π)
 Question 129
With respect to the numeri cal evaluation of the defi nite integral where a  and b are given, which of the followi ng statements is/are  TRUE? I) Th e value of obtained us ing the trapezoidal rule i s always greater than or equal to the exact value of the definite integral. II) Th e value of obtained using the Sim pson’s rule is always equ al to the ex act value of the definite inte gral.
 A I only B II only C Both I and II D Neither I nor II
Engineering-Mathematics       Calculus       Gate 2014 Set -03
Question 129 Explanation:
Note: Numerical methods are out of syllabus for the GATE -CS.
 Question 130
the value of the integral given below is
 A -2π B π C -π D 2π
Engineering-Mathematics       Calculus       Gate 2014 Set -03
Question 130 Explanation:
 Question 131
Let S be a sample space and two mutually exclusive events A and B be such that A∪B = S. If P(∙) denotes the probability of the event, the maximum value of P(A)P(B) is __________.
 A 0.25 B 0.26 C 0.27 D 0.28
Engineering-Mathematics       Probability       Gate 2014 Set -03
Question 131 Explanation:
We know that
P(A∪B) = P(A) + P(B) + P(A∩B) = 1 →①
But, as A and B are mutually exclusive events
P(A∩B) = 0
∴ P(A∪B) = P(A) + P(B) = 1 →②
Arithmetic mean of two numbers ≥ Geometric mean of those two numbers
(P(A)+P(B))/2≥√(P(A)∙P(B))
1/2≥√(P(A)∙P(B)) (∵from ②)
Squaring on both sides
1/4≥P(A)∙P(B)
P(A)∙P(B)≤1/4
∴ Maximum value of P(A)P(B) = 1/4 = 0.25
 Question 132
There are two elements , in a group ( ,∗) such that every element in the group can be written as a product of some number of x's and 's in some order. It is known that x*x=y*y=x*y*x=y*x*y*x=e where    is the identity element. The maximum number of elements in such a group is
 A 4 B 5 C 6 D 7
Engineering-Mathematics       Graph-Theory       Gate 2014 Set -03
Question 132 Explanation:
We know
a*a-1 = e

1. x*x=e So x-1 is x ⇒ x is element of Group
2. y*y=e So y-1 = y ⇒ y is element of Group

4. (y*x)*(y*x)=x*y*y*x=x*x*e=e So (y*x)-1=(y*x)
In ③, ④
x*y,y*x has same inverse, there should be unique inverse for each element.
x*y=y*x (even with cumulative law, we can conclude)
So {x, y, e, x*y} are element of Group.
 Question 133
 A P, Q and R are true B Only Q and R are true C Only P and Q are true D Only R is true
Engineering-Mathematics       Set-Theory       Gate 2014 Set -03
Question 133 Explanation:
f:{0,1,…,2014}→{0,1,…,2014} and f(f(i))=i

So f(i)should be resulting only {0, 1, …2014}
So, every element in range has a result value to domain. This is onto. (Option R is correct)
We have ‘2015’ elements in domain.
So atleast one element can have f(i) = i,
so option ‘Q’ is also True.
∴ Q, R are correct.
 Question 134
If G is a forest with n vertices and k connected components, how many edges does G have?
 A ⌊n/k⌋ B ⌈n/k⌉ C n–k D n-k+1
Engineering-Mathematics       Graph-Theory       Gate 2014 Set -03
Question 134 Explanation:
Suppose, if each vertex is a component, then k=n, then there will not be any edges among them Replace the same in options
Option 1, 2 will give answer 1. (i.e. one edge among them),
Option 3: n-k = 0 edges.
Option 4: n-k+1 : 1edge, which is false.
 Question 135
Let δ denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with δ ≥ 3, which one of the following is TRUE?
 A In any planar embedding, the number of faces is at least n/2+ 2 B In any planar embedding, the number of faces is less than n/2+ 2 C There is a planar embedding in which the number of faces is less than n/2+ 2 D There is a planar embedding in which the number of faces is at most n/(δ+1)
Engineering-Mathematics       Set-Theory       Gate 2014 Set -03
Question 135 Explanation:
Euler’s formula:
v – e + f = 2 →①
Point ① degree of each vertex is minimum ‘3’.

3×n≥2e
e≤3n/2
From ①
n-3n/2+f=2⇒
 Question 136
The CORRECT formula for the sentence, “not all rainy days are cold” is
 A ∀d (Rainy(d) ∧∼Cold(d)) B ∀d (∼Rainy(d) → Cold(d)) C ∃d (∼Rainy(d) → Cold(d)) D ∃d (Rainy(d) ∧∼Cold(d))
Engineering-Mathematics       Prepositional-Logic       Gate 2014 Set -03
Question 136 Explanation:
Not all rainy days are cold
= ∼[∀rainy days are cold]
= ∼[∀ days (rainy days ⇒ cold days]
= ∃ days[∼(cold days ∨ ∼rainy days)]
= ∃ days[rainy days ∧ ∼cold days]
 Question 137
A binary operation ⊕ on a set of integers is defined as x ⊕ y = x+ y2. Which one of the following statements is TRUE about ⊕?
 A Commutative but not associative B Both commutative and associative C Associative but not commutative D Neither commutative nor associative
Engineering-Mathematics       Set-Theory       Gate 2013
Question 137 Explanation:
Cumulative property:
A binary relation on a set S is called cumulative if a*b = b*a ∀ x,y∈S.
Associative property:
A binary relation on set is called associative if (a*b)*c = a*(b*c) ∀ x,y∈S.
Given x⊕y = x2 + y2 --------(1)
Replace x, y in (1)
y⊕x = y2 + x2 which is same as (1), so this is cumulative
(x⊕y)⊕z = (x2 + y2) ⊕ z
= (x2 + y2) + z2
= x2 + y2 + z2 + 2x2y2 ----------(2)
x⊕(y ⊕ z) = x ⊕ (y2 + z2)
= x2 + (y2 + z2)2
= x2 + y2 + z2 + 2y2z2 ----------- (3)
(2) & (3) are not same so this is not associative.
 Question 138
Suppose p is the number of cars per minute passing through a certain road junction between 5 PM and 6 PM, and p has a Poisson distribution with mean 3. What is the probability of observing fewer than 3 cars during any given minute in this interval?
 A 8/(2e3) B 9/(2e3) C 17/(2e3) D 26/(2e3)
Engineering-Mathematics       Probability       Gate 2013
Question 138 Explanation:
The formula for the Poisson probability mean function
P(x:λ)=(e λx)/x! for x = 0,1,2….
‘λ’ is the average number (mean)
Given that mean = λ = 3
The probability of observing fewer than three cars is
P(zero car) + P(one car) + P(two cars)
=(e-3 30)/0!+(e-3 31)/1!+(e-3 32)/2!
=e-3+e-3∙3+(e-3)∙9)/2
=(17e-3<)/2
=17/(2e3 )
 Question 139
Which one of the following does NOT equal to
 A B C D
Engineering-Mathematics       Linear-Algebra       Gate 2013
Question 139 Explanation:

Try to derive options from the given matrix.
Observe that col 2 + col 3 will reuse x(x+1) term
C2 → C1 + C2

 Question 140
Which one of the following functions is continuous at x = 3?
 A B C D
Engineering-Mathematics       Number-System-and-Calculus       Gate 2013
Question 140 Explanation:
Option A:
At x = 3, f(x) = 2
LHL (3), f(3- )=(x+3 )/3=(3+3)/3=2
RHL (3), f(3+ )=x-1=3-1=2
∴ f(x) is continuous.
Option B:
At x = 3, f(x) = 4
For x ≠ 3, f(x)=f(3+ )=f(3- )=8-x=8-3=5
This is not continuous.
Option C:
At x ≤ 3, f(x) = x+3 = 3+3 = 6
At RHL(3), f(3+ )=4
This is not continuous.
Option D:
f(x) at x=3 is not defined.
There is a break at x=3, so this is not continuous.
 Question 141
Function f is known at the following points:
 A 8.983 B 9.003 C 9.017 D 9.045
Engineering-Mathematics       Number-System-and-Calculus       Gate 2013
Question 141 Explanation:
Note: Numerical methods are not in GATE syllabus now.
 Question 142
What is the logical translation of the following statement?
  "None of my friends are perfect."
 A ∃x(F(x)∧¬P(x)) B ∃x(¬F(x)∧P(x)) C ∃x(¬F(x)∧¬P(x)) D ¬∃x(F(x)∧P(x))
Engineering-Mathematics       Prepositional-Logic       Gate 2013
Question 142 Explanation:
Let F(x) = x is my friend
P(x) = x is perfect
The meaning of ∃x(P(x)∧F(x)) is atleast one person who is my friend and perfect.
The negation of ∃x(P(x)∧F(x)) is “This is not the case that atlease one person who is my friend and perfect”.
So ~∃x(P(x)∧F(x)) is none of my friends are perfect.
 Question 143
The following code segment is excuted on a process which allows only register operands in its instructuoins. Each instructions can have atmost two sources operands and one destination opernad. Assume that all variables are dead after this code segement
 A 0 B 1 C 2 D 3
Engineering-Mathematics       Prepositional-Logic       Gate 2013
Question 143 Explanation:
After applying the code motion optimization the statement d = c*a; and e = c+a; can be moved down to else block as d and c are not used anywhere before that and also value of a and c is not changing.

In the above code total number of spills to memory is 1.
 Question 144
Consider the following logical inferences.
I1: If it rains then the cricket match will not be played.
The cricket match was played.
Inference: There was no rain.
I2: If it rains then the cricket match will not be played.
It did not rain.
Inference: The cricket match was played.
Which of the following is TRUE?
 A Both I1 and I2 are correct inferences B I1 is correct but I2 is not a correct inference C I1 is not correct but I2 is a correct inference D Both I1 and I2 are not correct inferences
Engineering-Mathematics       Propositional-Logic       Gate 2012
Question 144 Explanation:
I1: If it rains then the cricket match will not be played.
The cricket match was played.
Let p = it rains
q = playing cricket/ match played
If (it rains) then (the match will not be played)
p ⇒ (∼q)
Inference: There was no rain. (i.e., p = F)
So for any F ⇒ (∼q) is true.
So this inference is valid.
I2: If it rains then the cricket match will not be played.
It did not rain.
p ⇒ (∼q)
Inference: The cricket match was played.
q = T
p ⇒ (∼q)
p ⇒ (∼T)
p ⇒ F
This is false for p = T, so this is not true.
 Question 145
Consider the function f(x) = sin(x) in the interval x ∈ [π/4, 7π/4]. The number and location(s) of the local minima of this function are
 A One, at π/2 B One, at 3π/2 C Two, at π/2 and 3π/2 D Two, at π/4 and 3π/2
Engineering-Mathematics       Calculus       Gate 2012
Question 145 Explanation:
f(x) = sin x
f’(x) = cos x

[just consider the given interval (π/4, 7π/4)]
f'(x) = 0 at π/2, 3π/2
To get local minima f ’’(x) > 0, f ’’(x) = - sin x
f ’’(x) at π/2, 3π/2
f ’’(x) = -1< 0 local maxima
f ’’ (3π/2) = 1 > 0 this is local minima
In the interval [π/4, π/2] the f(x) is increasing, so f(x) at π/4 is also a local minima.
So there are two local minima for f(x) at π/4, 3π/2.
 Question 146
Let  be the 2×2 matrix with elements a11 = a12 = a21 = +1 and a22 = -1. Then the eigenvalues of the matrix A19 are
 A 1024 and -1024 B 1024√2 and -1024√2 C 4√2 and -4√2 D 512√2 and -512√2
Engineering-Mathematics       Linear-Algebra       Gate 2012
Question 146 Explanation:
a11=a12=a21=1, a22=-1
The 2×2 matrix =
Cayley Hamilton theorem:
If matrix A has ‘λ’ as eigen value, An has eigen value as λn.
Eigen value of
|A-λI| = 0

-(1-λ)(1+λ)-1=0
-(1-λ2 )-1=0
-1=1-λ2
λ2=2
λ=±√2
A19 has (√2)19=29×√2 (or) (-√2)19=-512√2
=512√2
 Question 147
 A ∃x (real(x) ∨ rational(x)) B ∀x (real(x) → rational(x)) C ∃x (real(x) ∧ rational(x)) D ∃x (rational(x) → real(x))
Engineering-Mathematics       Propositional-Logic       Gate 2012
Question 147 Explanation:

∃x (real(x) ∧ rational(x))
(A) ∃x(real(x) ∨ rational(x))
means There exists some number, which are either real or rational.
(B) ∀x (real(x)→rational(x))
If a number is real then it is rational.
(D) ∃x (rational(x)→real(x))
There exists a number such that if it is rational then it is real.
 Question 148
Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to
 A 3 B 4 C 5 D 6
Engineering-Mathematics       Graph-Theory       Gate 2012
Question 148 Explanation:
If the graph is planar, then we have to consider Euler’s formula
v-e+f=2
Given 10 vertices & 15 edges
10-15+f=2
f=2+15-10
f=7
There will be an unbounded face always. So, number of faces = 6.
 Question 149
Consider a random variable X that takes values +1 and −1 with probability 0.5 each. The values of the cumulative distribution function F(x) at x = −1 and +1 are
 A 0 and 0.5 B 0 and 1 C 0.5 and 1 D 0.25 and 0.75
Engineering-Mathematics       Probability       Gate 2012
Question 149 Explanation:
Cumulative probability is sum of probabilities of all other points till the given value.
The sum of probabilities at x=1, x=-1 itself is 0.5+0.5 =1. It is evident that, there is no probability for any other values.
The F(x=-1) is 0.5 as per given probabilities and
F(x=1) = sum of F(x=-1) +F(x=0)=...f(X=1) = 0.5 +0.5 =1
 Question 150
Which of the following graphs is isomorphic to
 A B C D
Engineering-Mathematics       Graph-Theory       Gate 2012
Question 150 Explanation:
Original graph:

(A) 3 cycle graph not in original one.

(B) Correct 5 cycles & max degree is 4.
(C) Original graph doesn’t have a degree of 3.

(D) 4 cycles not in original one.
 Question 151
The bisection method is applied to compute a zero of the function f(x) = x4 - x3 - x2 - 4 in the interval [1,9]. The method converges to a solution after ________ iterations.
 A 1 B 3 C 5 D 7
Engineering-Mathematics       Numerical-Methods       Gate 2012
Question 151 Explanation:
Note: Numerical methods are not present in the GATE CS syllabus anymore.
 Question 152
Suppose a fair six-sided die is rolled once. If the value on the die is 1, 2, or 3, the die is rolled a second time. What is the probability that the sum total of values that turn up is at least 6?
 A 10/21 B 5/12 C 2/3 D 1/6
Engineering-Mathematics       Probability       Gate 2012
Question 152 Explanation:
The value on the die for first time rolling= {1, 2, 3}
The value on second time can be {1, 2, 3, 4, 5, 6}
So the Sum can be

We have Sample space = 36
The no. of events where (Sum = atleast 6) = {6, 7, 6, 7, 8, 6, 7, 8, 9}
So the probability atleast ‘6’ while getting {1, 2, 3} in first time = 9/36 → ①
If we get ‘6’ in the first time itself, then we do not go for rolling die again.
So, its probability = 1/6
Total probability = 1/6 + 9/36 = 1/6 + 1/4 = 10/24 = 5/12
 Question 153
How many onto (or surjective) functions are there from an n-element (n ≥ 2) set to a 2-element set?
 A 2n B 2n-1 C 2n-2 D 2(2n– 2)
Engineering-Mathematics       Functions       Gate 2012
Question 153 Explanation:

Onto function is possible if m ≥ n. So, no. of onto functions possible is,
nm - nC1 (n-1)m + nC2 (n-2)m + .......
Here in Question,
m = n, n = 2
So, the final answer will be,
= 2n - 2C1 (2-1)n + 2C2 (2-2)n
= 2n - 2 × 1 + 0
= 2n - 2
 Question 154
Let G be a complete undirected graph on 6 vertices. If vertices of G are labeled, then the number of distinct cycles of length 4 in G is equal to
 A 15 B 30 C 45 D 360
Engineering-Mathematics       Graph-Theory       Gate 2012
Question 154 Explanation:
Complete graph means there exists an edge between every pair of vertices.
It is asked to find the distinct cycle of length 4. As it is complete graph, if we chose any two vertices, there will be an edge.
So, to get a cycle of length 4 (means selecting the 4 edges which can form a cycle) we can select any four vertices.
The number of such selection of 4 vertices from 6 vertices is 6C4 => 15.
From each set of 4 vertices, suppose a set {a, b, c, d} we can have cycles like
a-b-c-d
a-b-d-c
a-c-b-d
a-c-d-b
a-d-b-c
a-d-c-b (Total 6, which is equal to number of cyclic permutations (n-1)! )
As they are labelled you can observe, a-b-c-d and a-d-c-b are same, in different directions.
So, we get only three combinations from the above 6.
So, total number of distinct cycles of length 4 will be 15*3 = 45.
If it is asked about just number of cycles then 15*6 = 90
 Question 155
If the difference between the expectation of the square of a random variable (E[X2]) and the square of the expectation of the random variable (E[X])2 is denoted by R, then
 A R = 0 B R < 0 C R ≥ 0 D R > 0
Engineering-Mathematics       Probability       Gate 2011
Question 155 Explanation:
We know that difference of E(X2) and E(X))2 is nothing but variance or V(X) which is always greater than or equal to zero.
So the answer will be R≥0.
 Question 156
Consider the matrix as given below. Which one of the following provides the CORRECT values of eigenvalues of the matrix?
 A 1, 4, 3 B 3, 7, 3 C 7, 3, 2 D 1, 2, 3
Engineering-Mathematics       Linear-Algebra       Gate 2011
Question 156 Explanation:
Given matrix is upper triangular matrix and its diagonal elements are its eigen values = 1, 4, 3
 Question 157
Which one of the following options is CORRECT given three positive integers x,y and z, and a predicate
 A P(x) being true means that x is a prime number B P(x) being true means that x is a number other than 1 C P(x) is always true irrespective of the value of x D P(x) being true means that x has exactly two factors other than 1 and x
Engineering-Mathematics       Propositional-Logic       Gate 2011
Question 157 Explanation:
Statement: x is not equal to 1 and if there exists some z for all y such that product of y and z is x, then y is either the no. itselfor 1.
This is the definition of prime nos.
 Question 158

 A 0 B 2 C –i D i
Engineering-Mathematics       Calculus       Gate 2011
Question 158 Explanation:
We know that,
 Question 159
Consider a finite sequence of random values X = [x1, x2, …, xn]. Let μx be the mean and σx be the standard deviation of X. Let another finite sequence Y of equal length be derived from this as yi = a * xi + b, where a and b are positive constants. Let μy be the mean and σy be the standard deviation of this sequence. Which one of the following statements is INCORRECT?
 A Index position of mode of X in X is the same as the index position of mode of Y in Y. B Index position of median of X in X is the same as the index position of median of Y in Y. C μy = aμx + b D σy = aσx + b
Engineering-Mathematics       Probability-and-Statistics       Gate 2011
Question 159 Explanation:
σy is standard deviation then
y)2 is variance so,
yi = a * xi + b
y)2 = a2 x)2
⇒ σy = a σx
Hence option (D) is incorrect.
 Question 160
A deck of 5 cards (each carrying a distinct number from 1 to 5) is shuffled thoroughly. Two cards are then removed one at a time from the deck. What is the probability that the two cards are selected with the number on the first card being one higher than the number on the second.
 A 1/5 B 4/25 C 1/4 D 2/5
Engineering-Mathematics       Probability       Gate 2011
Question 160 Explanation:
The possible events are
(2,1) (3,2) (4,3) (5,4).
So only 4 possibilities are there and sample space will be,
5C1 × 4C1 = 20
So probability = 4/20 = 1/5
 Question 161
Let G = (V,E) be a graph. Define ξ(G) = Σd id x d, where id is the number of vertices of degree d in G. If S and T are two different trees with ξ(S) = ξ(T),then
 A |S| = 2|T| B |S| = |T| - 1 C |S| = |T| D |S| = |T| + 1
Engineering-Mathematics       Graph-Theory       2010
Question 161 Explanation:

id= no. of vertices of degree ‘d’ in ‘G’
Eg:

No. of vertices with degree ‘2’ = 3
ξ(G')=3×2='6' i.e., sum of degrees
By Handshaking Theorem,
The sum of degrees would be equal to twice the no. of edges
|V|=2|E|
It is given that ξ(G)=ξ(S) then
Sum of degrees of vertices in G is equal to sum of degrees of vertices in S
i.e., 2*(no. of edges in G)=2*no. of edges in S no. of edges in G=no. of edges in S
Eg:

ξ(G)=(2×2)+(2×3)=4+6=10

ξ(S)=2×5=10
You can observe that, though no. of vertices are different, but still no. of edges are same.
 Question 162
Newton-Raphson method is used to compute a root of the equation x2 - 13 = 0 with 3.5 as the initial value. The approximation after one iteration is
 A 3.575 B 3.676 C 3.667 D 3.607
Engineering-Mathematics       Newton-Raphson-Method       2010
Question 162 Explanation:
Note: Out of syllabus.
 Question 163
What is the possible number of reflexive relations on a set of 5 elements?
 A 210 B 215 C 220 D 225
Engineering-Mathematics       Sets-And Relation       2010
Question 163 Explanation:
Let set = ‘A’ with ‘n’ elements,
Definition of Reflexive relation:
A relation ‘R’ is reflexive if it contains xRx ∀ x∈A
A relation with all diagonal elements, it can contain any combination of non-diagonal elements.
Eg:
A={1, 2, 3}

So for a relation to be reflexive, it should contain all diagonal elements. In addition to them, we can have possible combination of (n2-n)non-diagonal elements (i.e., 2n2-n)
Ex:
{(1,1)(2,2)(3,3)} ----- ‘0’ non-diagonal element
{(1,1)(2,2)(3,3)(1,2)} ----- ‘1’ non-diagonal element
{(1,1)(2,2)(3,3)(1,2)(1,3)} “
___________ “
___________ “
{(1,1)(2,2)(3,3)(1,2)(1,3)(2,1)(2,3)(3,1)(3,2)} (n2-n) diagonal elements
____________________
Total: 2n2-n
For the given question n = 5.
The number of reflexive relations =2(25-5)=220
 Question 164
Consider the set S = {1, ω, ω2}, where ω and ω2 are cube roots of unity. If * denotes the multiplication operation, the structure (S,  *) forms
 A A group B A ring C An integral domain D A field
Engineering-Mathematics       Sets-And Relation       2010
Question 164 Explanation:
A Group is an algebraic structure which satisfies
1) closure
2) Associativity
3) Have Identity element
4) Invertible
Over ‘*’ operation the S = {1, ω, ω2} satisfies the above properties.
The identity element is ‘1’ and inverse of 1 is 1, inverse of ‘w’ is 'w2' and inverse of 'w2' is 'w'.
 Question 165
What is the value of
 A 0 B e-2 C e-1/2 D 1
Engineering-Mathematics       Calculus       2010
Question 165 Explanation:
 Question 166
Consider a company that assembles computers. The probability of a faulty assembly of any computer is p. The company therefore subjects each computer to a testing process. This testing process gives the correct result for any computer with a probability of q. What is the probability of a computer being declared faulty?
 A pq + (1 - p)(1 - q) B (1 - q)p C (1 - p)q D pq
Engineering-Mathematics       Probability       2010
Question 166 Explanation:
The probability of the computer being declared faulty is,
= Probability of testing process gives the correct result × Probability that computer is faulty + Probability of tetsing process giving incorrect result × Probability that computer is not faulty
= p × q + (1 - p) (1 - q)
 Question 167
What is the probability that divisor of 1099 is a multiple of 1096?
 A 1/625 B 4/625 C 12/625 D 16/625
Engineering-Mathematics       Probability       2010
Question 167 Explanation:
Probability that divisor of 1099 is a multiple of 1096
We can write 1099 as 1096×103
So, (1099)/(1096) to be a whole number, [1096×103/1096]➝ (1)
We can observe that every divisor of 103 is a multiple of 1096
So number of divisor of 103 to be found first
⇒ 103=(5×2)3=23×53
No. of divisors = (3 + 1) (3 + 1) = 16
Total number of divisor of 1099 are 1099=299×599=100×100=10000
Probability that divisor of 1099 is a multiple of 1096 is
⇒16/10,000
 Question 168
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?
(I) 7, 6, 5, 4, 4, 3, 2, 1
(II) 6, 6, 6, 6, 3, 3, 2, 2
(III) 7, 6, 6, 4, 4, 3, 2, 2
(IV) 8, 7, 7, 6, 4, 2, 1, 1

 A I and II B III and IV C IV only D II and IV
Engineering-Mathematics       Graph-Theory       2010
Question 168 Explanation:
Havel Hakimi theorem:
⇾ Arrange the degree of vertices in descending order
eg. d1,d2, d3...dn
⇾ Discard d1, subtrack ‘1’ from the next 'd1'degrees
eg:
⇒ 1 1 0 1
⇾ We should not get any negative value if its negative, this is not valid sequence
⇾ Repeat it till we get ‘0’ sequence
I. 7, 6, 5, 4, 4, 3, 2, 1
➡️5, 4, 3, 3, 2, 1, 0
➡️3, 2, 2, 1, 0, 0
➡️1, 1, 0, 0, 0
➡️0, 0, 0, 0
[valid]
II. 6, 6, 6, 6, 3, 3, 2, 2
➡️5, 5, 5, 2, 2, 1, 2
put them in descending order
➡️5, 5, 5, 2, 2, 2, 1
➡️4, 4, 1, 1, 1, 1
➡️3, 0, 0, 0, 1 (descending order)
➡️3, 1, 0, 0, 0
➡️0, -1, -1, 0
[This is not valid]
III. 7, 6, 6, 4, 4, 3, 2, 2
➡️5, 5, 3, 3, 2, 1, 1
➡️4, 2, 2, 1, 0, 1
➡️4, 2, 2, 1, 1, 0 (descending order)
➡️1, 1, 0, 0, 0
➡️0, 0, 0, 0
[valid]
IV. 8, 7, 7, 6, 4, 2, 1, 1
There is a degree ‘8’, but there are only ‘8’ vertices.
A vertex cannot have edge to itself in a simple graph. This is not valid sequence.
 Question 169
Consider the following matrix If the eigenvalues of A are 4 and 8, then
 A x=4, y=10 B x=5, y=8 C x=-3, y=9 D x=-4, y=10
Engineering-Mathematics       Linear-Algebra       2010
Question 169 Explanation:

Trace = {Sum of diagonal elements of matrix}

Here given that eigen values are 4, 8
Sum = 8 + 4 = 12
Trace = 2 + y
⇒ 2 + y = 12
y = 10

Determinant = |2y - 3x|
Product of eigen values = 8 × 4 = 32
2y - 3x = 32
(y = 10)
20 - 3x = 32
-12 = 3x
x = -4
∴ x = -4, y = 10
 Question 170
Suppose the predicate F(x, y, t) is used to represent the statement that person x can fool person y at time t. Which one of the statements below expresses best the meaning of the formula ∀x∃y∃t(¬F(x, y, t))?
 A Everyone can fool some person at some time B No one can fool everyone all the time C Everyone cannot fool some person all the time D No one can fool some person at some time
Engineering-Mathematics       Propositional-Logic       2010
Question 170 Explanation:
F(x,y,t) ⇒ Person 'x' can fool person 'y' at time 't'.
For better understanding propagate negation sign outward by applying Demorgan's law.
∀x∃y∃t(¬F(x, y, t)) ≡ ¬∃x∀y∀t(F(x,y,t))
Now converting ¬∃x∀y∀t(F(x,y,t)) to English is simple.
¬∃x∀y∀t(F(x,y,t)) ⇒ There does not exist a person who can fool everyone all the time.
Which means "No one can fool everyone all the time".
Hence, Option (B) is correct.
 Question 171
Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
 A No two vertices have the same degree. B At least two vertices have the same degree. C At least three vertices have the same degree. D All vertices have the same degree.
Engineering-Mathematics       Graph-Theory       2009
Question 171 Explanation:
Method 1:
If all vertices have different degrees, then the degree sequence will be {1,2,3,....n-1}, it will not have ‘n’( A simple graph will not have edge to itself, so it can have edges with all other (n-1) vertices). Degree sequence has only (n-1) numbers, but we have ‘n’ vertices. So, by Pigeonhole principle there are two vertices which has same degree.
Method 2:
A) consider a triangle, all vertices has same degree, so it is false
C) consider a square with one diagonal, there are less than three vertices with same degree, so it is false
D) consider a square with one diagonal, vertices have different degrees. So, it is false.
We can conclude that option B is correct.
 Question 172
What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n ≥ 2.
 A 2 B 3 C n-1 D n
Engineering-Mathematics       Graph-Theory       2009
Question 172 Explanation:
If n≥ 2 and there are no odd length cycles, Then it is bipartite graph. A bipartite graph has the chromatic number 2.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
 Question 173
Which one of the following in NOT necessarily a property of a Group?
 A Commutativity B Associativity C Existence of inverse for every element D Existence of identity
Engineering-Mathematics       Sets-And Relation       2009
Question 173 Explanation:
A Group should satisfy Closure, Associative, should have identity element and each element has inverse.
So, commutativity is not required.
 Question 174
Consider the binary relation R = {(x, y), (x, z), (z, x), (z, y)} on the set {x, y, z}. Which one of the following is TRUE?
 A R is symmetric but NOT antisymmetric B R is NOT symmetric but antisymmetric C R is both symmetric and antisymmetric D R is neither symmetric nor antisymmetric
Engineering-Mathematics       Sets-And Relation       2009
Question 174 Explanation:
Symmetric Relation: A relation R on a set A is called symmetric if (b,a) € R holds when (a,b) € R.
Antisymmetric Relation: A relation R on a set A is called antisymmetric if (a,b)€ R and (b,a) € R then a = b is called antisymmetric.
In the given relation R, for (x,y) there is no (y,x). So, this is not Symmetric. (x,z) is in R also (z,x) is in R, but as per antisymmetric relation, x should be equal to z, where this fails.
So, R is neither Symmetric nor Antisymmetric.
 Question 175
An unbalanced dice (with 6 faces, numbered from 1 to 6) is thrown. The probability that the face value is odd is 90% of the probability that the face value is even. The probability of getting any even numbered face is the If the probability that the face is even given that it is greater than 3 is 0.75, which one of the following options is closest to the probability that the face value exceeds 3?
 A 0.453 B 0.468 C 0.485 D 0.492
Engineering-Mathematics       Probability       2009
Question 175 Explanation:
P(0) = Probability of getting odd no. face.
P(e) = Probability of getting even no. face.
It is given that,
P(0) = 0.9 P(e) ----- (I)
Also we know that,
P(0) + P(e) = 1 ----- (II)
Solving equation (I) and (II) we get,
P(e) = 0.52
Also even no. can be 2 or 4 or 6.
And given in question that P(2) = P(4) = P(6).
So, 3 × P(2) = 0.52
P(2) = 0.175
So, P(2) = P(4) = P(6) = 0.175
Also in question it is given that,
P(e/>3) = 0.75
P(even no. greater than 3)/ P(no. greater than 3) = 0.75
P(4,6)/P(>3) = 0.75
(0.175×2)/P(>3) = 0.75
P(>3) = 0.35/0.75 = 0.467
 Question 176
For the composition table of a cyclic group shown below Which one of the following choices is correct?
 A a, b are generators B b, c are generators C c, d are generators D d, a are generators
Engineering-Mathematics       Sets-And-Relation       2009
Question 176 Explanation:
Each element of set can be written as a power of g in multiplicative notation, or as a multiple of g in additive notation. This element g is called a generator of the group.
We can observe that, a is an identity element. ( a *x = x ). An identity element cannot be a generator, as it cannot produce any other element ( always a*a*... = a).
Also, b*b =a, so it also cannot produce all other elements ( always b*b*... =a , where a is identify element).
c,d are able to produce other elements like { c*c =b, c*(c*c) = c*b= d, c*(c*(c*c))) = c*(c*b)= c*d=a. }. Similar with d.
 Question 177
Which one of the following is the most appropriate logical formula to represent the statement? “Gold and silver ornaments are precious”. The following notations are used: G(x): x is a gold ornament S(x): x is a silver ornament P(x): x is precious
 A ∀x(P(x) → (G(x) ∧ S(x))) B ∀x((G(x) ∧ S(x)) → P(x)) C ∃x((G(x) ∧ S(x)) → P(x) D ∀x((G(x) ∨ S(x)) → P(x))
Engineering-Mathematics       Propositional-Logic       2009
Question 177 Explanation:
Interpreting the options will lead to
(A) for all ornaments, if it is precious then they should be gold and silver.
But, given statement does not says that, “ only gold and silver are precious “ . So this is wrong.
(B) For all ornaments, which contains gold and silver are precious.

Which is only the shaded region in the venn diagrams. But, it misses p,r regions. So, this is wrong option.
C) Some ornaments, which are gold and silver are precious. It is false, because all gold or silver ornaments are precious.
D) For all ornaments, Any ornament which is gold or silver is precious. Which is true.
 Question 178
The binary operation □ is defined as follows Which one of the following is equivalent to P Ú Q ?
 A ¬Q□¬P B P□¬Q C ¬P□Q D ¬P□¬Q
Engineering-Mathematics       Propositional-Logic       2009
Question 178 Explanation:
The options are simple to draw the truth table then go with the corresponding options.

P∨Q=P□️Q
So, option B is correct.
 Question 179

 A 0 B 1 C ln 2 D 1/2 ln 2
Engineering-Mathematics       Calculus       2009
Question 179 Explanation:
 Question 180
Consider the following well-formed formulae: Which of the above are equivalent?
 A I and III B I and IV C II and III D II and IV
Engineering-Mathematics       Propositional-Logic       2009
Question 180 Explanation:
I) ¬∀x(P(x)) = ∃x(¬P(x)) [De morgan's Law]
II ) ¬∃x(P(x))= ∀x(~P(x))
III) ¬∃x(¬P(x)) = ∀x(P(x))
 Question 181

 A 1 B -1 C ∞ D -∞
Engineering-Mathematics       Calculus       Gate-2008
Question 181 Explanation:
 Question 182
If P, Q, R are subsets of the universal set U, then (P∩Q∩R) ∪ (Pc∩Q∩R) ∪ Q∪ Rc is
 A Qc ∪ Rc B P ∪ Qc ∪ Rc C Pc ∪ Qc ∪ Rc D U
Engineering-Mathematics       Sets-And-Relation       Gate-2008
Question 182 Explanation:
Given, (P∩Q∩R)∪(Pc∩Q∩R)∪Qc∪Rc
It can be written as the p.q.r + p'.q.r +q'+r'
=> (p+p').q.r + q' +r'
=> q.r +(q'+r')
=> q.r + q'+r' = 1 i.e U
 Question 183
The following system of equations x1 + x2  + 2x3  = 1 x1 + 2x2 + 3 x3 = 2 x1 + 4x2 + ax3 = 4 has a unique solution. The only possible value(s) for  a is/are
 A 0 B either 0 or 1 C one of 0, 1 or -1 D any real number
Engineering-Mathematics       Linear-Algebra       Gate-2008
Question 183 Explanation:
The conjugate matrix [A|B] is
When a-5=0, then rank(A)=rank[A|B]<3,
So infinite number of solutions.
But, it is given that the given system has unique solution i.e., rank(A)=rank[A|B]=3 will be retain only if a-5≠0.
 Question 184
The minimum number of equal length subintervals needed to approximate
 A 1000e B 1000 C 100e D 100
Engineering-Mathematics       Trapezidal Rule       Gate-2008
Question 184 Explanation:
Note: Out of syllabus.
 Question 185
The Newton-Raphson iteration can be used to compute the
 A square of R B reciprocal of R C square root of R D logarithm of R
Engineering-Mathematics       Newton-Raphson-Method       Gate-2008
Question 185 Explanation:
Note: Out of syllabus.
 Question 186
Which of the following statements is true for every planar graph on n vertices?
 A The graph is connected B The graph is Eulerian C The graph has a vertex-cover of size at most 3n/4 D The graph has an independent set of size at least n/3
Engineering-Mathematics       Graph-Theory       Gate-2008
Question 186 Explanation:
Lets do with elimination method,
(A) Consider the following disconnected graph which is planar.

So false.
(B) A graph is Eulerian if all vertices have even degree but a planar graph can have vertices with odd degree.
So false.
(D) Consider K4 graph. It has independent set size 1 which is less than 4/3.

So false.
Hence, option (C) is correct.
 Question 187

 A P = Q - k B P = Q + k C P = Q D P = Q +2 k
Engineering-Mathematics       Permutation-and-Combination       Gate-2008
Question 187 Explanation:

P=1+3+5+7+...+(2k-1)
=(2-1)+(4-1)+(6-1)+(8-1)+...+(2k-1)
=(2+4+6+8+...+2k)+(-1+-1+-1+k times)
=Q-(1+1+...+k times)
=Q-k
 Question 188
A point on a curve is said to be an extremum if it is a local minimum or a local maximum. The number of distinct extrema for the curve 3x4 - 16x3 + 24x2 + 37 is
 A 0 B 1 C 2 D 3
Engineering-Mathematics       Calculus       Gate-2008
Question 188 Explanation:
f(x) = 3x4 - 16x3 + 24x2 + 37
f’(x) = 12x3 + 48x2 + 48x = 0
12x(x2 - 4x + 4) = 0
x=0; (x-2)2 = 0
x=2
f’’(x) = 36x2 - 96x + 48
f ”(0) = 48
f ”(2) = 36(4) - 96(2) + 48
= 144 - 192 + 48
= 0
At x=2, we can’t apply the second derivative test.
f’(1) = 12; f’(3) = 36, on either side of 2 there is no sign change then this is neither minimum or maximum.
Finally, we have only one Extremum i.e., x=0.
 Question 189
Aishwarya studies either computer science or mathematics everyday. If she studies computer science on a day, then the probability that she studies mathematics the next day is 0.6. If she studies mathematics on a day, then the probability that she studies computer science the next day is 0.4. Given that Aishwarya studies computer science on Monday, what is the probability that she studies computer science on Wednesday?
 A 0.24 B 0.36 C 0.4 D 0.6
Engineering-Mathematics       Probability       Gate-2008
Question 189 Explanation:
→ Aishwarya studied CS on Monday. Then we have two possibilities to she study computer science on wednesday.
(i) She study Mathematics on Tuesday and computer science on wednesday.
⇒ 0.6×0.4
⇒ 0.24
(ii) She study computer science on Tuesday and computer science on wednesday.
⇒ 0.4×0.4
⇒ 0.16
→ The probability that she study computer science on wednesday is
0.24+0.16=0.40
 Question 190
How many of the following matrices have an eigenvalue 1?
 A one B two C three D four
Engineering-Mathematics       Linear-Algebra       Gate-2008
Question 190 Explanation:

Answer: We have only one matrix with eigen value 1.
 Question 191
Let X be a random variable following normal distribution with mean +1 and variance 4. Let Y be another normal variable with mean -1 and variance unknown. If P(X ≤ -1) = P(Y ≥ 2), the standard deviation of Y is
 A 3 B 2 C √2 D 1
Engineering-Mathematics       Probability       Gate-2008
Question 191 Explanation:
P(X ≤ -1) = P(Y ≥ 2)
We can compare their values using standard normal distributions.

The above equation satisfies when σy will be equal to 3.
 Question 192
Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton, and pda(y) means that y is a pushdown automaton. Let equivalent be another predicate such that equivalent (a, b) means a and b are equivalent. Which of the following first order logic statements represents the following: Each finite state automaton has an equivalent pushdown automaton
 A (∀x fsa(x)) ⇒ (∃y pda(y) ∧ equivalent(x,y)) B ∼∀y(∃x fsa(x) ⇒ pda(y) ∧ equivalent(x,y)) C ∀x ∃y(fsa(x) ∧ pda(y) ∧ equivalent(x,y)) D ∀x ∃y(fsa(y)∧ pda(x) ∧ equivalent(x,y))
Engineering-Mathematics       Propositional-Logic       Gate-2008
Question 192 Explanation:
Go through the options.
Option A:
If everything is a FSA. Then there exists an equivalent PDA for everything.
Option B:
Not for the case Y, if there exists a FSA then it can have equivalent PDA.
Option C:
Everything is a PDA and consists equivalent PDA.
Option D:
Everything is a PDA and has exist an equivalent FSA. In option A we are getting the equivalent of a and b.
 Question 193
P and Q are two propositions. Which of the following logical expressions are equivalent?
 A Only I and II B Only I, II and III C Only I, II and IV D All of I, II, III and IV
Engineering-Mathematics       Propositional-Logic       Gate-2008
Question 193 Explanation:
I. P∨∼Q (✔️)
II. ∼(∼P∧Q)⇒(P∨∼Q)≡I (✔️)
III. (P×Q)∨(P×∼Q)∨(∼P×∼Q)
P∧(Q∨∼Q)∨(∼P∧∼Q)
P∨(∼P×∼Q)
(P∨∼P)×(P∨∼Q)
(P∨∼Q)≡I=II (✔️)
IV. (P×Q)∨(P∧∼Q)∨(∼P×Q)
P×(Q∨∼Q)∨(∼P∧Q)
P∨(∼P×Q)
(P∨∼P)×(P∨Q)
(P∨Q)≠I (❌)
So I≡II≡III (✔️)
 Question 194
A sample space has two events A and B such that probabilities P(A ∩ B) = 1/2, P(A') = 1/3, P(B') = 1/3. What is P(A ∪ B)?
 A 11/12 B 10/12 C 9/12 D 8/12
Engineering-Mathematics       Probability       Gate 2008-IT
Question 194 Explanation:
P(A ∩ B) = 1/2
P(A') = 1/3; P(A) = 2/3
P(B') = 1/3; P(B) = 2/3
P(A ∪ B) = P(A) +P(B) - P(A ∩ B)
= 2/3 + 2/3 - 1/2
= 4+4-3/ 6
= 5/6
= 10/12
 Question 195
What is the chromatic number of the following graph?
 A 2 B 3 C 4 D 5
Engineering-Mathematics       Graph-Theory       Gate 2008-IT
Question 195 Explanation:
Chromatic number = 3
→ Chromatic number of a graph is the smallest number of colours needed to colour the vertices so that no two adjacent vertices share the same colour.
 Question 196
What is the size of the smallest MIS(Maximal Independent Set) of a chain of nine nodes?
 A 5 B 4 C 3 D 2
Engineering-Mathematics       Graph-Theory       Gate 2008-IT
Question 196 Explanation:
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9
(2, 5, 8) is the maximal independent set for a chain of 9 nodes. If we add any start node to the set then it will not be MIS.
Independent set:
A set of vertices is called independent set such that no two vertices in the set are adjacent.
 Question 197
Which of the following first order formula is logically valid? Here α(x) is a first order formula with x as a free variable, and β is a first order formula with no free variable.
 A [β→(∃x,α(x))]→[∀x,β→α(x)] B [∃x,β→α(x)]→[β→(∀x,α(x))] C [(∃x,α(x))→β]→[∀x,α(x)→β] D [(∀x,α(x))→β]→[∀x,α(x)→β]
Engineering-Mathematics       Propositional-Logic       Gate 2008-IT
Question 197 Explanation:
[(∃x,α(x))→β]→[∀x,α(x)→β]
L.H.S. : If there is an x such that α(x) is true, then β is true.
R.H.S. : For all x, if α(x) true, then β is true.
Here, the given LHS and RHS are to be same as β is a formula which can be independent of x (if β is true for one x, it is true for every x, and vice-versa).
Here, LHS = RHS
So, Option C is valid.
 Question 198
Which of the following is the negation of [∀ x, α → (∃y, β → (∀ u, ∃v, y))]
 A [∃ x, α → (∀y, β → (∃u, ∀ v, y))] B [∃ x, α → (∀y, β → (∃u, ∀ v, ¬y))] C [∀ x, ¬α → (∃y, ¬β → (∀u, ∃ v, ¬y))] D [∃ x, α ʌ (∀y, β ʌ (∃u, ∀ v, ¬y))]
Engineering-Mathematics       Propositional-Logic       Gate 2008-IT
Question 198 Explanation:
 Question 199
What is the probability that in a randomly chosen group of r people at least three people have the same birthday?
 A B C D
Engineering-Mathematics       Probability       Gate 2008-IT
Question 199 Explanation:
 Question 200
The exponent of 11 in the prime factorization of 300! is
 A 27 B 28 C 29 D 30
Engineering-Mathematics       Combinatorics       Gate 2008-IT
Question 200 Explanation:
 Question 201
In how many ways can b blue balls and r red balls be distributed in n distinct boxes?
 A B C D
Engineering-Mathematics       Combinatorics       Gate 2008-IT
Question 201 Explanation:
 Question 202
Consider the field C of complex numbers with addition and multiplication. Which of the following form(s) a subfield of C with addition and multiplication? (S1) the set of real numbers (S2) {(a + ib) | a and b are rational numbers} (S3) {a + ib | (a2 + b2) ≤ 1} (S4) {ia | a is real}
 A only S1 B S1 and S3 C S2 and S3 D S1 and S2
Engineering-Mathematics       Sets and Relations       Gate 2008-IT
Question 202 Explanation:
S1: It is closed under both * and +.
As real + real = real and real * real = real
S2: It is closed as rational + rational = rational and rational * rational = rational
S3: It is not closed.
⇒ (0.3+0.4i) + (0.7+0.6i) = 1+i
Both (0.3+0.4i) & (0.7+0.6i) are complex numbers follows S3 but addition of them doesn't follows.
⇒ 1+i, (a2+b2) <= 1
⇒ 1+1 is not less than or equal to 1.
S4: {ia | a ia real}
In this there is no multiplicative identity exists (i.e., 1).
 Question 203
Consider the following Hasse diagrams. Which all of the above represent a lattice?
 A (i) and (iv) only B (ii) and (iii) only C (iii) only D (i), (ii) and (iv) only
Engineering-Mathematics       Sets-And-Relation       Gate 2008-IT
Question 203 Explanation:
If a hasse diagram is a lattice then every pair of elements will have exactly one lub and gub.
(ii) and (iii), having more than one lub or glb for some pairs due to which they are not lattice.
 Question 204
G is a simple undirected graph. Some vertices of G are of odd degree. Add a node v to G and make it adjacent to each odd degree vertex of G. The resultant graph is sure to be
 A Regular B Complete C Hamiltonian D Euler
Engineering-Mathematics       Graph-Theory       Gate 2008-IT
Question 204 Explanation:
Euler graph theory is a trail in a finite graph which visits every edge exactly once and which is a undirected graph.
→ In Euler graph all degrees must be even for all nodes. And number of odd degree vertices should be even.
→ So, degree of this new node will be even and as a new edge is formed between this new node and all other nodes of odd degree hence here is not a single node exists with degree odd so this is Euler graph.
 Question 205
If M is a square matrix with a zero determinant, which of the following assertion (s) is (are) correct? (S1) Each row of M can be represented as a linear combination of the other rows (S2) Each column of M can be represented as a linear combination of the other columns (S3) MX = 0 has a nontrivial solution (S4) M has an inverse
 A S3 and S2 B S1 and S4 C S1 and S3 D S1, S2 and S3
Engineering-Mathematics       Linear-Algebra       Gate 2008-IT
Question 205 Explanation:
It is given that determinant of square matrix M is zero, means rows of M can be represented as a linear combination of other rows or columns of M can be represented as a linear combination of other columns. Also if determinant of matrix is zero then rank of matrix, which means MX=0 have infinite no.of solution or non – trivial solution.
If determinant of some square matrix is zero then matrix do not have any inverse.
Hence, from the above definitions we can conclude that S1, S2, S3 are true and S4 is false.
 Question 206
Consider the function f(x) = x2 - 2x - 1. Suppose an execution of the Newton- Raphson method to find a zero of f(x) starts with an approximation x0 = 2 0f x. What is the value of x2, 'the approximation of x' that the algorithm produces after two iterations, rounded to three decimal places?
 A 2.417 B 2.419 C 2.423 D 2.425
Engineering-Mathematics       Newton-Raphson-Method       Gate 2008-IT
Question 206 Explanation:
Note: Out of syllabus.
 Question 207
If f(x) is defined as follows, what is the minimum value of f(x) for x ∊ (0, 2] ?
 A B C D
Engineering-Mathematics       Calculus       Gate 2008-IT
Question 207 Explanation:
 Question 208
Consider the following two statements about the function f(x)=|x|
P. f(x) is continuous for all real values of x
Q. f(x) is differentiable for all real values of x
Which of the following is TRUE?
 A P is true and Q is false. B P is false and Q is true. C Both P and Q are true. D Both P and Q are false.
Engineering-Mathematics       Calculus       Gate-2007
Question 208 Explanation:
f(x) = |x|
→ f(x) is continuous for all real values of x

For every value of x, there is corresponding value of f(x).
For x is positive, f(x) is also positive
x is negative, f(x) is positive.
So, f(x) is continuous for all real values of x.
→ f(x) is not differentiable for all real values of x. For x<0, derivative is negative
x>0, derivative is positive.
Here, left derivative and right derivatives are not equal.
 Question 209
Let S be a set of n elements. The number of ordered pairs in the largest and the smallest equivalence relations on S are:
 A n and n B n2 and n C n2 and 0 D n and 1
Engineering-Mathematics       Sets-And-Relation       Gate-2007
Question 209 Explanation:
A relation is said to be equivalent relation if it satisfies,
→ Reflexive
→ Symmetric
→ Transitive
Let a set S be,
S = {1, 2, 3}
Now, the smallest relation which is equivalence relation is,
S×S = {(1,1), (2,2), (3,3)}
= 3
= n (for set of n elements)
And, the largest relation which is equivalence relation is,
S×S = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)}
= 9
= 32
= n2 (for set of n elements)
 Question 210
Let G be the non-planar graph with the minimum possible number of edges. Then G has
 A 9 edges and 5 vertices B 9 edges and 6 vertices C 10 edges and 5 vertices D 10 edges and 6 vertices
Engineering-Mathematics       Graph-Theory       Gate-2007
Question 210 Explanation:
Using Euler’s formula we know that,
if n ≥ 3 then e ≤ 3n-6 (for planarity)
where n = no. of vertices
e = no. of edges
Now lets check the options.
A) e=9, n=5
9 ≤ 3(5) - 6
9 ≤ 15 - 6
9 ≤ 9
Yes, it is planar.
B) e=9, n=6
9 ≤ 3(6) - 6
9 ≤ 18 - 6 9 ≤ 12 Yes, it is planar.
iii) e=10, n=5
10 ≤ 3(5) - 6
10 ≤ 15 - 6
10 ≤ 9 No, it is not planar.
So, option C is non-planar graph.
iv) e=10, n=6
10 ≤ 3(6) - 6
10 ≤ 18 - 6
10 ≤ 12
Yes, it is planar.
 Question 211
How many different non-isomorphic Abelian groups of order 4 are there?
 A 2 B 3 C 4 D 5
Engineering-Mathematics       Sets-And-Relation       Gate-2007
Question 211 Explanation:
In this problem first of all we find the exponents of prime nos. that can be taken out from given number.
4 = 22
So, prime no. is 2 and power of 2 is 2. So exponent value 2 is considered now.
Now the no. of ways we can divide 2 into sets will be the answer.
So division can be done as,
{1,1}, {0,2}
in two ways. Hence, answer is 2.
 Question 212
Let Graph(x) be a predicate which denotes that x is a graph. Let Connected(x) be a predicate which denotes that x is connected. Which of the following first order logic sentences DOES NOT represent the statement: “Not every graph is connected”?
 A ¬∀x (Graph (x) ⇒ Connected (x)) B ¬∃x (Graph (x) ∧ ¬Connected (x)) C ¬∀x (¬Graph (x) ∨ Connected (x)) D ∀x (Graph (x) ⇒ ¬Connected (x))
Engineering-Mathematics       Propositional-Logic       Gate-2007
Question 212 Explanation:
Option (A) and (C) are same, because in option (C) the given expression is
Given expression is
¬∀x(¬Graph(x) ∨ Connected(x)
which can be rewritten as,
¬∀x(Graph(x) ⇒ Connected(x)
which is equivalent to option (A)
(∵ ¬p∨q ≡ p→q)
So, option (A) and (C) cannot be the answer.
Coming to option (B), the given expression is,
∃x (Graph (x) ∧ ¬Connected (x))
"There exist some graph which is not connected", which is equivalent in saying that "Not every graph is connected".
Coming to option (D),
For all x graph is not connected, which is not correct.
Hence, option (D) is the answer.
 Question 213
Which of the following graphs has an Eulerian circuit?
 A Any k-regular graph where k is an even number. B A complete graph on 90 vertices. C The complement of a cycle on 25 vertices. D None of the above.
Engineering-Mathematics       Graph-Theory       Gate-2007
Question 213 Explanation:
Two necessary condition for the existence of Eulerian circuits is
→ all vertices in the graph have an "even degree".
→ And the graph must be corrected.
Now in option (C) it is saying that the complement of a cycle on 25 vertices without complement the degree of each vertex is 2.
Now since there are 25 vertices, so maximum degree of each vertex will be 24 and so in complement of cycle each vertex degree will be 24 - 2 = 22.
There is a theorem which says "G be a graph with n vertices and if every vertex has a degree of atleast n-1/2 then G is connected."
So we can say that complement of cycle with 25 vertices fulfills both the conditions, and hence is Eulerian circuit.
 Question 214
Suppose we uniformly and randomly select a permutation from the 20! Permutations of 1, 2, 3,….., 20. What is the probability that 2 appears at an earlier position than any other even number in the selected permutation?
 A 1/2 B 1/10 C 9!/20! D None of these
Engineering-Mathematics       Probability       Gate-2007
Question 214 Explanation:
1, 2, 3, 4, …….20
→ Total no. of possible even number = 10
→ Here we are not considering odd number.
→ The probability that 2 appears at an earlier position than any other even number is =1/10
 Question 215
Let A be a 4 x 4 matrix with eigenvalues -5, -2, 1, 4. Which of the following is an eigenvalue of
[A  I]
[I  A]
where I is the 4 x 4 identity matrix?
 A -5 B -7 C 2 D 1
Engineering-Mathematics       Linear-Algebra       Gate-2007
Question 215 Explanation:
Eigen value of A[4×4] matrix is -5, -2, 1, 4.

|(A-λI)2-I|=0 [a2-b2=(a+b)(a-b)]
|(A-λI+I)(A-λI-I)=0
|(A-(λ-I)I)(A-(λ+I)I|=0
Let us assume λ-1=k & λ +1=k
λ =k+1 λ =k-1
⇓ ⇓
for k=-5; λ=-4 λ =-6
k=-2; λ=-1 λ =-3
k=1; λ=2 λ = 0
k=4; λ=5 λ = 3
So; λ=-4,-1,2,5,-6,-3,0,3
Check with the option
Option C = 2
 Question 216

 A B C D
Engineering-Mathematics       Sets-And Relation       Gate-2007
Question 216 Explanation:
π4 = refines every partition. So it has to be bottom of poset diagram.
And, neither π2 refines π3, nor π3 refines π2.
Here, only π1 refined by every set, so it has to be at the top.
Finally, option C satisfies all the property.
 Question 217
Consider the set of (column) vectors defined bu
 A {[1,-1,0]T, [1,0,-1]T} is a basis for the subspace X. B {[1,-1,0]T, [1,0,-1]T} is a linearly independent set, but it does not span X and therefore is not a basis of X. C X is not a subspace of R3 D None of the above
Engineering-Mathematics       Linear-Algebra       Gate-2007
Question 217 Explanation:
Since, [1,-1,0]T and [1,0,-1]T are linearly independent set and spans X. So is the basis for subspace X.
 Question 218

 A 1.5 B √2 C 1.6 D 1.4
Engineering-Mathematics       Newton-Raphson-Method       Gate-2007
Question 218 Explanation:
Given series is xn+1=xn/2+9/8xn ⟶ (I); x0=0.5
Equation based on Newton-Rapson is
xn+1=xn-f(xn)/f'(xn)⟶ (II)
Equate I and II
xn-f(xn)/f'(xn)=xn/2+9/8xn
xn-f(xn)/f'(xn)=xn-xn/2+9/8xn
xn-f(xn)/f'(xn)=xn-(4xn2-9)/8xn
So, f(x)=4xn2-9
4x2-9=0
4x2=9
x2=9/4
x=±3/2
x=±1.5
 Question 219
Consider the data given in above question. 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)?
 A B 220 C 210 D None of the above
Engineering-Mathematics       Combinatorics       Gate-2007
Question 219 Explanation:
Lets name one unit up movement as 'u' and one unit right movement as 'r'.
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 220
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)
 A 29 B 219 C D
Engineering-Mathematics       Combinatorics       Gate-2007
Question 220 Explanation:
So to solve this lets find the no. of paths possible if line segment from (4,4) to (5,4) is taken. And then we will subtract it from the total no. of paths possible.
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}

 Question 221
Suppose there are two coins. The first coin gives heads with probability 5/8 when tossed, while the second coin gives heads with probability 1/4. One of the two coins is picked up at random with equal probability and tossed. What is the probability of obtaining heads ?
 A 7/8 B 1/2 C 7/16 D 5/32
Engineering-Mathematics       Probability       Gate 2007-IT
Question 221 Explanation:
Each coin has equal probability to pick i.e., 1/2.
= (1/2)(5/8) + (1/2)(1/4)
= (5/16) + (1/8)
= 7/16
 Question 222
Let A be the . What is the maximum value of xTAx where the maximum is taken over all x that are the unit eigenvectors of A?
 A B C D
Engineering-Mathematics       Linear-Algebra       Gate 2007-IT
Question 222 Explanation:
 Question 223
The minimum positive integer p such that 3p modulo 17 = 1 is
 A 5 B 8 C 12 D 16
Engineering-Mathematics       Numerical-Methods       Gate 2007-IT
Question 223 Explanation:
According to Fermat's little theorem,
ap-1 mod p = 1
Here, p = 17
So, p-1 = 16 is the answer.
 Question 224
Which one of these first-order logic formula is valid?
 A ∀x(P(x) ⇒ Q(x)) ⇒ (∀xP(x) ⇒ ∀xQ(x)) B ∃x(P(x) ∨ Q(x)) ⇒ (∃xP(x) ⇒ ∃xQ(x)) C ∃x(P(x) ∧ Q(x)) (∃xP(x) ∧ ∃xQ(x)) D ∀x∃y P(x, y) ⇒ ∃y∀x P(x, y)
Engineering-Mathematics       Propositional-Logic       Gate 2007-IT
Question 224 Explanation:
LHS = for every x, if P holds then Q holds
RHS = if P(x) holds for all x, then Q(x) holds for all x
LHS ⇒ RHS (✔)
RHS ⇒ LHS (️❌)
 Question 225
The trapezoidal method is used to evaluate the numerical value of . Consider the following values for the step size h. i. 10-2 ii. 10-3 iii. 10-4 iv. 10-5 For which of these values of the step size h, is the computed value guaranteed to be correct to seven decimal places. Assume that there are no round-off errors in the computation.
 A (iv) only B (iii) and (iv) only C (ii), (iii) and (iv) only D (i), (ii), (iii) and (iv)
Engineering-Mathematics       Trapezoidal Method       Gate 2007-IT
Question 225 Explanation:
Note: Out of syllabus.
 Question 226
A partial order P is defined on the set of natural numbers as follows. Here x/y denotes integer division. i. (0, 0) ∊ P. ii. (a, b) ∊ P if and only if a % 10 ≤ b % 10 and (a/10, b/10) ∊ P. Consider the following ordered pairs: i. (101, 22) ii. (22, 101) iii. (145, 265) iv. (0, 153) Which of these ordered pairs of natural numbers are contained in P?
 A (i) and (iii) B (ii) and (iv) C (i) and (iv) D (iii) and (iv)
Engineering-Mathematics       Sets-And-Relation       Gate 2007-IT
Question 226 Explanation:
For ordered pair (a, b) to be in P, each digit in starting from unit place must not be larger than the corresponding digit in b.
The given condition can be satisfied by
(iii) (145, 265) → 5 ≤ 5, 4 < 6 and 1< 2
(iv) (0, 153) → 0 < 3
 Question 227
Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5.
 A 5 B 6 C 7 D 10
Engineering-Mathematics       Probability       Gate 2007-IT
Question 227 Explanation:
Total spaces = 20, no. of entries = 1
Probability of collision for each entry = 1/20
After inserting X values then probability becomes 1/2
i.e., (1/20)X = 1/2
X = b
 Question 228

In a multi-user operating system on an average, 20 requests are made to use a particular resource per hour. The arrival of requests follows a Poisson distribution. The probability that either one, three or five requests are made in 45 minutes is given by :

 A 6.9 × 106 × e-20 B 1.02 × 106 × e-20 C 6.9 × 103 × e-20 D 1.02 × 103 × e-20
Engineering-Mathematics       Probability       Gate 2007-IT
Question 228 Explanation:
q0 request in 1 hour. So we can expect 15 requests in 45 minutes.
So, λ=15
 Question 229
Consider the sequence <xn>, n>= 0 defined by the recurrence relation xn + 1 = c . xn2- 2, where c > 0. Suppose there exists a non-empty, open interval (a, b) such that for all x0 satisfying a < x0 < b, the sequence converges to a limit. The sequence converges to the value?
 A B C D
Engineering-Mathematics       Combinatorics       Gate 2007-IT
Question 229 Explanation:
Let c=1, x0=1
Then,
x1 = c ⋅ (x0)2 - 2 = 1 ⋅ (1)2 - 2 = -1
x2 = c ⋅ (x1)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 230

 A (i) 0nly B (i) and (ii) only C (i), (ii) and (iii) only D (i), (ii), (iii) and (iv)
Engineering-Mathematics       Combinatorics       Gate 2007-IT
Question 230 Explanation:
For the series to converge the limit: 'n' tends to infinity of (xn+1 / xn) should be <1.
From the recurrence we should have c(xn)2 - xn - 2 < 0
For all the above values of c we have above equation as negative.
 Question 231
Let P1, P2,..... , Pn be n points in the xy-plane such that no three of them are collinear. For every pair of points Pi and Pj, let Lij be the line passing through them. Let Lab be the line with the steepest gradient amongst all n(n -1)/2 lines. Which one of the following properties should necessarily be satisfied ?
 A Pa and Pb are adjacent to each other with respect to their x-coordinate B Either Pa or Pb has the largest or the smallest y-coordinate among all the points C The difference between x-coordinates Pa and Pb is minimum D None of the above
Engineering-Mathematics       Lines-and-Curves       Gate 2007-IT
Question 231 Explanation:
Draw the line from the first to third point, and look at whether the middle point is above, at or below it. If the middle point is on the line, all slopes are equal. If the middle point is above the line, then the slope from the first to the second point is the highest. If the middle point is below the line, then the slope from the middle point to the second is highest. In any case, you can find a greater slope betweem two adjacent points.
 Question 232
Let P1,P2,…,Pn be n points in the xy-plane such that no three of them are collinear. For every pair of points Pi and Pj, let Lij be the line passing through them. Let Lab be the line with the steepest gradient among all n(n−1)/2 lines. The time complexity of the best algorithm for finding Pa and Pb is
 A Θ(n) B Θ(nlogn) C Θ(nlog2n) D Θ(n2)
Engineering-Mathematics       Lines-and-Curves       Gate 2007-IT
Question 232 Explanation:

For gradient to be maximum x2-x1 should be minimum. So, sort the points (in Θ(n logn) time) according to n coordinate and find the minimum difference between them (in Θ(n) time).
∴ Complexity = Θ(n logn + n) = Θ(n logn)
 Question 233
The 2n vertices of a graph G corresponds to all subsets of a set of size n, for n >= 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The maximum degree of a vertex in G is:
 A B 2n-2 C 2n-3 × 3 D 2n-1
Engineering-Mathematics       Graph-Theory       Gate-2006
Question 233 Explanation:
The degree of each subset with k elements will be
(k(c))2 2n-k
∴ We need to find 'k' value such that, the value will be maximum.[k should be an integer].
If you differentiate (k(c))2 2n-k w.r.t. k and equal to 0.
You will get k = 2/(loge)2 which is not an integer.
So you can see it like

∴ The maximum degree 3⋅2n-3 at k=3 or k=4.
 Question 234
The 2n vertices of a graph G corresponds to all subsets of a set of size n, for n >= 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in G is:
 A n B n+2 C 2n/2 D 2n / n
Engineering-Mathematics       Graph-Theory       Gate-2006
Question 234 Explanation:
Not connected nodes is n+1.
While other nodes are connected so that total number of connected components is (n+1)+1
(here we are adding 1 because it is connected corresponding remaining vertices)
= n+2
 Question 235
A relation R is defined on ordered pairs of integers as follows: (x,y) R(u,v) if x < u and y > v. Then R is: Then R is:
 A Neither a Partial Order nor an Equivalence Relation B A Partial Order but not a Total Order C A Total Order D An Equivalence Relation
Engineering-Mathematics       Sets-And Relation       Gate-2006
Question 235 Explanation:
If a relation is equivalence then it must be
i) Symmetric
ii) Reflexive
iii) Transitive
If a relation is partial order relation then it must be
i) Reflexive
ii) Anti-symmetric
iii) Transitive
If a relation is total order relation then it must be
i) Reflexive
ii) Symmetric
iii) Transitive
iv) Comparability
Given ordered pairs are (x,y)R(u,v) if (xv).
Here <, > are using while using these symbol between (x,y) and (y,v) then they are not satisfy the reflexive relation. If they uses (x<=u) and (y>=u) then reflexive relation can satisfies.
So, given relation cannot be a Equivalence. Total order relation or partial order relation.
 Question 236
The set {1, 2, 3, 5, 7, 8, 9} under multiplication modulo 10 is not a group. Given below are four plausible reasons. Which one of them is false?
 A It is not closed B 2 does not have an inverse C 3 does not have an inverse D 8 does not have an inverse
Engineering-Mathematics       Sets-And Relation       Gate-2006
Question 236 Explanation:
The given set is x = {1,2,3,5,7,8,9}
Option A:
It is not closed under multiplication. After multiplication modulo (10) we get ‘0’. The ‘0’ is not present in the set.
(2*5)%10 ⇒ 10%10 = 0
Option B:
2 does not have an inverse such as
(2*x)%10 ≠ 1
Option C:
3 have an inverse such that
(3*7)%10 = 1
Option D:
8 does not have an inverse such that
(8*x)%10 ≠ 1
 Question 237
The 2n vertices of a graph G corresponds to all subsets of a set of size n, for n >= 6 . Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of vertices of degree zero in G is:
 A 1 B n C n+1 D 2n
Engineering-Mathematics       Graph-Theory       Gate-2006
Question 237 Explanation:
No. of vertices with degree zero is
= no. of subsets with size less than or equal to 1
= n+1, because in question it is given that the two vertices are connected if and only if the corresponding sets intersect in exactly two elements.
 Question 238
Let X, Y, Z be sets of sizes x, y and z respectively. Let W = X×Y and E be the set of all subsets of W. The number of functions from Z to E is:
 A Z2xy B Z×2xy C Z2x+y D 2xyz
Engineering-Mathematics       Sets-And-Functions       Gate-2006
Question 238 Explanation:
A set consists of n elements then no. of possible subsets are 2n.
A set ‘P’ consists of m elements and ‘Q’ consists of n elements then total number of function from P to Q is mn.
⇒ E be the no. of subsets of W = 2|w| = 2|xxy| = 2xy
No. of function from Z to E is = (2xy)z = (2xy)z = 2xyz
 Question 239
Consider the polynomial p(x) = a0 + a1x + a2x2 + a3x3, where ai ≠ 0, ∀i. The minimum number of multiplications needed to evaluate p on an input x is:
 A 3 B 4 C 6 D 9
Engineering-Mathematics       Numerical-Methods       Gate-2006
Question 239 Explanation:
Given polynomial equation is
p(x) = a0 + a1x + a2x2 + a3x3 where ai≠0
This can be written as
p(x) = a0 +x( a1 + a2x + a3x2)=a0+(a1+(a2+a3x)x)x
Total no. of multiplications required is 3
i.e., a3x = K.....(i)
(a2+K)x = M..... (ii)
(a1+M)x=N...... (iii)
 Question 240
Consider the following propositional statements: P1 : ((A ∧ B) → C)) ≡ ((A → C) ∧ (B → C)) P2 : ((A ∨ B) → C)) ≡ ((A → C) ∨ (B → C)) Which one of the following is true?
 A P1 is a tautology, but not P2 B P2 is a tautology, but not P1 C P1 and P2 are both tautologies D Both P1 and P2 are not tautologies
Engineering-Mathematics       Propositional-Logic       Gate-2006
Question 240 Explanation:
It’s better to draw truth table such that

Both P1 and P2 are not Tautologies.
 Question 241
A logical binary relation □ ,is defined as follows: Let ~ be the unary negation (NOT) operator, with higher precedence than □. Which one of the following is equivalent to A∧B ?
 A (~A B) B ~(A ~B) C ~(~A ~B) D ~(~ A B)
Engineering-Mathematics       Sets-And-Relation       Gate-2006
Question 241 Explanation:
 Question 242
We are given a set X = {x1, .... xn} where xi = 2i. A sample S ⊆ X is drawn by selecting each xi independently with probability pi = 1/2. The expected value of the smallest number in sample S is:
 A 1/n B 2 C √n D n
Engineering-Mathematics       Probability       Gate-2006
Question 242 Explanation:
The smallest element in sample S would be xi for which i is the smallest.
The given probability Pi is for selection of each item independently with probability 1/2.
Now, Probability for x1 to be smallest in S = 1/2
Now, Probability for x2 to be smallest in S = Probability of x1 not being in S × Probability of x2 being in S
= 1/2 × 1/2
Similarly, Probability xi to be smallest = (1/2)i
Now the Expected value is
 Question 243
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?
 A (n-|A ∪ B|) |A| |B| B (|A|2+|B|2)n2 C n!(|A∩B|/|A∪B|) D
Engineering-Mathematics       Combinatorics       Gate-2006
Question 243 Explanation:
Given a set of elements N = {1, 2, 3, ...N}
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 1-to-1 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 244
Fis an n×n real matrix. b is an n×1 real vector. Suppose there are two n×1 vectors, u and v such that, u≠v and Fu=b, Fv=b. Which one of the following statements is false?
 A Determinant of F is zero B There are an infinite number of solutions to Fx=b C There is an x≠0 such that Fx=0 D F must have two identical rows
Engineering-Mathematics       Linear-Algebra       Gate-2006
Question 244 Explanation:
⇾ Fu = b, Fv = b
Fu = Fv
Fu - Fv = 0
F(u - v) = 0
Given u ≠ v
F = 0 (i.e., Singular matrix, so determinant is zero)
Option A is true.
⇾ Fx = b; where F is singular
It can have no solution (or) infinitely many solutions.
Option B is true.
⇾ x ≠ 0 such that Fx = 0 is True because F is singular matrix (“stated by singular matrix rules). Option C is true.
⇾ F can two identical columns and rows.
Option D is false.
 Question 245
Which one of the first order predicate calculus statements given below correctly express the following English statement?
Tigers and lions attack if they are hungry or threatened.
 A ∀x [(tiger(x) ∧ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}] B ∀x [(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) ∧ attacks(x)}] C ∀x [(tiger(x) ∨ lion(x)) → {(attacks(x) → (hungry (x)) ∨ threatened (x))}] D ∀x [(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}]
Engineering-Mathematics       Propositional-Logic       Gate-2006
Question 245 Explanation:
Tigers and lions attack if they are hungry (or) threatened.
Here we have two cases.
i) If Tiger is hungry (or) threaten that will attack.
ii) If Lion is hungry (or) threaten that will attack.
If Tiger is hungry (or) threaten then both lion and tiger will not attack only Tiger will attack and vice-versa.
∀x[(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}]
Note: Don’t confuse with the statement Tiger and Lion.
 Question 246
Let S = {1, 2, 3, ...., m}, m>3. Let x1, x2,....xn be the subsets of S each of size 3. Define a function f from S to the set of natural numbers as, f(i) is the number of sets of Xj that contain the element i. That is f(i) =
 A 3m B 3n C 2m+1 D 2n+1
Engineering-Mathematics       Sets And Functions       Gate-2006
Question 246 Explanation:
No. of subsets of size 3 is = mC3
n = mC3
Which subsets contains element i then size is
= (m-1)C2
Because 1 element is already known
 Question 247
Let E, F and G be finite sets. Let X = (E ∩ F) - (F ∩ G) and Y = (E - (E ∩ G)) - (E - F). Which one of the following is true?
 A X ⊂ Y B X ⊃ Y C X = Y D X - Y ≠ ∅ and Y - X ≠ ∅
Engineering-Mathematics       Sets-And-Relation       Gate-2006
Question 247 Explanation:
Let us consider
E = {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3), (3,1)}
F = {(1,1), (2,2), (3,3)}
G = {(1,3), (2,1), (2,3), (3,1)}
X = (E∩F) - (F∩G)
= {(1,1), (2,2), (3,3) - ∅}
= {(1,1), (2,2), (3,3)} (✔️)
Y = (E - (E∩G) - (E - F))
= (E - {(1,3), (2,3), (3,1)} - {(1,2), (1,3), (2,3), (3,1)})
= {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3), (3,1)} - {(1,3), (2,2), (2,1)} - (1,2), (1,3), (2,3), (3,1)}
= {(1,1), (1,2), (2,2), (3,3)} - {(1,2), (1,3), (2,3), (3,1)}
= {(1,1), (2,2), (3,3)} (✔️)
X = Y

X = (E∩F) - (F∩G) = {2,5} - {5} = {2}
Y = (E - (E∩G) - (E - F))
= {(1,2,4,5) - (4,5) - (1,4)}
= {(1,2) - (1,4)}
= {2}
X = Y
 Question 248
For each element in a set of size 2n, an unbiased coin is tossed. The 2n coin tosses are independent. An element is chosen if the corresponding coin toss were head. The probability that exactly n elements are chosen is:
 A B C D
Engineering-Mathematics       Probability       Gate-2006
Question 248 Explanation:
Total number of coins = 2n
No. of elements selected = n
Probability of getting head = ½
Probability of n heads out of 2n coin tosses is
2nCn*(1/2)n*(1/2)n=2nCn/4n
 Question 249

In a certain town, the probability that it will rain in the afternoon is known to be 0.6. Moreover, meteorological data indicates that if the temperature at noon is less than or equal to 25°C, the probability that it will rain in the afternoon is 0.4. The temperature at noon is equally likely to be above 25°C, or at/below 25°C. What is the probability that it will rain in the afternoon on a day when the temperature at noon is above 25°C?

 A 0.4 B 0.6 C 0.8 D 0.9
Engineering-Mathematics       Probability       Gate 2006-IT
Question 249 Explanation:
Probability rain in afternoon = (0.5×probability of rain when temp≤25) + (0.5×Probability of rain when temp>25)
0.6 = (0.5×0.4) + (0.5×P(rain at temp>25)
0.6 = (2) + (0.5×P(rain at temp>25)
P(rain at temp>25) = 0.8
 Question 250
For the set N of natural numbers and a binary operation f : N x N → N, an element z ∊ N is called an identity for f, if f (a, z) = a = f(z, a), for all a ∊ N. Which of the following binary operations have an identity?
1. f (x, y) = x + y - 3
2. f (x, y) = max(x, y)
3. f (x, y) = xy
 A 1 and 2 only B 2 and 3 only C 1 and 3 only D None of these
Engineering-Mathematics       Sets and Relations       Gate 2006-IT
Question 250 Explanation:
(1) f(x, y) = x + y -3
y = 3
Here, identity element is 3.
(2) f(x, y) = max(x, y) = x = max(y, x)
⇒ y = 1
Here, identity element = 1
(3) f(x, y) = xny is not equal to f(y, x) = ynx
So, no identity element.
 Question 251
Given a boolean function f (x1, x2, …, xn), which of the following equations is NOT true.
 A f (x1, x2, …, xn) = x1’f(x1, x2, …, xn) + x1f(x1, x2, …, xn) B f (x1, x2, …, xn) = x2f(x1, x2, …, xn) + x2’f(x1, x2, …, xn) C f (x1, x2, …, xn) = xn’f(x1, x2, …, 0) + xnf(x1, x2, …,1) D f (x1, x2, …, xn) = f(0, x2, …, xn) + f(1, x2, .., xn)
Engineering-Mathematics       Sets-And-Relation       Gate 2006-IT
Question 251 Explanation:
Proceed by taking f(x1) = x,
LHS: f(x1) = 0 where x1 = 0
LHS: f(x1) = 1 when x1 = 1
RHS: f(0) + f(1) = 0 + 1 = always 1
 Question 252
Consider the following first order logic formula in which R is a binary relation symbol. ∀x∀y (R(x, y)  => R(y, x)) The formula is
 A satisfiable and valid B satisfiable and so is its negation C unsatisfiable but its negation is valid D satisfiable but its negation is unsatisfiable
Engineering-Mathematics       Propositional-Logic       Gate 2006-IT
Question 252 Explanation:
The given relationis known to be symmetry. We have both symmetric relations possible as well as antisymmetric but neither always holds for all sets. So they both are valid but are satisfiable.
 Question 253

When a coin is tossed, the probability of getting a Head is . Let be the random variable denoting the number of tosses till the first Head appears, including the toss where the Head appears. Assuming that successive tosses are independent, the expected value of  is

 A 1/p B 1/(1-p) C 1/p2 D 1/(1-p2)
Engineering-Mathematics       Probability       Gate 2006-IT
Question 253 Explanation:
E = 1 × P + (2 × (1 - p) p) + (3 × ( 1 - p) (1 - p) p) + ......
Multiply both sides with (1 - p) and subtract,
E - (1 - p) E = 1 × p + (1 - p) p + (1 - p) (1 - p) p + ......
E - (1 - p) E = p/(1 - (1 - p))
(1 - 1 + p) E = 1
pE = 1
E = 1/p
 Question 254
Let P, Q and R be sets let Δ denote the symmetric difference operator defined as PΔQ = (P U Q) - (P ∩ Q). Using Venn diagrams, determine which of the following is/are TRUE? PΔ (Q ∩ R) = (P Δ Q) ∩ (P Δ R) P ∩ (Q ∩ R) = (P ∩ Q) Δ (P Δ R)
 A 1 only B 2 only C Neither 1 nor 2 D Both 1 and 2
Engineering-Mathematics       Sets-And-Relation       Gate 2006-IT
Question 254 Explanation:

P = {1, 2, 4, 5}
Q = {2, 3, 5, 6}
R = {4, 5, 6, 7}
(1) P Δ (Q ∩ R) = (P Δ Q) ∩ (P Δ R)
P Δ ({2,3,5,6} ∩ {4,5,6,7}) = ({1,2,4,5} Δ {2,3,5,6} ∩ {1,2,4,5} Δ {4,5,6,7})
P Δ {5,6} = ({1,2,3,4,5,6} - {2,5}) ∩ ({1,2,4,5,6,7} - {4,5})
({1,2,4,5} Δ {5,6}) = {1,3,4,6} ∩ {1,2,6,7}
{1,2,4,5,6} - {5} = {1,6}
{1,2,4,6} ≠ {1,6}
Statement-1 is False.
(2) P ∩ (Q ∩ R) = (P ∩ Q) Δ (P Δ R)
LHS:
{1,2,4,5} ∩ {5,6} = {5}
RHS:
({1,2,4,5} ∩ {2,3,5,6}) Δ ({1,2,4,5} Δ {4,5,6,7})
{2,5} Δ ({1,2,4,5,6,7} - {4,5})
{2,5} Δ {1,2,6,7}
{1,2,5,6,7} - {2}
{1,5,6,7}
LHS ≠ RHS
Statement - 2 is also wrong.
 Question 255
What is the cardinality of the set of integers X defined below? X = {n | 1 ≤ n ≤ 123, n is not divisible by either 2, 3 or 5}
 A 28 B 33 C 37 D 44
Engineering-Mathematics       Sets       Gate 2006-IT
Question 255 Explanation:
n = 123
A = set of numbers divisible by 2
B = set of numbers divisible by 3
C = set of numbers divisible by 5
n(A∪B∪C) = n(A) + n(B) + n(C) - n(A∩B) - n(B∩C) - n(C∩A) + n(A∩B∩C)
= ⌊123/2⌋ + ⌊123/3⌋ + ⌊123/5⌋ - ⌊123/6⌋ - ⌊123/15⌋ - ⌊123/10⌋ + ⌊123/30⌋
= 61 + 41 + 24 - 20 -12 - 8 + 4
= 90
Total no. that are not divisible
= n - n(A∪B∪C)
= 123 - 90
= 33
 Question 256

Consider the undirected graph G defined as follows. The vertices of G are bit strings of length n. We have an edge between vertex u and vertex v if and only if u and v differ in exactly one bit position (in other words, v can be obtained from u by flipping a single bit). The ratio of the chromatic number of G to the diameter of G is

 A 1/(2n-1) B 1/n C 2/n D 3/n
Engineering-Mathematics       Graph-Theory       Gate 2006-IT
Question 256 Explanation:
For the given condition we can simply design a K-map and mark an edge between every two adjacent cells in K-map.
That will give us a bipartite graph, with chromatic number = 2
Also from the same we can conclude that we need for a 'n' bit string, to traverse no more than (n-1) edges or 'n' vertices to get a path between two arbitary points. So the ratio is (2/n).
 Question 257
What are the eigenvalues of the matrix P given below
 A B a, a, a C 0, a, 2a D -a, 2a, 2a
Engineering-Mathematics       Linear-Algebra       Gate 2006-IT
Question 257 Explanation:
 Question 258
Match the following iterative methods for solving algebraic equations and their orders of convergence.
 A 1-R, 2-S, 3-P, 4-Q B 1-S, 2-R, 3-Q, 4-P C 1-S, 2-Q, 3-R, 4-P D 1-S, 2-P, 3-Q, 4-R
Engineering-Mathematics       Match-the-Following       Gate 2006-IT
Question 258 Explanation:
Note: Out of syllabus.
 Question 259
The following definite integral evaluates to
 A B C D E None of the above
Engineering-Mathematics       Calculus       Gate 2006-IT
Question 259 Explanation:
 Question 260
x + y/2 = 9 3x + y = 10 The value of the Frobenius norm for the above system of equations is:
 A 0.5 B 0.75 C 1.5 D 2
Engineering-Mathematics       Linear-Algebra       Gate 2006-IT
Question 260 Explanation:
 Question 261
x + y/2 = 9 3x + y = 10 What can be said about the Gauss-Siedel iterative method for solving the above set of linear equations?
 A it will converge B it will diverse C it will neither converge nor diverse D It is not applicable
Engineering-Mathematics       Linear-Algebra       Gate 2006-IT
Question 261 Explanation:
As,
|1| + |1/2| <= |9|
and |3| + |1| <= |10|
 Question 262
Let A, B and C be non-empty sets and let X = (A - B) - C and Y = (A - C) - (B - C). Which one of the following is TRUE?
 A X = Y B X ⊂ Y C Y ⊂ X D None of these
Engineering-Mathematics       Sets-And Relation       Gate-2005
Question 262 Explanation:
Consider, A = {1, 2, 3, 4, 5, 6}
B = {1, 3, 4, 5}
C = {2, 4, 5, 6}
X = (A - B) - C
X = {2, 6} - {2, 4, 5, 6}
= ∅
Y = (A - C) - (B - C)
= {1, 3} - { 1, 3}
= ∅
X = Y
X = (A - B) - C
= (1, 5) - (5, 7, 4, 3)
= (1)
Y = (A - C) - (B - C)
= (1, 4) - (2, 4)
= (1)
X = Y
 Question 263
Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is:
 A 6 B 8 C 9 D 13
Engineering-Mathematics       Graph-Theory       Gate-2005
Question 263 Explanation:
No. of faces in a planar embedding of a graph is
F = E - V + 2 [From Euler's formula i.e., F + V - E = 2]
F = 19 - 13 +2
F = 8
 Question 264
Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then, the size of the maximum independent set of G is
 A 12 B 8 C Less than 8 D More than 12
Engineering-Mathematics       Graph-Theory       Gate-2005
Question 264 Explanation:
No. of vertices = 20
Edges = 100
Minimum cover of vertex G is = 8
Maximum Independent set of G = No. of vertices - Minimum cover of vertex G
= 20 - 8
= 12
 Question 265
Let f(x) be the continuous probability density function of a random variable X. The probability that a < X ≤ b, is:
 A f(b - a) B f(b) - f(a) C D
Engineering-Mathematics       Probability       Gate-2005
Question 265 Explanation:
f(x) be the continuous probability density function of random variable X.
Then the probablity be area of the corresponding curve i.e.,
 Question 266
The set {1, 2, 4, 7, 8, 11, 13, 14} is a group under multiplication modulo 15. The inverses of 4 and 7 are respectively:
 A 3 and 13 B 2 and 11 C 4 and 13 D 8 and 14
Engineering-Mathematics       Sets-And Relation       Gate-2005
Question 266 Explanation:
Let say,
Inverse of 4 = m; Inverse of 7 = n
(4×m)%15=1; (7*n)%15=1
Option A: m=3 n=13
12%15≠1 (✖️) 91%15=1 (✔️)
Option B: m=2 n=11
8%15≠1 (✖️) 11%15≠1 (✖️)
Option C: m=4 n=13
16%15=1(✔️) 91%15=1 (✔️)
Option D: m=8 n=14
120%15≠1(✖️) 98%15≠1(✖️)
 Question 267
A random bit string of length n is constructed by tossing a fair coin n times and setting a bit to 0 or 1 depending on outcomes head and tail, respectively. The probability that two such randomly generated strings are not identical is:
 A 1/2n B 1 - 1/n C 1/n! D 1-(1/2n)
Engineering-Mathematics       Probability       Gate-2005
Question 267 Explanation:
Total combinations of strings that can be generated are 2n. We will get one such string in the first experiment. So, favourable cases for the second string are 2n - 1, so that it doesn't match with the previous generated string.
Hence Probability = (2n - 1) /2n = 1 - 1/2n
 Question 268
Box P has 2 red balls and 3 blue balls and box Q has 3 red balls and 1 blue ball. A ball is selected as follows:
(i)  Select a box
(ii) Choose a ball from the selected box such that each ball in
the box is equally likely to be chosen. The probabilities of
selecting boxes P and Q are (1/3) and (2/3), respectively.
Given that a ball selected in the above process is a red ball, the probability that it came from the box P is
 A 4/19 B 5/19 C 2/9 D 19/30
Engineering-Mathematics       Probability       Gate-2005
Question 268 Explanation:
P → 2 red, 3 blue
Q → 3 red, 1 blue
The probability of selecting a red ball is
(1/3)(2/5) + (2/3)(3/4)
2/15 + 1/2 = 19/30
The probability of selecting a red ball from P
(1/3) * (2/5) = 2/15
→ The colour of ball is selected is to be red and that is taken from the box P.
⇒ Probability of selecting a red ball from P/Probability of selecting a red ball
⇒ (2/15)/(19/30)
⇒ 4/19
 Question 269
What are the eigenvalues of the following 2 × 2 matrix?
 A -1 and 1 B 1 and 6 C 2 and 5 D 4 and -1
Engineering-Mathematics       Linear-Algebra       Gate-2005
Question 269 Explanation:

|A| = (2 - λ)(5 - λ) - (4) = 0
10 - 7λ+ λ2 - 4= 0
λ2 - 7λ + 6 = 0
λ2 - 6λ - λ + 6 = 0
(λ - 6) -1(λ - 6) = 0
λ = 1 (or) 6
 Question 270

 A i B i+1 C 2i D 2i
Engineering-Mathematics       Combinatorics       Gate-2005
Question 270 Explanation:

Put g(i) = i+1

S = 1 + 2x + 3x2 + 4x3 + .....
Sx = 1x + 2x2 + 3x3 + 4x4 + ......
S - Sx = 1 + x + x2 + x3 + .....
[Sum of infinite series in GP with ratio < 1 is a/1-r]
S - Sx = 1/(1-x)
S(1-x) = 1/(1-x)
S = 1/(1-x)2
 Question 271
Which one of the following graphs is NOT planar?
 A G1 B G2 C G3 D G4
Engineering-Mathematics       Graph-Theory       Gate-2005
Question 271 Explanation:
G2 can also be drawn as

which is planar
G3 can also be drawn as

which is planar
G4 can also be drawn as

which is planar
But G1 cannot be drawn as planar graph.
Hence, option (A) is the answer.
 Question 272
Consider the following system of equations in three real variables xl, x2 and x3 2x1 - x2 + 3x3 = 1 3x1- 2x2 + 5x3 = 2 -x1 + 4x2 + x3 = 3 This system of equations has
 A no solution B a unique solution C more than one but a finite number of solutions D an infinite number of solutions
Engineering-Mathematics       Linear-Algebra       Gate-2005
Question 272 Explanation:

2(-2 - 20) +1(3 + 5) + 3(12 - 2)
= -44 + 8 + 30
= -6 ≠ 0
→ |A| ≠ 0, we have Unique Solution.
 Question 273
Consider the set H of all 3 × 3 matrices of the type where a, b, c, d, e and f are real numbers and abc ≠ 0. Under the matrix multiplication operation, the set H is
 A a group B a monoid but not a group C a semi group but not a monoid D neither a group nor a semi group
Engineering-Mathematics       Sets-And-Relation       Gate-2005
Question 273 Explanation:
abc != 0 & Identity matrix is identity then it is non-singular and inverse is also defined.
The algebraic structure is a group because the given matrix can have inverse and the inverse is non-singular.
 Question 274
What is the minimum number of ordered pairs of non-negative numbers that should be chosen to ensure that there are two pairs (a, b) and (c, d) in the chosen set such that "a ≡ c mod 3" and "b ≡ d mod 5"
 A 4 B 6 C 16 D 24
Engineering-Mathematics       Sets-And-Relation       Gate-2005
Question 274 Explanation:
a = cmod3
That means a=0,1,2 ⇒ |3|
b = dmod5
That means b=0,1,2,3,4 ⇒ |4|
→ Total no. of order pairs = 3 * 5 = 15
→ Ordered pair (c,d) has 1 combination.
Then total no. of combinations = 15+1 = 16
 Question 275
Let f: B → C and g: A → B be two functions and let h = f∘g. Given that h is an onto function. Which one of the following is TRUE?
 A f and g should both be onto functions B f should be onto but g need not be onto C g should be onto but f need not be onto D both f and g need not be onto
Engineering-Mathematics       Sets And Functions       Gate-2005
Question 275 Explanation:
Given:
f: B→C and g: A→B are two functions.
h = f∘g = f(g(x))
→ If his onto function, that means for every value in C, there must be value in A.
→ Here, we are mapping C to A using B, that means for every value in C there is a value in B then f is onto function.
→ But g may (or) may not be the onto function i.e., so values in B which may doesn't map with A.
 Question 276
Let R and S be any two equivalence relations on a non-empty set A. Which one of the following statements is TRUE?
 A R∪S, R∩S are both equivalence relations. B R∪S is an equivalence relation. C R∩S is an equivalence relation. D Neither R∪S nor R∩S is an equivalence relation.
Engineering-Mathematics       Sets-And-Relation       Gate-2005
Question 276 Explanation:
R∪S might not be transitive.
Let (a,b) present in R and (b,c) present in S and (a,c) is not present in either of them. Then R∪S will contain (a,b) and (b,c) but not (a,c) and hence not transitive.
And equivalence relation must satisfy 3 property:
(i) Reflexive
(ii) Symmetric
(iii) Transitive
But as we have seen that for R∪S, Transitivity is not satisfied.
 Question 277
What is the first order predicate calculus statement equivalent to the following? Every teacher is liked by some student
 A ∀(x) [teacher(x) → ∃ (y) [student(y) → likes (y, x)]] B ∀(x) [teacher(x) → ∃ (y) [student(y) ∧ likes (y, x)]] C ∃(y) ∀(x) [teacher(x) → [student(y) ∧ likes (y, x)]] D ∀(x) [teacher(x) ∧ ∃ (y)[student(y) → likes (y, x)]]
Engineering-Mathematics       Propositional-Logic       Gate-2005
Question 277 Explanation:
Option A: If x is a teacher, then there exist a y such that if y is a student , then y likes x.
Option B: If x is a teacher, then there exists some y, who is a student and like x. (✔️)
Option C: There exists a student who likes all teachers.
Option D: If x is a teacher and then there exists some y, if y is a student then y likes x.
 Question 278
Let P, Q and R be three atomic prepositional assertions. Let X denote (P ∨ Q) → R and Y denote (P → R) ∨ (Q → R). Which one of the following is a tautology?
 A X ≡ Y B X → Y C Y → X D ¬Y → X
Engineering-Mathematics       Propositional-Logic       Gate-2005
Question 278 Explanation:
X: (P∨Q) → R
⇒ ∼(P∨Q) ∨ R
⇒ (∼P∧∼Q) ∨ R
⇒ (∼P∨R) × (∼Q∨R)
⇒ (P→R) ∧ (Q→R)
Option B: X→Y
[(P→R) × (Q→R)] → [(P→R) ∨ (Q→R)]
∼[(P→R) × (Q→R) ∨ (P→R) ∨ (Q→R)]
[∼(P→R) ∨ ∼(Q→R)] ∨ [(P→R) ∨ (Q→R)]
[∼(P→R) ∨ (P→R)] ∨ [∼(P→R) ∨ (Q→R)] ∨ [(Q→R) ∨ (P→R)] ∨ [∼(Q→R) ∨ (Q→R)]
T ∨ [∼(P→R) ∨ (Q→R)] ∨ [(Q→R) ∨ (P→R)] V T
T (✔️)
 Question 279

A bag contains 10 blue marbles, 20 green marbles and 30 red marbles. A marble is drawn from the bag, its colour recorded and it is put back in the bag. This process is repeated 3 times. The probability that no two of the marbles drawn have the same colour is

 A 1/36 B 1/6 C 1/4 D 1/3
Engineering-Mathematics       Probability       Gate 2005-IT
Question 279 Explanation:
 Question 280
If the trapezoidal method is used to evaluate the integral obtained 01x2dx ,then the value obtained
 A is always > (1/3) B is always < (1/3) C is always = (1/3) D may be greater or lesser than (1/3)
Engineering-Mathematics       Calculus       Gate 2005-IT
Question 280 Explanation:
Note: Out of syllabus.
 Question 281
The determinant of the matrix given below is
 A -1 B 0 C 1 D 2
Engineering-Mathematics       Linear-Algebra       Gate 2005-IT
Question 281 Explanation:

determinant = product of diagonal element [upper triangular matrix]
= -1 * 1 * 1 * 1
= -1
 Question 282

Let f be a function from a set A to a set B, g a function from B to C, and h a function from A to C, such that h(a) = g(f(a)) for all a ∈ A. Which of the following statements is always true for all such functions f and g?

 A g is onto ⇒ h is onto B h is onto ⇒ f is onto C h is onto ⇒ g is onto D h is onto ⇒ f and g are onto
Engineering-Mathematics       Set-Theory       Gate 2005-IT
Question 282 Explanation:
g(f(a)) is a composition function which is A→B→C.
If h: A→C is a onto function, the composition must be onto, but the first function in the composition need to be onto.
So, B→C is must be onto.
 Question 283
Let A be a set with n elements. Let C be a collection of distinct subsets of A such that for any two subsets S1 and S2 in C, either S⊂ S2 or S⊂ S1. What is the maximum cardinality of C?
 A n B n + 1 C 2(n-1) + 1 D n!
Engineering-Mathematics       Set-Theory       Gate 2005-IT
Question 283 Explanation:
Consider an example:
Let A = {a, b, c}, here n = 3
Now, P(A) = {Ø, {a}, {b}, {c}, {a,b}, {b,c}, {{a}, {a,b,c}}
Now C will be contain Ø (empty set) and {a,b,c} (set itself) as Ø is the subset of every set. And every other subset is the subset of {a,b,c}.
Now taking the subset of cardinality, we an take any 1 of {a}, {b}, {c} as none of the set is subset of other.
Let's take {2}
→ Now taking the sets of cardinality 2 -{a,b}, {b,c}
→ {b} ⊂ {a,b} and {b,c} but we can't take both as none of the 2 is subset of the other.
→ So let's take {c,a}.
So, C = {Ø, {b}, {b,c}, {a,b,c}}
→ So, if we observe carefully, we can see that we can select only 1 set from the subsets of each cardinality 1 to n
i.e., total n subsets + Ø = n + 1 subsets of A can be there in C.
→ So, even though we can have different combinations of subsets in C but maximum cardinality of C will be n+1 only.
 Question 284
An unbiased coin is tossed repeatedly until the outcome of two successive tosses is the same. Assuming that the trials are independent, the expected number of tosses is
 A 3 B 4 C 5 D 6
Engineering-Mathematics       Probability       Gate 2005-IT
Question 284 Explanation:
Generally which uses a recursion strategy to solve this problem. Other than using recursion we can solve using a formula which we know
The expected number of coin flips for getting n consecutive heads is(2^(n+1) -2)
The expected number of coin flips for getting n consecutive heads is(2^(n+1) -2)
The expected number of coin flips for getting n consecutive same tosses is (2^(n+1) -2) / 2.
where n = 2,
which is (2^(3+1) - 2) / 2 = 3
 Question 285
Let n = p2q, where p and q are distinct prime numbers. How many numbers m satisfy 1 ≤ m ≤ n and gcd (m, n) = 1? Note that gcd (m, n) is the greatest common divisor of m and n.
 A p(p - 1) B pq C (p2 - 1)(q - 1) D p(p - 1)(q - 1)
Engineering-Mathematics       Set-Theory       Gate 2005-IT
Question 285 Explanation:
n = p2q, [p, q are prime numbers]
→ No. of multiples of p in n = pq [n = p⋅p⋅q]
→ No. of multiples of q in n = p2 [n = p2q]
→ Prime factorization of n contains only p & q.
→ gcd(m,n) is to be multiple of p and (or) 1.
→ So, no. of possible m such that gcd(m,n) is 1 will be
n - number of multiples of either p (or) q
= n - p2 - pq + p
= p2q - p2 - pq + p
= p(pq - p - q + 1)
= p(p - 1)(q - 1)
 Question 286
What is the value of