# Gate 2003 Math solutions

Q.3 Let P(E) denote the probability of the event E. Given P(A) = 1, P(B) = 1/2, the values of P(A|B) and P(B|A) respectively are
(A) 1/4,1/2  (B) 1/2,1/4   (C) 1/2,1  (D) 1,1/2

Sol : Assuming A and B are exhaustive events i.e. P(A U B) = 1, we have P(A $\cap$ B) = P(A) + P(B) - P(A $\cup$ B) = 1 + 0.5 - 1 = 0.5.
Now P(A|B) = $\frac{P(A,B)}{P(B)}$ = 0.5/0.5 = 1, and P(B|A) = $\frac{P(A,B)}{P(A)}$ = 0.5/1 = 0.5.
So option (d) is correct.

Q.4 Let A be a sequence of 8 distinct integers sorted in ascending order. How many distinct pairs of sequences, B and C are there such that (i) each is sorted in ascending order, (ii) B has 5 and C has 3 elements, and (iii) the result of merging B and C gives A?
(A) 2   (B) 30   (C) 56   (D) 256

Sol : For B, if we simply pick any 5 elements from A in the same order in which they appear, and put remaining in C, we will statisfy all 3 conditions.
So question reduces just to find number of ways to choose 5 elements of 8 elements, which is just $^8\mathrm{C}_5 = 56$. So option (c) is correct.

Q.5. n couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of different gatherings possible at the party is
(A) $^{2n}\mathrm{C}_n*2^n$   (B) $3^n$   (C) $\frac{(2n)!}{2^n}$   (D) $^{2n}\mathrm{C}_n$

Sol : For every couple, there can be 3 possibilities - (i) Husband accompanied by wife, (ii) wife accompanied by husband, (iii) wife accompanied by someone else. Note that "Husband not accompanied by wife" is not possible as given in question. Since there are n couples, so total number of gatherings = $3^n$. So option (b) is correct.

Q.31. Let (S, ≤) be a partial order with two minimal elements a and b, and a maximum element c. Let P: S $\to$ {True, False} be a predicate defined on S. Suppose that P(a) = True, P(b) = False and P(x) $\Rightarrow$ P(y) for all x, y $\in$ S satisfying x≤y, where $\to$ stands for logical implication. Which of the following statements CANNOT be true?
(A) P(x) = True for all x $\in$ S such that x ≠ b
(B) P(x) = False for all x $\in$ S such that x ≠ a and x ≠ c
(C) P(x) = False for all x $\in$ S such that b ≤ x and x ≠ c
(D) P(x) = False for all x $\in$ S such that a ≤ x and b ≤ x

Sol : First, we understand the meaning of question. So in question, we are given a partial order, which means all elements may not be related with each other. Now a and b are given as minimal elements, and c as maximum element, so hasse diagram looks something like this.

Now we have a function P, which associates with each element either True or False. So in question, element a is assigned True, and element b to be False. Moreover, if x≤y i.e. if there is an upward edge from x to y in hasse diagram, then formula P(x) $\Rightarrow$ P(y) holds. So for example, all elements x which have an edge from element a, have to be True, because a is true i.e. P(a) = True and since there is an edge from a, they have to satisfy formula P(a) $\Rightarrow$ P(x), which can only be done by setting P(x) = True. Moreover, elements which have an edge from b can be anything, because anyway formula P(b) $\Rightarrow$ P(x) is satisfied because of P(b) = False.
Now we see options one by one, and check which one cannot be true.

• Option (A) : This can be true, because making all elements true trivially satisfy formula P(x) $\Rightarrow$ P(y).
• Option (B) : This can also be true, if all elements are connected from b, then as we saw, they can be anything, in particular, they all can be false.
• Option (C) : This can also be true, infact, it is exactly the case we saw in option (B)
• Option (D) : This can't be true, because if an element has an edge from both a and b, then it has to true (as we discussed earlier).

So option (D) is correct.

Q.32. Which of the following is a valid first order formula? (Here $\alpha$ and $\beta$ are first order formulae with x as their only free variable)
(A) ((∀x)[α] ⇒ (∀x)[β]) ⇒ (∀x)[α ⇒ β]
(B) ((∀x)[α] ⇒ (∃x)[α ∧ β]
(C) ((∀x)[α ∨ β] ⇒ (∃x)[α]) ⇒ (∀x)[α]
(D) (∀x)[α ⇒ β] ⇒ ((∀x)[α]) ⇒ (∀x)[β])

Sol : A formula is valid if it is always whatever be the truth assignment of predicates. The best way to do these type of questions is by example. Take predicates α and β to some simple English sentences and then understand the meaning of the formula.
So let α : "Person is employed", and β : "Person is salaried".
So now let us see each option what does it mean.

