Gate 2004 Math solutions

Q.23. Identify the correct translation into logical notation of the following assertion.
"Some boys in the class are taller than all the girls"
Note : taller(x,y) is true if x is taller than y.
(A) (∃x) (boy(x) → (∀y) (girl(y) ∧ taller(x,y)))
(B) (∃x) (boy(x) ∧ (∀y) (girl(y) ∧ taller(x,y)))
(C) (∃x) (boy(x) → (∀y) (girl(y) → taller(x,y)))
(D) (∃x) (boy(x) ∧ (∀y) (girl(y) → taller(x,y)))

Sol : Now many people get confused when to use ∧ and when to use →. This question tests exactly that.
We use ∧ when we want to say that the both predicates in this statement are always true, no matter what the value of x is. We use → when we want to say that although there is no need for left predicate to be true always, but whenever it becomes true, right predicate must also be true.
Now we have been given the statement "Some boys in the class are taller than all the girls". Now we know for sure that there is atleast a boy in class. So we want to proceed with "(∃x) (boy(x) ∧" and not "(∃x) (boy(x) →", because latter would have meant that we are putting no restriction on the existence of boy i.e. there may be a boy-less class, which is clearly we don't want, because in the statement itself, we are given that there are some boys in the class. So options (A) and (C) are ruled out.
Now if we see option (B), it says, every y in class is a girl i.e. every person in class is a girl, which is clearly false. So we eliminate this option also, and we get correct option (D). Let us see option (D) explicitly also whether it is true or not. So it says that if person y is a girl, then x is taller than y, which is really we wanted to say.
So option (D) is correct.

Q.24. Consider the binary relation : $$S = \{(x,y)\vert y=x+1 \text{ and } x,y \in \{0,1,2\}\}$$ The reflexive transitive closure of \(S\) is
(A) \(\{(x,y)\vert y>x \text{ and } x,y \in \{0,1,2\}\}\) (B) \(\{(x,y)\vert y\ge x \text{ and } x,y \in \{0,1,2\}\}\)
(C) \(\{(x,y)\vert y < x \text{ and } x,y \in \{0,1,2\}\}\) (D) \(\{(x,y)\vert y\le x \text{ and } x,y \in \{0,1,2\}\}\)

Sol : Reflexive closure of a relation \(R\) on set \(X\) is the smallest reflexive relation which contains \(R\). So to find reflexive closure of \(R\), we just take its union with set \(\{(a,a) \forall a \in X\}\).
So we are given \(S = \{(0,1),(1,2)\}\). We make it reflexive by taking its union with set \(\{(0,0),(1,1),(2,2)\}\), thus getting reflexive closure \(S_R = \{(0,0),(0,1),(1,1),(1,2),(2,2)\}\).
Now transitive closure is also defined in same way i.e. smallest transitive relation which contains \(S\). So we try to make \(S_R\) transitive now. For this, we have to see where does it violate property of transitivity, and then add appropriate pair. So here we see that we have \((0,1)\) and \((1,2)\), but not \((0,2)\), so we add that to make relation \(S_{RT} = \{(0,0),(0,1),(0,2),(1,1),(1,2),(2,2)\}\). Now we can see that relation \(S_{RT}\) is transitive, so we have found reflexive transitive closure of \(S).
Among the options given, only option (B) matches \(S_{RT}\), so it is the correct answer.

Q.25. If a fair coin is tossed 4 times, what is the probability that two heads and two tails will result ?
(A) \(\frac{3}{8}\) (B) \(\frac{1}{2}\) (C) \(\frac{5}{8}\) (D) \(\frac{3}{4}\)

Sol : By binomial theorem, we have $$P(\text{two heads}) = ^4\text{C}_2*\left(\frac{1}{2}\right)^2*\left(\frac{1}{2}\right)^2 = \frac{6}{16} = \frac{3}{8}$$
So option (A) is correct.

Q.26. The number of different \(n * n\) symmetric matrices with each element being either 0 or 1 is : (Note: Power(2,x) is same as \(2^x\))
(A) power(2,n) (B) power(2,\(n^2\))
(C) power(2,\(n^2+n/2\)) (D) power(2,\((n^2-n)/2\))

Sol : Since we want symmetric matrix, diagonal elements can be anything. So for each of the n diagonal elements, we have 2 choices.
Now number of remaining elements are \(n^2-n\). We can choose half of them, because other half will automatically be decided due to symmetric matrix. So for half of the elements i.e. for each of the \(\frac{n^2-n}{2}\) elements, we have 2 choices. So total number of elements over which we have choice = \(n + \frac{n^2-n}{2} = \frac{n^2+n}{2}\).
So total number of matrices = power(2,\((n^2-n)/2\)).
Hence, option (D) is correct.

