Discrete Mathematics |Gate-2018| previous year questions| Set-3

Discrete Mathematics |Gate-2018|

1. Two people, PP and Q,Q, decide to independently roll two identical dice, each with 66 faces, numbered 11 to 6.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 PP and Q.Q. Assume that all 66 numbers on each dice are equi-probable and that all trials are independent. The probability (rounded to 33 decimal places) that one of them wins on the third trial is _____.[GATE – 2018]

a. 0.022
b. 0.024
c. 0.025
d. 0.026

2. 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? [GATE – 2018]

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.

3. Consider Guwahati (G)(G) and Delhi (D)(D) whose temperatures can be classified as high (H),(H), medium (M)(M) and low (L).(L). Let P(HG)P(HG) denote the probability that Guwahati has high temperature. Similarly, P(MG)P(MG) and P(LG)P(LG) denotes the probability of Guwahati having medium and low temperatures respectively. Similarly, we use P(HD),P(HD), P(MD)P(MD) and P(LD)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)(HG) then the probability of Delhi also having a high temperature (HD)(HD) is 0.40;0.40; i.e., P(HD|HG)=0.40.P(HD|HG)=0.40. Similarly, the next two entries are P(MD|HG)=0.48P(MD|HG)=0.48 and P(LD|HG)=0.12.P(LD|HG)=0.12. Similarly for the other rows.

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

a. 0.61
b. 0.64
c. 0.66
d. 0.67

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

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

Which of the sets above are countable? [GATE – 2018]

a. Q and S only
b. P and S only
c. P and R only
d. P,Q and S only

5. Consider a matrix A=uvTA=uvT where u=(12),v=(11).u=(12),v=(11). Note that vTvT denotes the transpose of v.v. The largest eigenvalue of AA is _____. [GATE – 2018]

a. 3
b. 4
c. 5
d. 6

6. Which one of the following is a closed form expression for the generating function of the sequence {an}, where an=2n+3 for all n=0,1,2,….? [GATE – 2018]

a. 3/(1-x)2
b.  3x/(1-x)2
c. (1-x)
d. 3-x/(1-x)2

7. Consider a matrix P whose only eigenvectors are the multiples of

[1]
[4].

Consider the following statements. [GATE – 2018]

(I)(I)  PP does not have an inverse
(II)(II)  PP has a repeated eigenvalue
(III)(III)  PP 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

8. Let GG be a finite group on 8484 elements. The size of a largest possible proper subgroup of GG is ________. [GATE – 2018]

a. 42
b. 43
c. 44
d. 45