• (A) : "If it is true that if every person is employed, then only every person gets salary, then it implies that every employed person gets salary". This is clearly not true, because first statement only tells about scenario when every person is employed, but it doesn't say anything if some are employed and some not. So we can't say from first statement that if a person is employed, then he gets salary.
• (B) : "If every person on this planet is employed, then it implies that there must be a person who is both employed and salaried". This is clearly false, no need for explanation.
• (C) : If it is true that if every person on this planet is either employed or salaried, then there is an atleast one person who is employed, then this whole thing implies that all persons are employed". This is also false, because it may happen that only one person is employed.
• (D) : "If every person who is employed also gets salary, then this implies that if every person is employed, then every person also gets salary". This is true, because if every person is employed, then because of given first sentence, it means every person aloso gets salary.

So option (D) is correct.

Q.33. Consider the following formula and its two interpretations $I_1$ and $I_2$.
$\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right]$
$I_1$ : Domain: the set of natural numbers
$P_x$ = 'x is a prime number'
$Q_{xy}$ = 'y divides x'
$I_2$ : same as $I_1$ except that $P_x$ = 'x is a composite number'.
Which of the following statements is true?
(A) $I_1$ satisfies $\alpha$, $I_2$ does not   (B) $I_2$ satisfies $\alpha$, $I_1$ does not
(C) Neither $I_1$ nor $I_2$ satisfies $\alpha$   (D) Both $I_1$ and $I_2$ satisfies $\alpha$

Sol : First of all, note that, in $\alpha$, $\neg Q_{yy}$ is always false, because every number divides itself. Also not that rightmost formula $(\forall x)\left[\neg P_x\right]$ is always false, because clearly it is not the case that every number is not the prime number (in case of $I_1$), nor it is the case that every number is not the composite number (in case of $I_2$). Also note that, variable x in this expression is not same as variable x in leftside expression, they are independent. In fact, we can rewrite $\alpha$ as $\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall z)\left[\neg P_z\right]$.
Let us consider $I_1$ first. So let us assign some value to x, and see if it satisfies $\alpha$. We can partition assignments of x into 3 parts : when x is prime, when x is composite, when x is 1.

1. When x is prime : $P_x$ is true, also $Q_{xy}$ is false for all y except 1, because only 1 divides x. So formula $Q_{xy} \Leftrightarrow \neg Q_{yy}$ is true for all y except 1, but due to $\forall y$ outside this, whole formula $\forall y\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]$ becomes false, because it would have been true if $Q_{xy} \Leftrightarrow \neg Q_{yy}$ was true for every y.
So now $\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right]$ becomes false for all x whenever x is prime.
2. Since for some x (where x is prime), $\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right]$ is false, so $(\forall x) \left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right]$ is definitely false, since false$\Rightarrow$ false is true, so $\alpha$ is true in $I_1$, and we don't need other cases of x.

Now consider $I_2$. Here also we can argue in the same way as we did in cases of $I_1$, here case of x being composite leads to false$\Rightarrow$false, and so $\alpha$ is also true in $I_2$, hence option (D) is correct.

Q.34. m identical balls are to be placed in n distinct bags. You are given that m ≥ kn, where k is a natural number ≥ 1. In how many ways can the balls be placed in the bags if each bag must contain at least k balls?
(A) $\left( \begin{array}{c} m - k \\ n - 1 \end{array} \right)$   (B) $\left( \begin{array}{c} m - kn + n - 1 \\ n - 1 \end{array} \right)$   (C) $\left( \begin{array}{c} m - 1 \\ n - k \end{array} \right)$   (D) $\left( \begin{array}{c} m - kn + n + k - 2 \\ n - k \end{array} \right)$

Sol : This is very simple application of stars and bars. If you haven't read stars and bars before, please read here . Since we want atleast k balls in each bag, so first we put kn balls into bags, k balls in each bag. Now we are left with m - kn balls, and we have to put them into n bags such that each bag may receive 0 or more balls. So applying theorem 2 of stars and bars with m - nk stars and n bars, we get number of ways to be $\left( \begin{array}{c} m - kn + n - 1 \\ n - 1 \end{array} \right)$. So option (B) is correct.

Q.37. Let $f : A \to B$ be an injective (one-to-one) function. Define $g : 2^A \to 2^B$ as:
$g(C) = \{f(x) | x \in C\}$, for all subsets C of A.
Define $h : 2^B \to 2^A$ as: $h(D) = \{x | x \in A, f(x) \in D\}$, for all subsets D of B. Which of the following statements is always true?
(A) $g(h(D)) \subseteq D$   (B) $g(h(D)) \supseteq D$   (C) $g(h(D)) \cap D = \phi$   (D) $g(h(D)) \cap (B - D) \ne \phi$