Q.27. Let A,B,C,D be \(n*n\) matrices, each with non-zero determinant. if ABCD = I, then B^-1 is
(A) D^-1C^-1A^-1 (B) CDA
(C) ADC (D) Does not necessarily exist

Sol : Since we want to find B^-1, we take inverse on both sides, so we get (ABCD)^-1 = I^-1, which is D^-1C^-1B^-1A^-1 = I. Since we want B^-1, we move other stuff to right side. So first we pre-multiply both sides by (CD), so we get B^-1A^-1 = CD. Now we just post-multiply both sides by A to get desired result i.e. B^-1 = CDA.
So option (B) is correct.

Q.70. The following propositional statement (P → (Q ∨ R)) → ((P ∧ Q) → R) is
(A) satisfiable but not valid   (B) valid <  (C) a contradiction   (D) None of the above

Sol : First we create the truth table for given statement S as :

A formula is satisfiable if there is atleast one assignment for which it is true. Clearly this formula is satisfiable as there are 7 assignments in which it is true. A formula is valid if it is true in all assignments, which is not the case here. So option (A) is correct.

Q.71. How many solutions does the following system of linear equations have?
$$-x+5y=-1, \; x-y=2, \;x+3y = 3$$
(A) infinitely many   (B) two distinct solutions <  (C) unique   (D) None

Sol : Augmented matrix we get from equations is : $$\left( \begin{array}{cc} -1 & 5 \\ 1 & -1 \\ 1 & 3 \end{array} \middle\vert \begin{array}{c} -1\\2\\3\end{array}\right)$$ Now we do row operations to bring left matrix to row echelon form.

\(\left( \begin{array}{cc} -1 & 5 \\ 1 & -1 \\ 1 & 3 \end{array} \middle\vert \begin{array}{c} -1\\2\\3\end{array}\right) \xrightarrow{R2\leftarrow R1+R2} \left( \begin{array}{cc} -1 & 5 \\ 0 & 4 \\ 1 & 3 \end{array} \middle\vert \begin{array}{c} -1\\1\\3\end{array}\right) \xrightarrow{R3\leftarrow R3+R1} \left( \begin{array}{cc} -1 & 5 \\ 0 & 4 \\ 0 & 8 \end{array} \middle\vert \begin{array}{c} -1\\1\\2\end{array}\right) \xrightarrow{R3\leftarrow R3-R2} \left( \begin{array}{cc} -1 & 5 \\ 0 & 4 \\ 0 & 0 \end{array} \middle\vert \begin{array}{c} -1\\1\\0\end{array}\right)\)

Q.72. The following is the incomplete operation table of a 4-element group.

Sol : A group G should follow 4 properties :

1. Closure : result of a * b must be in group G.
2. There must be an identity element i.e. e * a = a * e = a
3. There must be an inverse element b for every element a such that a * b = b * a = e
4. Associativity i.e. (a * b) * c = a * (b * c)

• So from first row, we can conclude that e is identity element of this group, because it gives same element when applied to an element. So we can say c * e = c i.e. we have found first entry of last row.
• Now for rest of the entries, just make use of associative property. For example, if we want to find c * a, just find a * (c*a) because that would be same as (a * c) * a, which we can see from table, is e * a = a. So a * (c * a) = a. Now again from table, we can conclude that c * a must be e.
• Similarly for c * b, find a * (c * b) = (a * c) * b = e * b = b. So a * (c * b) = b. From table, we can see that in row of a, b as result comes only for a * a, so c * b must be a.
• Similarly for c * c, find a * (c * c) = (a * c) * c = e * c = c. So a * (c * c) = c. From table, we can see that in row of a, c as result comes only for a * b, so c * c must be b.

Q.73. The inclusion of which of the following sets into $$S = \{\{1,2\},\{1,2,3\},\{1,3,5\},\{1,2,4\},\{1,2,3,4,5\}\}$$ is necessary and sufficient to make S a complete lattice under the partial order defined by set containment?
(A) \(\{1\}\)   (B) \(\{1\},\{2,3\}\)   (C) \(\{1\},\{1,3\}\)   (D) \(\{1\},\{1,3\},\{1,2,3,4\},\{1,2,3,5\}\)

Sol : A lattice is complete if every subset of partial order set has a supremum and infimum element. For example, here we are given a partial order set S. Now it will be a complete lattice if whatever be the subset we choose, it has a supremum and infimum element. Here relation given is set containment, so supremum element will be just union of all sets in the subset we choose. Similarly, infimum element will be just intersection of all the sets in the subset we choose.

Now as we can see, S now is not complete lattice, because although it has a supremum for every subset we choose, but some subsets have no infimum. For example : if we take subset {{1,3,5},{1,2,4}}, then intersection of sets in this is {1}, which is not present in S. So clearly, if we add set {1} in S, we will solve the problem.

