Gate 2010 Math solutions

Q.1. Let G=(V, E) be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree d in G. If S and T are two different trees with $\xi(S) = \xi(T)$, then
(A) |S| = 2|T|   (B) |S| = |T| - 1   (C) |S| = |T|   (D) |S| = |T| + 1

Sol : $\xi(G)$ basically is the sum of degrees of all vertices in a graph. If sum of degrees of two different trees are same, then number of nodes in the trees has to be same. We prove this by induction on sum of degree of all vertices in the two trees.

• Base case : When $\xi(S) = \xi(T) = 1$, then we have only single node in both trees and hence |S| = |T|.
• Induction hypothesis : Assume, for $\xi(S) = \xi(T) = k$, we have |S| = |T|.
• Induction step : For $\xi(S) = \xi(T) = k+1$, we must add a leaf vertex in both trees, and hence |S| = |T|.
So |S| = |T|. So option (C) is correct.

Q.2. Newton-Raphson method is used to compute a root of the equation $x^2 - 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

Sol : We know that, according to Newton-Raphson method, $$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$ In this question $f(x) = x^2-13$, and so $f'(x) = 2x$.
Here current $x_n = 3.5$, $f(x_n) = f(3.5) = -0.75$, and $f'(x_n) = f'(3.5) = 7$. So $$x_{n+1} = 3.5 - \frac{-0.75}{7} = 3.607$$ So option (D) is correct.

Q.3. What is the possible number of reflexive relations on a set of 5 elements?
(A) $2^{10}$   (B) $2^{15}$   (C) $2^{20}$   (D) $2^{25}$

Sol : Consider a table of size 5*5 in which each possible pair is listed. In a reflexive relation, we must include all 5 diagonal elements. So from rest of the 20 elements, we have choice whether to include them or not. So we have $2^{20}$ possible reflexive relations. So option (C) is correct.

Q.4. 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

Sol : We can directly answer this question as "A Group", because other three options require two operations over structure, but let us see whether (S, *) satisfies group properties or not.

• Closure : If we multiply any two elements of S, we get one of three elements of S, so S is closed over *.
• Associativity : multiplication operation is anyway associative.
• Identity element : 1 is identity element of S.
• Inverse element : inverse of 1 is 1 because 1 * 1 = 1, inverse of $ω$ is $ω^2$, because $ω * ω^2 = 1$. Also inverse of $ω^2$ is $ω$, because $ω^2 * ω = 1$
So S satisfies all 4 properties of group, so it is a group. Infact S is an abelian group, because it also satisfies commutative property.
So option (A) is correct.

Q.5. What is the value of $\lim_{n \to \infty}\left(1 - \frac{1}{n}\right)^{2n}$ ?
(A) 0   (B) $e^{-2}$   (C) $e^{-1/2}$   (D) 1

Sol : We know that $\lim_{n \to \infty}\left(1 - \frac{1}{n}\right)^{n} = e^{-1}$, so $$\lim_{n \to \infty}\left(1 - \frac{1}{n}\right)^{2n} = e^{-2}$$. So option (B) is correct.

Q.26. 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 - q)p   (D) pq

Sol : P(declared faulty) = P(actually faulty)*P(declared faulty|actually faulty) + P(not faulty)*P(declared faulty|not faulty) = p*q + (1-p)*(1-q).
So option (A) is correct.

Q.27. What is the probability that divisor of $10^{99}$ is a multiple of $10^{96}$?
(A) 1/625   (B) 4/625   (C) 12/625   (D) 16/625

Sol : Divisiors of $10^{99}$ are of the form $2^a*5^b$, where a and b can go from 0 to 99 each, so there are 10000 divisors of $10^{99}$. Now Any of those divisors would be a multiple of $10^{96}$ if both a and b are atleast 96 i.e. 96, 97, 98, or 99. So each of a and b have 4 choices each, and so there are 16 divisiors which are multiple of $10^{96}$.
So prob = 16/10000 = 1/625, so option (A) is correct.

Q.28. 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

Sol : This can be solved using havel hakimi theorem, which says :

1. First arrange degree sequence in decreasing order.
2. Remove 1st vertex, and let its degree be k, then subtract 1 from next k vertices.
3. If all vertices have degree 0, then answer is yes i.e. given degree seqeunce can be a degree sequence for a graph. If any vertex has degree < 0, then answer is no, otherwise repeat step 2.
So we check each degree sequence given in question :
1. 7, 6, 5, 4, 4, 3, 2, 1. Here first vertex has degree 7, so remove this first vertex, and then subtract 1 from next 7 vertices, so we get 5,4,3,3,2,1,0. Then we get 3,2,2,1,0,0, then 1,1,0,0,0, and then 0,0,0,0. So answer is yes.
2. 6, 6, 6, 6, 3, 3, 2, 2. Here first vertex has degree 6, so remove this first vertex, and then subtract 1 from next 6 vertices, so we get 5, 5, 5, 2, 2, 1, 2. Then we get 4, 4, 1, 1, 0, 2, then 3, 0, 0, -1, 2. Since degree of a vertex becomes negative, this degree sequence is not possible.
Since (II) comes only in option (A) and (D), and since (A) contains I, which is correct degree sequence, (D) must be right answer. We don't need to check for other sequences.

Q.29. Consider the following matrix $$A = \left[\begin{array}{cc}2 & 3\\x & y \end{array}\right]$$ 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

Sol : Characteristic equation for given matrix is $$(2-λ)(y-λ)-3x = 0$$ Putting λ = 4 and 8, we get 2 equations : $$3x+2y = 8$$ $$3x+6y = 48$$ Solving both equations, we get x = -4, y = 10. So option (D) is correct.

Q.30. 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

Sol : The formula ∀x∃y∃t(¬F(x,y,t)) says that for every person x, there exists a person y, and there exists a time t, such that x cannot fool y at time t i.e. No person can fool everyone all the time. So option (B) is correct. Alternatively, you can bring negation outside, thus swapping ∀ and ∃, and so statement becomes ¬(∃x∀y∀t(F(x,y,t)) i.e. there does not exist a person who can fool everyone at everytime, which is again option (B).