Sol : First we understand what these functions mean. So $f$ is a function from set $A$ to set $B$. Let these sets be $A = \{1,2\}$, and $B = \{3,4,5\}$, and let the mapping is $\{(1,3),(2,4)\}$. Note that since this is not an onto function, we can have an element (here 5), which doesn't have a preimage. Now $g$ is a function, which takes a set (which is a subset of A) as input, and gives another set (which is a subset of B) as output, such that the output set contains all images of elements in input set. For example, $g(\{1\}) = \{3\}$. On the other hand, $h$ is a function which takes a set (which is a subset of B) as input, and gives another set of preimages of all elements in input set. For example, $g(\{3,5\}) = \{1\}$.
Now let us see $g(h(D))$, which is common in all options. So for example, let $D = \{3,5\}$, so $g(h(D)) = g(h(\{3,5\})) = g(\{1\}) = \{3\}$, which is clearly a subset of $D$, so we see that result is subset of $D$, and this will always be the case, because since function is one-one, we can't have 2 preimages of an element, and thus cannot come up with extra elements than D after applying function $g$.
So option (A) is correct.

Q.38. Consider the set $\{a, b, c\}$ with binary operators $+$ and $*$ defined as follows.

 + a b c a b a c b a b c c a c b
 * a b c a a b c b b c a c c c b
For example, $a + c = c, c + a = a, c * b = c$ and $b * c = a$. Given the following set of equations:
$(a * x) + (a * y) = c$
$(b * x) + (c * y) = c$
The number of solution(s) (i.e., pair(s) (x, y) that satisfy the equations) is
(A) 0   (B) 1   (C) 2   (D) 3

Sol : We see in $1^{st}$ equation that '+' of two things must become c, so we see in '+' table when can we get c as result. We have three options : $(a+c), (b+c)$, and $(c+b)$. So we choose one option at a time, and see which one fits into both equations.

1. $(a+c)$ : So we have $(a*x) = a$ and $(a*y)=c$. Looking into '*' table, we find $x=a, y=c$. Now putting these values of $x$ and $y$ into $2^{nd}$ equation gives us $(b*a)+(c*c) = b+b = b$, so this solution doesn't satisfy both equations.
2. $(b+c)$ : So we have $(a*x) = b$ and $(a*y)=c$. Looking into '*' table, we find $x=b, y=c$. Now putting these values of $x$ and $y$ into $2^{nd}$ equation gives us $(b*b)+(c*c) = c+b = c$, so this solution satisfies both equations.
3. $(c+b)$ : So we have $(a*x) = c$ and $(a*y)=b$. Looking into '*' table, we find $x=c, y=b$. Now putting these values of $x$ and $y$ into $2^{nd}$ equation gives us $(b*c)+(c*b) = a+c = c$, so this solution also satisfies both equations.
So 2 pairs of (x,y) satisfy both equations. So option (C) is correct.

Q.41. Consider the following system of linear equations $$\left( \begin{array}{ccc} 2 & 1 & -4 \\ 4 & 3 & -12 \\ 1 & 2 & -8 \end{array} \right) \left( \begin{array}{ccc} x \\ y \\ z \end{array} \right) = \left( \begin{array}{ccc} \alpha \\ 5 \\ 7 \end{array} \right)$$ Notice that the second and the third columns of the coefficient matrix are linearly dependent. For how many values of α, does this system of equations have infinitely many solutions?
(A) $0$   (B) $1$
(C) $2$   (D) $3$

Sol : We write the augmented matrix as :$$\left( \begin{array}{ccc} 2 & 1 & -4 \\ 4 & 3 & -12 \\ 1 & 2 & -8 \end{array} \middle\vert \begin{array}{c} \alpha\\5\\7\end{array}\right)$$ Now we do row operations to bring left matrix to row echelon form.
$\left( \begin{array}{ccc} 2 & 1 & -4 \\ 4 & 3 & -12 \\ 1 & 2 & -8 \end{array} \middle\vert \begin{array}{c} \alpha\\5\\7\end{array}\right) \xrightarrow{R2\leftarrow R2 - 2R1, R3\leftarrow R3 - 0.5R1} \left( \begin{array}{ccc} 2 & 1 & -4 \\ 0 & 1 & -4 \\ 0 & 1.5 & -6 \end{array} \middle\vert \begin{array}{c} 0.5\alpha\\5-2\alpha\\7-0.5\alpha\end{array}\right) \xrightarrow{R3\leftarrow R3 - 1.5R2} \left( \begin{array}{ccc} 1 & 0.5 & -2 \\ 0 & 1 & -4 \\ 0 & 0 & 0 \end{array} \middle\vert \begin{array}{c} 0.5\alpha\\5-2\alpha\\2+1.5\alpha\end{array}\right)$