So adding {1} is necessary and sufficient condition for S to be complete lattice. So option (A) is correct.

Q.74. An examination paper has 150 multiple choice questions of one mark each, with each question having four choices. Each incorrect answer fetches -0.25 marks. Suppose 1000 students choose all their answers randomly with uniform probability. The sum total of the expected marks obtained by all these students is
(A) 0   (B) 2550   (C) 7525   (D) 9375

Sol : First we calulate expected marks for 1 question for 1 student. $$E(\text{marks}) = P(\text{correct ans})*\text{marks for correct ans} + P(\text{wrong ans})*\text{marks for wrong ans} = \frac{1}{4}*1 + \frac{3}{4}*\left(\frac{-1}{4}\right) = \frac{1}{16}$$ So Expected marks for all students for all questions = \(1000*150*\frac{1}{16} = 9375\).
So option(D) is correct.

Q.75. Mala has a colouring book in which each English letter is drawn two times. She wants to paint each of these 52 prints with one of k colours, such that he colour pairs used to colour any two lwtters are different. Both prints of a letter can also be coloured with the same colour. What is the minimum value of k that satisfies this requirement ?
(A) 9   (B) 8   (C) 7   (D) 6

Sol : This question is slightly ambigous. So first let us understand what question is asking. So in a book, we have letters A-Z and each letter is printed twice, so there are 52 letters. Now we have to color each letter, so we need a pair of colors for that, because each letter is printed twice. Also in a pair, both colors can be some. Now condition is that a pair of colors can't be used more than once.

So suppose Mala has 3 colors : Red, Blue, Green. She can color as follows : (A,A) : (Red,Red), (B,B) : (Blue,Blue), (C,C) : (Green,Green), (D,D) : (Red,Blue), (E,E) : (Red,Green), (F,F) : (Blue,Green).
Now we don't have more pairs of colors left, we have used all pairs, but could color only 6 letters out of 26. So question is to find minimum no. of colors, so that we could color all 26 letters.

So if Mala has k colors, she can have k pairs of same colors, thus coloring k letters, then \(^k\mathrm{C}_2\) other pairs of colors, thus coloring \(^k\mathrm{C}_2\) more letters.
So total no. of letters colored = \(k + ^k\mathrm{C}_2 = k + \frac{k(k-1)}{2} = \frac{k(k+1)}{2}\).
So we want \(\frac{k(k+1)}{2} \ge 26\) i.e. \(k(k+1) \ge 52\), so \(k \ge 7\), so option (C) is correct.

Q.76. In an M * N matrix such that all non-zero entries are covered in a rows and b columns. Then the maximum number of non-zero entries, such that no two are on the same row or column, is
(A) ≤a+b   (B) ≤max(a,b)   (C) ≤min(M-a,N-b)   (D) ≤min(a,b)

Sol : Suppose a < b, for example let a = 3, b= 5, then we can put non-zero entries only in 3 rows and 5 columns. So suppose we put non-zero entries in any 3 rows in 3 different columns. Now we can't put any other non-zero entry anywhere in matrix, because if we put it in some other row, then we will have 4 rows containing non-zeros, if we put it in one of those 3 rows, then we will have more than one non-zero entry in one row, which is not allowed.

So we can fill only "a" non-zero entries if a < b, similarly if b < a, we can put only "b" non-zero entries. So answer is ≤min(a,b), because whatever is less between a and b, we can put atmost that many non-zero entries.

So option (D) is correct.

Q.80. A point is randomly selected with uniform probability in the X-Y plane within the rectangle with corners at (0,0), (1,0), (1,2) and (0,2). If p is the length of the position vector of the point, the expected value of p² is
(A) \(\frac{2}{3}\)   (B) 1   (C) \(\frac{4}{3}\)   (D) \(\frac{5}{3}\)

Sol : Here minimum value of p can be 0 (if point chosen is (0,0), then length of position vector will be 0), and maximum value can be \(\sqrt{5}\) when point chosen is (1,2), because that is the farthest point from origin, and length of position vector then will be \(\sqrt{1^2 + 2^2} = \sqrt{5}\). So p can vary from 0 to \(\sqrt{5}\).
Now we know that $$ E(p^2) = \int^\sqrt{5}_0 p^2*P(p)\,dp $$ Since p is a uniform random variable, \(P(p) = \frac{1}{\sqrt{5}-0} = \frac{1}{\sqrt{5}}\)
So $$ E(p^2) = \frac{1}{\sqrt{5}}\left[\frac{p^3}{3}\right]^{\sqrt{5}}_0 = \frac{5}{3} $$ So option (D) is correct.