Now for infinitely many solutions, we must have $2+1.5\alpha = 0$ i.e. $\alpha = -4/3$, so for only 1 value of $\alpha$, this system has infinitely many solutions. So option (B) is correct.

Q.42. A piecewise linear function f(x) is plotted using thick solid lines in the figure below (the plot is drawn to scale).

If we use the Newton-Raphson method to find the roots of $f(x)=0$ using $x_0, x_1,$ and $x_2$ respectively as initial guesses, the roots obtained would be
(A) 1.3, 0.6, and 0.6 respectively   (B) 0.6, 0.6, and 1.3 respectively
(C) 1.3, 1.3, and 0.6 respectively   (D) 1.3, 0.6, and 1.3 respectively

Sol : First of all, There is a mistake in coordinates of a given point. I have corrected that in red color.

Now in Newton-Raphson method, we draw a tangent from our guess point, and our new guess would be the point where this tangent cuts x-axis. Now we choose initial guess points one by one :

• $x_0$ : Tangent at this point is line AB itself, and that would cut x-axis at point $(1.0,0.0)$ (found using equation of line AB). So our next guess would be $1.0$. Point on the curve corresponding to this new guess 1.0 is shown as F. Now tangent at point F is line DE, which cuts x-axis at $1.3$, and at this point, value of function is zero, so we found the root as $1.3$.
• $x_1$ : Tangent at this point is line BE, which cuts x-axis at $0.6$, also function value is zero here, so we find root as $0.6$.
• $x_2$ : Tangent at this point is line CD, which cuts x-axis at $1.05$ (again found by finding equation of line CD). Point on the curve corresponding to this new guess 1.05 is shown as G. Now tangent at point G is line DE, which cuts x-axis at $1.3$, and at this point, value of function is zero, so we found the root as $1.3$.

So option (D) is correct.

Q.61. : In a permutation $a_1 ... a_n$, of n distinct integers, an inversion is a pair $(a_i, a_j)$ such that $i < j$ and $a_i > a_j$. If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of $1. . . n$?
(A) $\frac{n(n-1)}{2}$   (B) $\frac{n(n-1)}{4}$
(C) $\frac{n(n+1)}{2}$   (D) $2n[log_2n]$

Sol : Let $X_{ij}$ be an indicator random variable s.t. $$X_{ij} = \begin{cases} 0 &\mbox{if } (a_i,a_j) \text {not inverted} \\ 1 & \mbox{if } otherwise. \end{cases}$$ Let random variable $X$ denotes total number of inversions. So clearly $X=\sum\limits_{\substack{i,j \\ i<j}}X_{ij}$. Note that their are $^n\mathrm{C}_2$ terms in summation, because there are total $^n\mathrm{C}_2$ pairs, and each pair is either inverted or not.
So now we want to find $E(X)$. Now $E(X)=\sum\limits_{\substack{i,j \\ i<j}}E(X_{ij})$. But $E(X_{ij}) = \frac{1}{2}$, because for any pair, probability of inversion is same as of not inversion.
So $E(X) = \frac{^n\mathrm{C}_2}{2} = \frac{n(n-1)}{4}$.
So option (B) is correct.

Q.62. What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of $1. . . n$ with at most n inversions?
(A) $\Theta(n^2)$   (B) $\Theta(nlogn)$
(C) $\Theta(n^1.5)$   (D) $\Theta(n)$

Sol : In insertion sort, whenever we swap two values, some inversions are destroyed, also no new inversions are created, since smaller element comes at lower index in array. The no. of inversions destroyed is exactly the number of comparisons done before that swapping. So for every comparison, there is an inversion destroyed. Since there are at most n inversions initially, so in at most n comparisons, array will be sorted. So worst time complexity is $\Theta(n)$. So option (D) is correct.

Q.72. The following resolution rule is used in logic programming.
Derive clause (P ∨ Q) from clauses (P ∨ R), (Q ∨ ¬R)
Which of the following statements related to this rule is FALSE?
(A) ((P ∨ R) ∧ (Q ∨ ¬R)) ⇒ (P ∨ Q) is logically valid.
(B) (P ∨ Q) ⇒ ((P ∨ R)) ∧ (Q ∨ ¬R)) is logically valid.
(C) (P ∨ Q) is satisfiable if and only if (P ∨ R) ∨ (Q ∨ ¬R) is satisfiable.
(D) (P ∨ Q) ⇒ FALSE if and only if both P and Q are unsatisfiable.

Sol : option (A) itself is definition of resolution. So option (A) is correct.