Gate Cse PDF
Gate Cse PDF
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
i|t' fa€
ffi
T,T
3
C
$-*-d*
q.-JETgL I I
Dis(rete and Engineering
Mathematics
Contents
1.
2.
3.
4.
5.
6.
7.
Discrete and Engineering
Mathematics
Syllabus :
Mathematical Logic: Propositional and first order logic.
Set Theory & Algebra: Sets, relations, functions, partial orders and lattices. Groups.
Combinatorics: Counting, recurrence relations, generating functions.
Graph Theory: Connectivity, matching, coloring.
Probability: Random variables. Uniform, normal, exponential, poisson and binomial distributions. Mean, median,
mode and standard deviation. conditional probabiiity and Bayes theorem.
Linear Algebra: Matrices, determinants, system of linear equations, eigenvalues and eigenvectors, LU
decomposition.
Calculus: Limits, continuity and differentiability. Maxima and minima. Mean value theorem. lntegration.
t.t Indicate which of the foliowing well-formed 1.8 Let a, b, c, d be propositions. Assume that the
formula are valid: equivalence a e> O v - b) andb e c hold. Then
(a) ((P
^
+ Q)
= (Q
= R)) (P
= R) the truth-value of the formula (a r. b) -+ (a n c) v d
&) (P=Q)=(-P+-Q) is always
(c) (Pn(-PV-Q))=+Q (a) True
(d) ((P R) v (Q R)) ((P v Q)) R). (b) False
= = = =
(c) Same as the truth-value of b
[1990:2 Marks]
(d) Same as the truth-value of d
1.2 Which of the following predicate calculus
[2000:2 Marks]
statements is/are valid
(a) (Vx) P(x)v(Vx) Q(x) -+ (vx) {P(x) v Q(x)} 1.9 What is the converse of the following assertion?
&) (lx) P(x),^. (lx) Q(x) + (lx) {P(x) n Q(x)} I stay only if you go
(c) (lx) {P(x) v Q(x)} -+ (vxlp(x) v (vx) Q(x) (a) I stay ifyou go
(d) (lx) {P(x) v Q(x)} -+ - (vx) (b) If I stay then you go
[1992: l Mark] (c) Ifyou do not go then I do not stay
(d) If I do not stay then you go
1.3 Which of the following is/are tautology:
[2001: l Mark]
(a) (avb)-+(bnc) &) (a,rb)-+ftvc)
(c) (a v b) --+ ft -+ c) (d) (a + b) -+ (b -+ c) 1.10 Consider two well-formed formulas in
[1992:1Mark] propositional logic
Fr:P=-P
1.4 The proposition p n (- p v q) is Fr: (P = -P) v (-P
(a) a tautology (b) <+ (p q) = P)
" Which of the foilowing statements is correct?
(c) <+ (p v q) (d) acontradiction
(a) F, is satisfiable, F, is valid
[1993: l Mark]
@) F, is unsatisfiable, F, is satisfiable
1.5 Let p and q be propositions. Using only the (c) F, is unsatisfiable, F, is valid
truth table decide whether p <+ q does not (d) F, and F, are both satisfiable
imply p -e - q is true or false. [2001: l Mark]
[1994:2 Marks] 1.11 "If X then Y unless Z" is represented by which of
1.6 If the proposition - p = q is true, then the the following formulas in propostional logic?
truth value of the proposition - p v (p = q), ("-") is negation, "rr" is conjunction, and "-+" is
where - is negation, 'v'. is inclusive or and '=' is implication)
implication, is (a) (X n-Z) -+Y O) (X "Y) -+-Z
(a) true (b) multiple valued (c) X + ff n-Z) (d) (X -->Y) n-Z
(c) false (d) cannotbe determined 12002: l Markl
[1995:2 Marks] L.12 Which of the following is a valid first order
1.7 Which one of the following is false? Read n as formula? (Here u and B are first order formulae
AND, v as OR, - as NOT, -+ as one way with x as their only free variable)
implication and ++ as two way implication. (a) ((vx) [g] (vx)[B]) (Vx) [cr+
(a) ((x -+ y) x) -+ y
= = 0]
^
&) ((- x -+ y) ^ (- x -+ - y))+ x
(b) (Vx) [u]
= (lx) [cx " 0]
(c) (Vx) [u" B ] (3x) [u]= (Vx) [a]
(c) (x -r (x., y)) =
(d) ((x v y) e+ (- x --> - y))
($ rvx) frv=B =(Vx) [ct]=(Vx) [F])
1
1.13 Consider the following formula s and its two l.l7 Let p, q, r and s be four primitive statements.
interpretations I, and Ir. Consider the following arguments:
u: (Vx) [P* <+ (Vy) [Q*, <+ - Qyy]l P: [(-pvq) n (r -+ s) n (pvr)] -+ (-s -+ q)
+ (Vx) [-P*] Q: [(-pnq) ^ [q -+ (p -+ r)]l -+ -r
Ir: Domain : the set of natural numbers R: [[(q,^.r) -+ p] (-qvp)l -+ r
' P" ='x is a prime number' S: [pn(p -+ r) ,r^(q v -r)] -+ q
Q*, ='Y divides x' Which of the above arguments are valid?
Ir: Same as I, except that P, ='x is a composite (a) P and Q only (b) P and R only
number.' (c) P and S only (d) P, Q, R and S
Which of the following statements is true? 12004 :2 Marksl
(a) I, satisfies cx, I, does not
1.18 The following propositional statement is
ft) I, satisfies cr, 11 does not (P -+ (Q v R)) -+ ((P a Q) -+ R)
(c) Neither I, nor I, satisfies u
(a) satisfiable but not valid
(d) Both I, and I, satisfy cr (b) valid
[2003:2 Marks] (c) a contraditiction
L.74 The following resolution rule is used in iogic (d) None of the above
programming: Derive clause (P v Q) from 12004:2 Marksl
clauses (P v R), (Q v - R) 1.19 Let P, Q and R be three atomic propositional
Which of the following statemnets related to this assertions. Let X denote (? v Q) -+ R and Y denote
rule is FALSE? (P -+ R) v (Q -+ R). Which one of the following is
(a) (P v R)"(Q v - R) =+ (P v Q) is logicaily valid a tautologl'?
@) (P v Q) = (P v R)n (Q v - R) is logically valid (a) X=Y (b) X-+Y
(c) (P v Q) is satisfiable if and onlf if (P v R) n (c) Y--+X (d) -Y+X
(Q v - R) is satisfiable [2005:2 Marks]
(d) (P v Q)
= FALSE if and only if both P and Q l.2O What is the first order predicate calculus
are unsatisfiable
statement equivalent to the following? Every
[2003:2 Marks] tcacher is liked by some student
1.15 Identify the correct translation into logical (a) V(x) [te4cher (x) -+ 3 (y) [student (y) -+ likes
notation of the following assertion. Some boys in 6', x)ll
the class are taller than all the girls (b) V(x) [teacher (x) -+ ! (y) [student (y) n likes
Note: Taller (x, 5z) is true if x is taller than y. (y, x)ll
(a) (=x) (boy(x) -+ (Vy) (Sirl(),) n taller (x, y))) (c) l(y) V(x) [teacher (x) -+ [student (y) ,^.likes
(b) (lx) (boy(x) a (Vy) (gir](y) n taller (x, y))) (y, x)ll
(c) (:x) (boy(x) -+ (Vr) (girl(),) --> taller (*, y))) (d) V(x) [teacher (x) n 3 (y) [student (y) -+ likes
(d) (rx) &oy(x) ,r (Vy) (girl(y) -+ taller (x, y))) (y,
")ll
12004: l Markl [2005:2 Marks]
1.16 Let a(x, y), b(x, y,) and c(x, y) be three statements L.zl Let P(x) and Q(x) be arbitrary predicates. Which
of the following statements is always TRUE?
with variables x and y chosen from some
universe. Consider the following statement: (a) (vr(P(r) v Q(r))) + ((vrcP(r)) v (vrQ(r)))
(lr)(Vy) (b) (vr(pfx) + e(r))) ((vrp(r)) (vre(r)))
[(o( x, )) ^ b(x, y)),r -c(r..,,)] = =
(c) rvr(p(r) (vre(r)))) + (vr(p(x) g(r)))
Which one of the follovi'ing is its equivalent? = =
(d) (vr(p(r)) <= (vre(r))) (vx(p(r) <+ e(r)))
(a) ( Vr) (:y) [(:a(x, y') v b(x , y\) -+ c(x , y)) =
UT-2005 :2 Marksl
0) (!r)(vy)l(a(x,y)v b(x,y)) a - c(r,y)l
L.22 Consider the following first order logic formula
(c) -(Vr)(ly)[(o(r,y) n b(x, y))-+ c(r,1,)] in which R is a binary relation symbol.
(d) -(VrXly)Ua(x,y) v b(r,y)) -+ c(r:,.i,)l VrVy (R(x,y)a R(y,x))
IIT-2004: 1 Markl The formula is
MADE EASY I Discrete and Engineering Mathernatics ls
(a) satisfiable and valid represent the statement; "Not every graph is
ft) satisfiable and so is its negation connected'?
(c) unsatisfiairle but its negation is vaiid (a) - Vx (Graph(x) Connected (x))
=
(d) satisfiable but its negation is unsatisfiable &) I " (Graph(x) n- Connected (x))
IIT-2006 : 2 Marksl (c) - Vx (- Graph(x) v Connected (x))
(d) Yx (Graph(x) Connected (x))
L.23 Which one of the first order predicate calcuius =-
1200'i :2 Marksl
statements given below correctly expresses the
following English statement'r) L.27 Which of the following is TRUE about formulae
Tigers and lions attack if they are hungry or in Conjunctive Normal Form?
threatened. (a) For any formula, there is a truth assignment
(a) Vx [(tiger (x) n lion (x)) -+ {(hungry (x) v for which at least haif the clauses evaluate to
threatened (")) -+ attacks (x))l true.
&) v" [(tiger (x) v Iion (x)) -+ {(hungry (x) v &) For any formula, there is a truth assignment
threatened (x)) r. attacks (x)}l for a which all the clauses evaluate to true.
(c) Vx [(tiger (x) v lion (x)) -+ {(attacks (x) --> (c) There,is a formula such that for each truth
(hungry (x) v Threatened (x)))l assignment at most one-fourth of the clauses
(d) Vx [(tiger (x) v lion (x)) -+ {(hungry (x) v evaluate to true.
threatened (x)) -+ attacks (x)}l (d) None of the above
[2006:2 Marks] 12A07 :2 Marksl
1.24 Consider the follorving propositional statements: 1.28 Which one of these first-order logic formulae is
P1: ((A n B) --> C)) = ((A -+ C) n (B -+ C)) valid?
P2: ((Av B) -+ C)) = ((A-+ C) v (B + C)) (a) v x(P(x) + Q(x)) ((v xP(x)) + (v xQ(x)))
=
Which one of the following is true?
&) :x(P(x) " Q(x)) .+ ((3x P(x)) = (ixQ(x)))
(a) P1 is a tautoiogy. but not P2
(c) lx(P(x),r Q(x)) <+ ((3x P(x)) ,^. (lxQ(x)))
(0) P2 is a tautology, but not P1
(c) P1 and P2 are both tautologies (d) v xly P(i, y) = 3y v x P(x, y)
(d) Both P1 and P2 are not tautologies , tIT-2007:2Marksl
[2006:2 Marks] t.29 Let fsa and pda be two predicates such that fsa(x)
1.25 Aiogical binary relation O, is defined as follows:
means x is a finite state automaton, and pda(y)
means, that y is a pushdown automaton. Let
A B A3B equivalent be another predicate such that
True True True equivalent (a, b) means a and b are equivalent.
True False True Which of the following first order logic statement
False True False represents the following:
False False True Each finite state automaton has an equivalent
pushdown automaton.
Let - unary negation (NOT) operator, with
be the
higher precedence, than O. Which one of the
(a) (Vx fsa(x)
= (ly pda(y)n equivalent (x,y))
(b) -Vy(lx fsa(x) =+ pda(y)nequivalent (x,y))
following is equivalent to A n B?
(c) Vx !y (fsa(x) r. pda(y) n equivalent (x,y))
(a) (-AoB) (b) -(Ao-B)
(d) Vx (fsa(y) n pda(x) n equivalent (x,y))
(c) -(-Ae-B) (d) -(^"AoB) =y
[2008:1Mark]
[2006:2 Marks]
1.30 Which of the following first order formulae is
L.26 Let Graph (x) be a predicate which denotes that
Iogically valid? Here a(r) is a first order formula
x is a graph. Let Connected (x) be a predicate
with x as a free variable, and p is a first order
which denotes that x is connected. Which of the
formrr.Ia with no free variable.
following first order logic sentences DOES NOT
6! GATE PreviousYears Sotved Papers: [$ | MADE EASY
1.39 What is the correct translation of the following 1.44 Which one of the following Boolean expressions
statement into mathematical logic? is NOT a tautology?
"Some real numbers are rational" (a) ((a -+ b) n(b + c)) -+ (a -+ c)
(a) 3x (real (x) vrational (x))
&) + (- b -+ (a nc))
(a e+ c)
. &) Vx (real (x) -+ rational (x))
(c) 3x (real (x) n rational (x))
(c) (anbnc)+(cva)
(d) lx (rational (x) -+ real (x)) (d) a+(b-+a)
[2012:1Mark] [2014 (Set-2):2 Marks]
1.40 What is the logical translation of the foilowing 1.45 Consider the following statements:
statements? P: Good mobile phones are not cheap
"None of my friends are perfect." Cheap mobile phones are not good
Q:
(a) 3 r (F(r) n- P(x))
L: Pimplies Q
&) lr(-F(r)rP(x)) M: implies P
Q
(c) 3 r (- F(r) n'- P{x))
(d) -3r(F(r),^,P(x))
N: P is equivalent to Q
[2013 : 2 Marks] Which one of the following about L, M, and N is
CORRECT?
L.4L Which one of the following is NOT logically (a) OnIy L is TRUE (b) Only M is TRUE
equivalent to -3x(V1, (a) nV z(0)) (c) OnIyNis TRUE (d) L,MandNareTRUE.
(a) Vx(-z(-p) -+ Vy(ct)) (Set-3):1Mark]
[2014
(b) Vx{Vz(81-+ !y(-&)) o'not
L.46 The CORRECT formula for the sentence,
(c) Vx(Vy(cr) -+ :z(-9))
a1l rainy days are cold" is
(d) Vx(ly(-o) v Iz(-B))
(a) vd(Rainy (d)r.^-Cold (d))
[2013:2 Marks]
(b) vd(-Rainy (tJ) -+ Cold (d))
1.42 Consider the statement
"Not all that glitters is gold" (c) ld(-Rainy (d) -+ CoId (d))
Predicate glitters(x) is true if r glitters and (d) ld(Rainv (d),.. - Cold (d))
predicate gold(r) is true if ris gold. Which one of
the following logicalformulae represents the above [2014 (Set-3):2 Marks]
statement? L,47 Which one of the following is Not equivalent to
(a) Vx : giitters(x) +-gold(x) peq?
(b) Vx : gold(x) +glitters(r) (a) (-p v e) ,r (p v -q)
(c) 3x : gold(x) r, -glitters(x) (b) (-p v s) n (q -+ p)
(c) (-p n q) v (p n -q)
(d) lx : glitters(x) n -gold(x)
(d) (-p n -q) v (p q)
[201a (Set-l): l Mark] "
[2015 (Set-l):1Mark]
L,43 Which one of the following propositional logic
formulas is TRUE when exactly two of p, q, and 1.48 The binary operator * is defined by the foilowing
r are TRUE? truth table.
(a) ((p e+ q) nr) v(pr.qn - r) p g p*q
0 n 0
(b) (- (p e q) r.r) v(pnqn - r) U 1 1
1 1 0
(d) (- (p o q) nr) n (pnqr, - r)
Which one of the following is true about the
[2014 (Set-l):2 Marks] I.)
8i GATE Previous Years Solved Papers : !$ | MADE EASY
(a) Both commutative and associative "The result of the loss ls head if and orulv if
(b) Commuiative but not associative I ctm telling the truth."
(c) Not commutative but associative Which of the follow-ing options is correct?
(d) Neither commutative nor associative
r2o1b(set-l):2Marksr 3] Ii:;:::i:i:f,]*
L.49 Consider the following two statements. (c) If the person is of Type 2, then the result is
51: If a candidate is known to be corrupt. then tail
he will not be eiected. (d) If the person is of Type 1, then the result is
52: If a candidate is kind . he will be elected. tail
Which one of the following statements follows [2015 (Set-3): l Mark]
from 51 and 52 as per sound inference rules of
logic? 1.52 Letp, q, r, s represent the followingpropositions.
(a) If a person is known to be corrupt, he is kind p .r i8, 9, 10, 11, 12)
O) If a person is not known to be corrupt. he q r is a composite number
is not kind r is a perfect square
(c) If a person is kind, he is not known io be s r is a prime number
corrupt The integer r 2 which satisfies ((p q)
(d) if a person is not kind. he is not known to ( r s)) is _.
be corrupt [2016 (Set-1): l Marks]
Mark]
[2015 (set-2) : I
,.u, conside. the forowing expr.essions:
1.50 which one of the following well formed formulae 0 false (ii) g
is a tautology? (il) true (iv) P @
(a) :r ,r,.R(r, 1) j, r -R(r, i') (v) -Q P
@) t 'Iyfi(.r,,r) S(.r,:,)]) -r y,S(r.1,) The number ofexpressions given above that are
(c)lr,v(P(r,:,) R(r,.r))l irr(P(r,r)fi(r,i,))l logicaily.impliedbyP(P Q)is_.
(d) r 'r, P(r. j) r 1'P(y. r) [2016 (Set-2): l Marks]
[2015 (Set-2) : 2 Marks] 1.54 Which one of the following well-formed formulae
1.b1 In a room there are only two types of people, in predicate caiculus is Nor valid?
namelyTypelandType2.Typelpeoplealwa5,s (a) ( rp(r) xq(x)) ( x p(x) xq(x))
tellthetruthandType2peoplealwaysiie.you &) ( rp(r) xq(x)) x(p(x) q(x))
give a fair coin to a person in that room, without
knorving which type he is from and tell him to (c) x(p(x) q(r)) ( rp(r) xq(x))
toss it and hide the result from vou t,lyou ask (d) x(p(x) q(x)) ( x p(x) xq(x))
for it. Upon asking, the person replies the
following [2016 (Set_2):2 Marks]
= a'b'+ bc
Therefore, ((a v b) -+ Now since -p -+ e is given true, we reduce the
& n c)) is contingency and
not tautology. truth table as follows
O) (a.^, b) + (b v c) p q
-P)Q
=ab-+b+c 0 1 1
:(ab)'+b+c 1 0 1
=a'+b'+b+c 1 1 1
' @:r€)
a e+ True
Q,, = "y divides y" is always true
So a is true, i.e. a = 1 .'. Q*v e - Q,, is same as Q*, <+ False
' b<+cholds.Sob=c Now cr becomes
Now the given expression is (Vx)[P(x) <+ (Vy)(Q*re+ false)]
(a r. b) -+ ((a n c) v d) (a .b)+((a .c) + d)
= +(Vx) [-P(x)]
Putting a = 1in above expression we get
Now consider I, : P(x) = "x is a prime number".
1 'b -+ ((1 .c) + d)
u becomes
=b-+c+d (Vx x is a prime number if and only if Vy (y
=b'+c+d does not divide x))
Now putting b = c in above expression we get = (Vx) x is not prime.
which means that x is a prime number if and
=c'+c+d=1+d=1 only if no number divides x implies that no
So the expression is always true.
number is prime.
=
l
@'(a}
@&I
X:(PvQ)--rR
The statement is "some boys in the class are taller Y:(P+R)v(Q-+R)
than a1lthe girls". X: P + Q -+ R= (P + Q)' + R = P' Q' + R
So the notation for the given statement is Y: (P'+ R) + (Q'+ R) = P'+ Q'+ R
(lx) &oy(x) n (Vy) ($r1(-!) + taller (x, y))) Clearly X * Y
Considel X -+ Y
E'{o = (P'Q'+ R) +
(P'+ Q'+ R)
Choice (c) is
= (P'Q'+ R)'+ P'+ Q'+ R
-(Vr)(ly)[(o(x, y) n b(x, y)) -+ c(x, y)] = (P'Q)'
.R'+ P'+ Q'+ R
= -(Vr)(ly)[o n b -+ c] = (P + Q) .R'+ P'+ Q'+ R
@rrr RHS:
(A+C)r.(B+C)
Consider choice (b)
(vr(P(x) = (A',+ C) (B',+ C)
= Q(:r))) = ((vrP(r)) = (VrQ(x))) = A'B'+ C
Let the LHS of this implication be true Clearly, LHS * RHS
'This means that P, is not a tautology
P,+Q, Pr: ((A v B -+ C)) = ((A -+ C)'r (B + C))
Pz+Q, LHS = (A+B-+C)
:
= (A+B)'+C
Pr+Q, = A'B'+ C
Now we need to check if the RHS is also true. RHS = (A+C)v(B+C)
The RHS is ((VrP(r)) = (VrQ(r))) = (A',+ C) + (B',+ C)
To check this let us take the LHS of this as
= A'+ B'+ C
true Clearly, LHS * RHS =+ P" is aiso not a tautology.
i.e. takeVrP(r) to be true. This means that Therefore, both P, and P, are not tautologies.
(P1, Po,...P.) is taken to be true. Now P, aiong Correct choice is (d).
with P, + Q, will imply that Q, is true. Similarly
P, along with Pr; Q, will imply that Q, is true.
@tar
I3y using rnin terms we can define
And so on...
Therefore (Qi, Q2,...Q,) all true. AiaB=AB+AB'+A'B'
i.e. VrQ(r) istrue. Thereforethe statement @)
=A+A'B'
- (A+A) (A+B)-.{+B'
is a i':rlic1 lileclicii'c statement.
(a) -AOB=A'eB=A'+B'
@tnr (b) ^- (Ae -B) = (Ar.:) B')' =(A+ (B')')' - (A + B)'
_ A/fi/
Since a relation may or may not be symmetric, -Art
the given predicate is satisfiable but not val,id. (c) - (-A C "'B) ='(A'G.) B')'= (A' + (B')')'= (A'*
So (a) is clearly faise.
B)'= AF'
Whenever a predicate is satisfiable its negation
(d) - (-Ae B) = (A'e B)'= (A'+ B')'=A.B=A
also is saiisfiable. So option (b) is the correcr
ans\,ver.
nB
.'. Only, choice (d) = A 2,. B
ffitar Note: This problem can also be done l;y
constructing truth table for each choice and
The given statement should he read as
comparing with truth table for A r. B.
"If an animal is a tiger or a 1ion, then (if the
animal is hungry or threatened, then it
will attack). Therefore the coruect translation is
@rul
The statement "Not every graph is connected" is
Vx [(tiger (x) v lion (x)) -+{(rungry (x) v threatened
same as "There exists some graph which is not
(x)) +attacks (x))l
connected" which is same as
which is choice (d). Ix {graph (x) ,r - connected (x)}
@ur Which is choice (b)
By boolean algebra we can see that option (a) and
Pr: ((A n B) -+ C)) = ((A -+ C) n (B -+ C))
(c) are same as (b). Only option (d) is not the
LHS:
(A,^. B) -+ C same as (b).
Infact option (d) means that "aII graphs are not
=AB-+C
: (A B)'+ C connected".
= A'+ B'+ C
MADE EASY I Discrete and EnEineering Mathematics 113
(iir) (P"Q)v(Pn-Q)"(-P"-Q)
Nor,r'putting n = 1, 2, . . .; rve get 712, 314, 718 ...
= pq + pq'+ p'q'
Ail cf these propciriions are Z ll2 and so choice p(q + q') + p'q'
(a) atleasi haif of the ciauses evaluate to true, is
=
= p+p'q'
'ihe ccrrrect answer. (p+p')(p+q')
=
=p+q'
(iv) (P n Q) v (P -Q) v (-P n Q)
Option (a) is a standard one way distributive "
= pq + pq'+ p'q
property of predicates. ' =p(q+q')+p'q
@It"l = p+p'q
"For x which is an fsa, there exists a ;z which is = (p+p')(p+q)
a pda and which is equivalent to x."
=p+q
Cleariv (i), (iil and (iii) are equivalent. Correct
(Vx fsa(x) =+ (Iy pda(y) n equivalent (x, y)) is the
choice is (b).
logical representation.
@or
The correct translation of "Gold and silver
Option (c) is
ornaments are precious" is choice (d)
[(!r, o(r)) -+ 0]-+ [Vx,u(x) -+ B] Vx((G(x)vS(x))+P(x))
Let us check the validity of this predicate. which is read as "if an ornament is gold or silver,
Let the LHS of this predicate be true. then it is precious".
This means that some tx -+ p. Now since a given ornament cannot be both gold
Let uu -+ P and silver at the same time.
Now we wiil check if the RHS is true. The RHS
Choice O) Vx((G(x) n S(x)) -+ P(x)) is incorrect.
is [Vr,cr(r) -+ B] to check this implication let us
take Vr,u(r) to we true. @tur
This means that all the u are trr' e. It means The given table can be converted into boolean
that cx" is also true. function by adding minterms corresponding to
true rows.
14 I
GATE PreviousYears Solved Papers: !p I MADE EASY
q
PIQ
TIT -p
TiF Ciearly I, is correct since it is in the form of Modus
FIT Tollens (rule of contrapositive)
Iz:p=q
Since there is only one false in the above truth -p
tab1e, rn'e can represent the function p = Q more -q
efficientel5r, in conjunctive normal form.
Translates Pi-:Q = P + Q'(the max-term
which corresponds [p = q "- p]
=- q
@rar @ro
Not (all rainy days are cold):
(a) glitters(x) + -gold(x)
Vx
All glitters are not gold - (vd (Rainy (d) -+ Cotd (d)))
&) V.r gold(x) = glitters(.r) =- (Vd (- Rainy (d) v Cold (d)))
All golds are glitters : id (Rainy (dh - Oold (d))
(c) f, gold(x) r, - glitters(x)
Alternate Method
There exist gold which is not glitter i.e. not Not all rainy days are cold is same as some rainy
all golds are glitters. days are not cold which is same as
(d) 1r glitters(r) r - gold(x)
ld (Rainy (d)n.- Cotd (d))
Not all that glitters is gold i.e., there exist
some which glitters and which is not gold.
Et"l
@rur Here, option (a) and (b) can be reduced to (p -+
q) n (q -+ p) and hence = p <+q
Option O) is (- (p ++ q) n r) v (p n qn - r) Option (d) is p'q'+ pq = p <+ q,
= ((p @ q) r) + pqr' Option (c) is p'q * pq' = p @ q which is not
= (pq'+ p'q) r * pqr' equivalenttopoq.
= pq'r * p'qr * pqr'
= pqr'* pq'r * p'qr
This is exactly the min-term form of a logical
@t'l
formula which is true when exactly two variables
The given truth table corresponds to p'q * pq'
are true (oniy p, q true or only p, r true or only q, =p@q.
r true). @ is known to be both commutative and
associative.
@,rnr
(ae+c)+(-b-+(anc)) @t"l
: (a e+ c)'+ &'-+ ac) C Person is corrupt
= (a @ c)' + (b'-+ ac) K Person is kind.
=ac'+a'c*b+ac E Person is elected
= a(c'* c) + a'c + b s1 : C-+E
=a*a'c*b=a+c+b s K-+E
which is not a tautology.
s2
= E-+K.
@'.t*l So from S, and Sz : (C-+E) (E-+R)
g: mobile is good ^ =
C-+R
c : mobile is cheap
We can conclude C + K which is same as
P: Good mobile phones are not cheap
K -+ e , which is same as option (c).
g)c'=(g'+c')
Q: Cheap mobile phones are not good @'t*t
c-+g'=(c'+g') Since P -+ R = -P v R, and the quantifiers on
.'. Both P and Q are equivalent. both the sides are same (Vr 3y) .
Option (c) is clearly a tautology.
16! GATE Previous Years Solved Papers : EEI I MADE EASY
@rut @sol.
Type 1 always tells tri-rth. p^Lp =+ q\ = pQt' + q\ = PO.
= (p=+q) = 0 ...(1) :
2.1 State whether the foliowing statement are TRUE (c) (goh)2 - 82 ohz for: every g, h e G.
or FALSE: (d) G is offinite order
The union of two equivalence relations is also an [1994:2 Marks]
equivalence relation.
2,8 Let R be a symmetric and transitive relation on
[1987: l Mark] a set A. Then
2,2 (a) How many binary relations are there on a (a) R is reflexive and hence an equivalence
setAwithnelements? relation
(b) How many one-to-one functions are there (b) R is reflexive and hence a partial order
from a set A with n elements onto itself. (c) R is reflexive and hence not an equivalence
[1987:1Mark] relation
(d) None of the ahove
2.3 The complement(s) of the eiement'a'in the lattice
l Mark]
[1995:
shown in figure is (are) ..."..
1 2.9 The number of elements in the power set P(S) of
the set S = {(0), 1, (2, B)} is:
(a) 2 (b) .1
are exactly 97 functions from X to Y. From this 2.18 The number of equivalence relations on the set
one can conclude that {1, 2, 3, 4} is
(ul lxl =r, lYi=sz (a) 15 (b) 16
(b) ixl=e7,lYl =r @) 2a (d) 4
(c) lXl =gz, lYl =sz [1997:1Mark]
' (d) Noneof theabove
[1996:1 ]Iarkl z.Lg Suppose A is a finite set with n elements. The
number of elements in the Largest equivaience
2.14 tr&ich of the following statements is false?
(a) The set of rational numbers is an abelian relation ofA is
group under addition (a) n &) n2
(b) The set of integers in an abelian group under (c) 1 (d) n+1
addition [1998: l Mark]
(c) The set of rational numbers form an abelian
2.20 Let R, and R, be two equivalence relations on a
group under multiplication
set. Consider the following assertions:
(d) The set of real numbers excluding zero in an
abelian group under multiplication
(i) Rr u R, is.an equivalence relation
l Mark] (ii) R1n R, is an equivalence relation
[1996:
Which of the following is correct?
2.75 Let R denote the set of real numbers. Let
(a) both assertions are true
f : R x R -+R x Rbe atrijective function defined
by f(x. y) = (x * y, x - y). The inverse function of
(b) assertion (i) is true but assertion (ii) is not
fis given by true
r 1 ,1) (c) assertion (ii) is true but assertion (i) is not
(a) f-r(x,y)=l-,-r true
\x+y x-y) (d) neither (i) nor (ii) is true
&) f*1(x, y) = (x - y, x + ), [1998:1Mark]
. (x+y *_y)
(c) f -1(x.Y) = 2.21 The number of functions from an m element set
r.2
|
2) to an n element set is
(d) f-1(x, y) = (2(x - y), 2(x + y))
(a)m+n, (b)m"
[1996:2 Marks] (c) n- (d) m*n
2.L6 Let R be a non-empty relation on a collection of [1998:1Mark]
sets defined by ARB if and only if A n B= Q. Then,
2.22 The binary relation R = {(1, 1), (2, 1), (2,2), (2,
(pick the true statement)
3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4)) on the set
(a) R is reflexive and transitive
A =tl,2,3.4)is
(b) R is symmetric and not transitive
(a) Reflexive, symmetric and transitive
(c) R is an equivalence relation
(d) R is not reflexive and not symmetric @) Neither reflexive, nor irreflexive but
transitive
[1996:2 Marks]
(c) Irreflexive, s5zmmetric and transitive
2.17 Which one of the following is false? (d) Irreflexive and antisymmetric
(a) The set of all bijective functions on a finite [1998:2 Marks]
set forms a group under function composition.
(b) The set {1, 2, ..., p - 1} forms a group under 2.23 Suppose A = {a, b, c, d} and fI, is the following
multiplication mod p where p is a prime partition ofA
number. rI, = {{a, b, c}, {d}}
(c) The set of all strings over a finite alphabet X (a) List the ordered pairs of the equivalence
forms a group under concatenation. relations induced by fI,
(d) A subset s + S of G is a subgroup of the group ft) Draw the graph of the above equivalence
(G, x) if and only if for any pair of elements relation
a,b€s,a*b-1es. [1998:2 Marks]
[1996:2 Marks]
MADE EASY I Discrete and Engineering Mathematics lle
2.34 Let (S, <) be a partial order ivith two minitnal 2.38 In a class of 200 students, 125 students have
elements a and b, and a maximum eiement c. taken Programming Language course, 85
Let P : S + {Tlue. Fa}se} be a predicate definecl students have taken Data Structures course, 65
on S. Suppose that P(a) = True, P(b) = False sturients have taken Computer Organization
and P (x) + P(y) for atrl x, y e S satisfvingx <y,
course; 50 -"iudents have taken bcih
Prcgramming Language and Data Stri-rctures,
where sta-nds for logical implication. Which of
= 35 students have taker: both Data- Structures and
the follow-ing statements CANNOT be true?
Computer Organization; 30 students have taken
(a) P (x) = T'Lue for aII x eS such that x * tr
both Data Structures and ComPuter
(b) P (x) = False for all x e S such that x + a and
Organization, 15 students have takcn all the
x#c three courses. How many students hrr,'e trot
(c) P (x) = False for allx eS suchthatb <x such taken any ofthe three courses?
thatxlc (a) 15 (h) 20
(d) P (x) = False for all x eS such that a < x and (c) 25 (d) 30
b<x UT-2004 : 1 l\Iarkl
[2003:2 Marks]
2.39 Let R, be a relation from A = {1, 3, 5,7} toB= {2,
A.OU Consider the set {a, b. c} with binary operators + 4, 6, 8) and R, be another relation lrom B to
and x defined as follows : C = {1, 2,3.4} as defined below:
f+T,
ttl
t-;l I;T,- b-; (i) An element x in A is relaied to an element
;, in B (under Rr) if x + 3r is divisible by 3.
luiu a c: loiu b.i
lol, r, .l iu]r, . ,l
(ii) An element x in B is related to an element
r,' in C (under Rr) if x + y is even but not
1.1". oll.l. " r,
divisible by 3.
For example, a * c = c, c * a = a, c x b Which is the composite relation R,R, fi:om A
=candbxc=a. to C?
Given the following set of equations: (a) RrRr=l(1, 2), (7,4), (3, 3), (5, 4), (7, 3)l
(axx)+(axy)=s 1b) RrRr={(1,2), (1,3), (3, 2), (5,2), (7, 3)}
(bx*)+(cxy)=c (c) RrRr={(1, 2), (3, 2), (3, 4), (5,4), (7,2)i
The number of solution (s) (i.e., pair (s) (x, 5) that (d) RrRr={(S, 2), (3, 4), (5, 1), (5, 3), (7, 1)}
satisfies the equations) is IIT-2004: l Markl
(a) o (b) 1 2.40 The following is the incomplete operation table
(c) 2 (d) 3 of a 4-element group.
[2003:2 Marks]
e a b C
[2004:2 Marks]
lo b dl
I
I
.I
2.42 LetA, B and C be non-empty sets anci let X =
[oo Ll
where a, b, c, d, e and f are real numbers and
(A- B) - C andY= (A- C) - (B- C) abc * 0. Under the matrix multiplication
Which one of the followingis TRUE? operation, the set H is
(a) X=Y &) XcY (a) a group
(c) YcX (d) None of these ft) a monoid but not group
[2005:1Mark] (c) a semigroup but not a monoid
2.43 The following (d) neither a group nor a semigroup
is the Hasse diagram of the poset
[{a, b, c, d,e}, <] [2005:2 Marks]
2.48 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 a1l ae A. Which of
the following statements is always true for all
The poset is
such functions f and g?
(a) not a lattice
(a) g is onto + h is onto
@) a lattice but not a distributive lattice (r) h is onto f is cnto
(c) a distributive iattice but not a
=
(c) h is onto + g is onto
Boolean algebra (d) h is onto + f and g are onto
(d) a Boolean algebra
IIT-2005 :2 Marksl
[2005: l Mark]
2.49 Let A be a set with n elements. Let C be a
2.44 The set {1,2, 4,'7,8,77,13,14} is a group under collection ofdistinct subsets ofA such that for
multiplication modulo 15. The inverses of 4 and
any two subsets S, and S, in C, either S, c S, or
7 are respectively
S, c S' What is the maximum cardinality of C?
(a) 3 and 13 (b) 2 and 11 (a) n (b) n+1
(c) 4 and 13 (d) 8 and 14 (c) 2n-1 +l (d) n!
[2005: l Mark] [IT-2005:2 Marks]
2.45 Let R and S be any two equivalence relations on 2.50 For the set N of natural numbers and a binary
a non-empty set A. Which one of the following
operation f : N x N -+ N, an element ze N is
statements is TRUE?
called an identity for f, if f(a, z) = a - f(2, a), for
(a) R n S, R u S are both equivalence relations
e N. \44dch of the following binary operations
a-ll a
G) R u S is an equivalence relation have a identity?
(c) R n S is an equivalence relation
(d) Neither R u S nor R n S is an equivalence
I. f(x, Y) = x*Y - 3
II. f(x, y) = max(x, y)
relation
III.f(x, Y) = xY
[2005:2 Marks] (a) I and II only @) II
and III only
2.46 Let f: B -+ C and g: A -+ B be two functions and (c) I and III only (d) None of these
let h = f o g. Given that h is an onto function. IIT-2006: l Markl
Which one of the following is TRUE?
(a) f and g should both be onto functions 2.51 Let, X, Y,Zbe sets of sizes x, y and z respectively.
(b) f should be onto but g need not be onto Let W = X x Y and E be the set of all subsets of
(c) g should be onto but f not be onto W. The number of functions fromZ to E is
both f and g need not be o"floou
(a) z b) zx 2xv
(c) 2' (d) 2*Y'
:2 Marksl
[2006: l Mark]
22l' GATE Previous Years Solved Papers : lft I MADE EASY
The set {1,2, 3, 5.7, 8,91 under multiplication 2.57 What is the cardinality of the set of integers X
modulo 10 is not a group. Given below are four defined below? a = {nl1 < n < L23, nis not
possibie reasons, S4:ich one ofthem is false? divisible by 2, 3 or 5)
(a) It is not closed (a) 28 (b) 33
(c) 37 (d) 44
@) 2 does not have an inverse
(c) 3 does not have an inverse [IT-2006 : 2 Marks]
($ 8 does not have an inverse 2.58 Let S be a set of n elements. The number of
[2006: l Mark] ordered pairs in the largest and the smallest
equivalence relations on S are
A relation R is defined on ordered pairs ofintegers
(a) n and n (b) n2 and n
as follows: (x, y)R(u,v ) if x < u and y > v. (c) n2 and 0 (d) n and 1
Then R is [2007:1Mark]
(a) Neither a Partial Order nor an Equivalence
Consider the set S = {a, b, c, d}. Consider the
Relation
following 4 partitions lt t.Ttz.lt'.TE4,on
ft) A Partial Order but not a Total Order
(c) A Total Order S: ri, = 1aUcI1,nr{"b,.a}, n, = 1abc, d},
(d) An Eqnivalence Relation
[2006:1Mark] n, = ii,U,a,a1
Let the partial order on the set ofpartitions
< be
2.54 Let E, F and G be finite sets. S' = (nr,nr, nr,na) defined as follows: n, < nrif
LetX=(EnF)-(FnG)and and only if n, refines r,. The poset diagram for
Y=(E-(EnG))"-(E-F). (s" <) is
Which one of the following is true? nrT nl
(a) X cY
nrl
@) X:Y (a) (b) n,
X=Y
I
(c) -l/r3 I
(d) X-Y *A andY -X+A
,rl
I
rts
[2006:2 Marks]
2.55 Let S = {!,2,3,..., ffi}, m > 3. Let X,
X2, ..., X' be subsets of S each of size 3. Define a (c) n,
function f from S to the set of natural numbers
as, f(i) is the number of sets X, that contains the
n, ll4
element i. That is f(i) = lfi li. X,tl.
m 12007 z2 Marksl
Then ) f(i) is ofnatural
1=l 2.60 A partial order P is defined on the set
(a) 3m @) 3n numbers as follows. Here x/y denotes integer
(c) 2m+1 (d) 2n+ 1 division.
[2006:2 Marks]
(r) (0, 0) e P.
(ii) (a, b) eP if and only if ao/ol0 < b %10 and
2.56 Let P, Q and R be sets let A denote the symmetric (ai 10, b/10) e P.
difference operator defined as PAQ = (P u Q) - Consider i;he following ordered pairs:
(P n Q).UsingVenn diagtams, determine which (il (101, 22) (ii) (22, 101)
of the following is/are TRUE? (iii)(145,265) (iv) (0, 153)
I. PA (Q n R) = (PA Q) n (PAR)
Which of these ordered pairs of natural numbers
tr. P n (Q A R) - (P n Q) I (P n R)
are contained in P?
(a) I only (b) II only (a) (i) and (iii) (b) (ii) and (iv)
(c) Neither I nor II (d) Both I and II (c) (i) and (iv) (d) (iii) and (iv)
UT-2006: 2 Marksl IIT-2007:2 Marksl
MADE EASY I Discrete and Engineering Mathematics
123
2,6L If P, Q, R are subsets of the universal set (.a) 210 (b) 2t5
U, then (P n Q n R) u (P"n Q n R) u e"u R.is (c) 220 (d) zz;
(a) Q"u R" &) Q"uR" Pt [2010: l Mark]
(c) P"uQ"uR. (d) U
Consider the set S = {1, rrl, c02}, where ro and ro2
[2008: l Markl
are cube roots of unity. If 'r denotes the
2.62 Consider the following Hasse diagrams. multiplication operation, the structure {S, x}
oo80
'V
(i) (,,) (iii)
Which all of the above represent a lattice?
(iu)
2.68
forms
(a) a group (b) a ring
(c) an integral domain (d) a field
[2010:
How many onto (or surjective) functions are there
l Mark]
(a) (i) and (iv) only (b) fiil and (iii) onty from an n-element (n > 2) set to a 2-element set?
(c) (iii) only (d) (i), (ii) and (iv) only (a) 2 &) 2"- 1
[IT-2008: 2 Marks] (c) 2 -2 (d) 2(2-2)
2.63 Which one of the following is NOT necessarily a 12012:2 Marksl
property of a Group? 2.69 Abinary operation @ on a set of integers is defined
(a) Commutativity as x @ y = x2 + y2. Which one of the following
(b) Associativity
statements is TRUE about @?
(c) Existence of inverse for every element (a) Comrnutative but not associative
(d) Existence of ideptity (b) Both commutative and associative
[2009: l Mark] (c) Associative but not commutative
2.64 Consider the binary relation: R = {(x, y), (x, z), (d) Neither commutative nor associative
(z,x), (2, y)) on the set {x, y, z}. Which one of the [2013: l Mark]
following is TRUE? 2.70 Let S denote the set of aIl functions
(a) R is symmetric but NOT antisymmetric
f : {0,1}a -+ {0,1} . Denote by N the number of
(b) R is NOT symmetric but antisymmetric
functioris from S to the set {0, 1}. The value of
(c) R is both symmetric and antisymmetric
log, logrN is
(d) R is neither symmetric nor antisymmetric
[2014(Set-l):2Marks]
[2009: l Mark]
2.7L --.
Consider the following relation on subsets of the
2.65 For the composition table of a cyclic group shown
set S of integers between 1 and 2014. For two
below:
distinct subsets U and Yof S we say U < V if
I
abcd the minimum element in the symmetric
;-t-;-a
I
-1
f -1(S r., T) = f-1(S) n r-1(t) 2.78 Suppose L= tp, e, r, s,l) is a lattice represented
. by the following Hasse diagram:
12014 (Set-3):1Markl
2.73 Let G be a group with 15 elements. Let Lbe a
subgroup of G. It is known that L + G and that /t\
'\ l'
;-..
!['Sot. @sot.
A relation is said to be equivalence relation is The complement of an element x is x' iff
(, Reflexive LUB of x and x' is 1 (greatest element) and GLB
(iil Symmetric, and of x and x' is 0 (least element).
(iii) Transitive .'. The complement of the element 'a' in the
Union of two reflexive relations and two lattice =.[b. c, d, e].
symmetric reiations are reflexive and symmetric
respectively. However, union of two transitive @s"t.
relations need not to be transitive. Therefore, The relation have (1, 2) (2, 3) then add (1, 3) to
union of two equivalence relations need not be relation. Since relation have (2, 3) (3, 4) then add
an equivalence relation. (2, 4) to relation.
Example: So the resuitant relation is
Let R, and R, on set A = {1. 2. 3 } = {(1, 2), (2, 3), (3, .1), (5, 4).(1, 3), (2, 4)}
R, = {(1, 7), (2, 2,'), (3, 3) (1, 2), (2, 1)} is an Now the resultant relation have (1, 2) (2, 4) then
equivalence relation add (1. 4) to the relation
R, = {(1, l),(2,2). (3, 3), (2,3), (3, 2.t} is an .'. {(1,2), (2,3). (3,4), (5,4), (1,3), (2,4), (1,4)}
equivalence relation So the transitive closure ofthe relation is
R, u R, = {(1, 1), (2, 2), (3, 3,), (1, 2), (2, 7), (2, 3), = l(7,2), (2,3), (3,4), (5,4), (1,3), (2,4). (1,4)|
(3, 2)) is not an equivalence relation,
because (7,2) & (2,3) needs (1,3) eiementtobe Et"l
in transitive relation. S=SruSruSru...uS,.
For S to be infinite set, atleast one of sets S, must
@sot. be infinite, since if all S, were finite, then S wiil
(a) Set A contain n elements. Every sutrset of A also be finite.
x A is a binary relation on the set A.
Number of binary relations on a set A with Etul
Number of elements in A x A = n2
n elements = 2n'
.'. Number of elements in the power set of A x A
(b) Number of one-to-one functions from a set
A with m-elements to a set B with n- -
.)rr
elements is nP-.
So the number of one-to-one functions from
a set A with n-elements to itself is nPn = nl.
MADE EASY I Discrete and Engineering Mathematics
lt27
@@t {a)'
(g"h)2 = (goh)o(goh) (A-B)u(B-A)u(AnB)
Since group is abelian so it is commutative as Representing above set using Venn diagram as
well as associative. follows.
= go(hog)h A:-B
- go(goh)oh :l:
ByVenn diagram,
E,tui (A- B) u (B -A) u (A rl B) :Au B
A relation which is symmetric and transitive,
need not be reflexi-,,e reiation.
(,
R = { }; on the set A = {a, b}. The relation R is
@tur
x = {2. B. 6. 12. 2l}
symmetric and transitive but not reflexive. The Hasse diagram of (x. <) is
(ii) R = {(a, a), (b, b)}; on the set A - {a, b}.
The relation ii i. .y^*"tric, transitive ' '124
and
also reflexive.
i,,
I
4
,,=r4
"2 t
4
_
JI
4l
_1
Total=1+7+6+1=15
Alternate Method So tire number of equivalence relations on the
Given f(x, y) = ((x + y), (x - v)) set {1, 2, 3, 4} is 1 5.
Take some random ordered pair say (2, 3)
f(2, 3) = ((2 + 3), (2 - 3;1 = (5, -1) @tti
A is a finite set r,vith n elements. The largest
Now the correct inverse must map (5, -1) back
equivalence relation of A is the cross-product
io (2, 3).
A x A and the number cf elements in the cross
Trying the options one'by-one we find that oniy productAxAisn2.
option (c) maps (5, -1) to (2, 3).
@t"l
@<ur A relation is said to be equivalence relation if
(i) Reflexive relation is
AnA=A+0 (1.) Reflexir-e
So; (A, A) doesn't belongs to reiation R. (ii) S1'mmetric
.'. Relation R is not reflexive.
(iii) Transitive
(ii) Syrnmetric
Reflexive and symmetric properties are both closed
IfA n B - g then B n A = S is aiso true
.'. relation R is symmetric relation. underu&n.'
(iii) Transitive Transitive property is closed under n but not u.
IfAn B - q and B n C = 0, it need not be Sc equivalence relations are closed under n but
truethatAnC=0. not u.
For example: Therefore R, n R, is an equivalence relation but
A = {1, 2},8= {3, 4}, C = {1, 5, 6} R, u R, is not necessarily an equivalence relation.
An B -Q andBn C -SbutAn C = {1} *O
.'. Relation R is not transitive relation. @,,tol
The number of functions from an m element set
Eto In option (c), the set of a1i strings over a finite
to an n element set is nm.
@sot. @sor.
Given partition of A is (a) According to Mr. X if xRy, is in relation then
&= [(r. b. c). (d)i yRx also in relationbecause of symmetricity.
(a) The ordered pairs of the equivalence Now because R is transitive, xRy and yRx
relations induced by ru, is implies xRx.
R = (a, b, c) x (a, b, c) u (d) x(d) FIaw in Mr. X claim is that if xRy present
R = {(a, a), (a, b). (a, c), (b, a), (b, b), then only it implies yRx and herrce xRx.
(b, c), (c, a), (c, b), However, if xRy is not present then
(c, c), (d, d)) according to symmetricity yRx is also not
(b) The diagraph of the above equivalence present. So xRx need not be present in
relation is as follows relation. So it need not be reflexive.
For Example; Empty relation Q is both
symmetric and transitive. However, Q is not
reflexive relation.
&) Examples of a relations which are symmetric
and transitive but not reflexive.
Diagraph of Relation R
(, Empty relation S is symmetric and
@s"t. (ir)
transitive but not reflexive.
Given a*b Relation R = {(a, b), @, a), (a, a), ft, b)}
= axb t-rersion
b*a
over A = {a, b, c} is both symmetric
The contrapositive of this is
a*b-b*a=+a=b.' and transitive but not reflexive.
(a) Now since (A, 'r) is given to be a semigroup,
x is associative @flt"t
i.e.ax(a*a)=(2x2)xa A relation R is defined as xRy iff (x + y) is even
Hencea=axa over set ofintegers.
(0) (axbxa)*a-a*b*(axa) (x + y) is even iff
-a*bxa (, both x and y are even
*a (D both x and y are oCd
= a*(axbxa)=(ax2)*f Therefore, relation R is equivalence relation
-arrb*a
as a * a = a [proved in part a] because relation is
So (a,t b,t a) x a = a'r. (a * b'r. a) (, Reflexive
Hencea*b*a-a x*x=2x=even
G) (a xI xc) x (a x c) = a xl x (c x a x c) So (x, x) belongs to R. So relation is reflexive.
-a'kb*C (i, Symmetric
(a * c) x (a x b x g) = (a x c,r a) * b x c Ifx + y = even then y * x is also even
-axb'rc So relation is symmetric.
So (a*bxc) x (a x c) = (a x c) x (a x b x c) (iii) Transitive
Henceaxb*C=a*c If x + y = even and y + z = even
Then x + y + y * z = even+ even
@t"t = x+ ra2Y =even
The maximum number of elements in a binary x+ z=eyen-2y
relation on a set A with n elements = Number of
=
=+ X+Z=even
elementsinAxA=n2 .'. Relation R is transitive.
Each element has two choices, either to appear So relation R is an equivalence relation which
on a binary relation or doesn't appear on a binary divides the set of integer into two equivalence
relation. classes: One is of all even and other is of odd
.'. Numberof binaryrelations = 2n' integer.
30 I
GATE Previous Years Solved Papers : [[ | MADE EASY
Equivalence classes ofR are (iil If la -bl < 2 then also ib - al!2
[0] = {..., -6, -4, -2,0,2, 4, 6, ...} .'. R* is symmetric relation
[1] = {..., --7, -5, -3, -1, 1, 3, 5, 7, ...}
(r1) If la - bl < 2 and lb - cl < 2 then
it is not necessary that la - cl < 2
@ttl Ex.13 - 5lS 2 and 15 - 7l< 2 but
in any powerset of a set and <il is
$ always present t3-7t#2
the only common element between P(S) and Rn is not transitive.
P(P(s) Since R. is reflexive and symmetric not
.'. P(S) n P(P(S)) = {0} transitive, so R, is not an equivalence
relation.
@tut @t.t
(D Relation Rr(a, b) iff (a + b) is even over the
set ofintegers. Sr: Let A= set ofintegers
(i) a + a= 2a which is even B = set ofodd integers
So (a, a) belongs to R, C = set ofeven integers
.'. R, is reflexive relation A n (B n C) =t| and 0 is finite set.
(iil If (a + b) is even, then (b + a) is also Therefore, S, is true.
even Sr: Let two irrational number x and y are
.'. R, is symmetric relation respectivcly (r + vz) and (r - ut).
(iii) If (a + b) and (b + c) are even then
a+c=(a+b)+(b+c)-2b So x*y= t+Ji+t-Ji
= even + even - even = 2 which is rational number
= even Therefore.. S, is true. Since both S, and S, are
.'. R, is transitive relation. true. option (c) is true.
Since R, is reflexive, slrmmetric and
transitive so R, is an equivalence relation. @t"l
(II) Rr(a, b) iff (a +kr) is odd over set of integers.
Given a function f: x -> y and subsets
E and F ofA then we have
(i) a + a= 2a which is not odd
f(E u,F) = f(E) u f(F) and
So (a, a) doesn't belong to
R,
.'. R, is not reflexive relation f(EnF)cf(E)nf(F)
Since R, is not reflexive, it is not an Therefore S, is correct and S, is false.
equivalence relation.
(III) Rr(a, b) iff a.b > 0 over set of non-zero
@rar
The empty relation on any set is always transitive
relational numbers.
and symmetric but not reflexive.
(, a. a. > 0 for every non-zero rational
number.
R, is reflexive relation.
@(ul
I={0,1}
(ii) If a.b > 0 then b.a > 0 ,. - {0, 1}.
R, is symmetric relation.
= {s, 0, 1. 01. 10, 11, 000, ...}
(iii) a.b > 0 and b.c > 0 + All a,b,c are positive
So (X*, ') is an algebraic system, where '
or all a,b,c are negative.
(concatenation) is a binary operation.
Soa.c>0
So ()*, . ) is a group if and only if the following
.'. Ru is transitive relation.
conditions are satisfied.
So R" is an equivalence relation.
1. ' (Concatenation) is a closed operation.
(T\4 R* (a, b) iff - bl < 2 over the set of natural
la 2. ' is an associative operation.
number
(, la--als2 3. There is an identity.
o<2
4. Every element of ). has a inverse
.'. R, is reflexive relation.
MADE EASY I Discrete and Engineering Mathematics
tr31
Condition 2: For any string x, y, z e Z*, = {(0, 1), (1,2), (2.3), (3, 4), ..^}
x'(v'z)=(x'v)'z Now let T, be the reflexive closure of S.
So it is associative for example let T, = {(0, 0), (1, 1), (2.2), (3,3) ...} u
x=01,y=11,,2=00then {(0, 1), (1,2), (2,3), (3, 4) ...}
L.H.S. = x.(y.z)
= {(0, 0), (0, 1), (1, 7), (1,2), (2,2),
= 01'(11.00) = 01.(1100) (2, 3), (3, 3), (3, 4) ...)
= 011100
Let T, be the transitive closure of S.
R.H.S. = (x.1).2
(0, 1), (1, 2) e S .+ (0, 2) e T,
= (01.11).00 = (0111).00
= 011100 (0,2),(2,3)e S + (0,3)e T,
Condition 3: The Identity is e or empty string (0, 3), (3, 4) e S (0, 4) e T,
because for anv string co e I-.
=
and so on ...
toJ = [0€=0]. Also S=
(1,2), (2,3) e (1, 3) e T,
Now, since r e ,*, identity exists.
eS =
(1, 3), (3, 4) (1, 4) e T,
Condition 4: There is no inverse exist for I"
(7,4),(4,5)e S (1, 5)e T,
because any string o) € :*, there is no string o-1 =
such that cD . [D-1 = t = co-1 (r). and so on ...
So X- rvith the concatenation operator for strings T, = {(0, 1), (0, 2), (0, 3), ..., (1, 2),
doesn't form a group but it does form a monoid. (1, 3), (1, 4), ...1
Now the reflexive, transitive closure of S will be
@ral T, = T' uTz={(0, 0),(0, 1), (0, 2),..., (1, l), (1, 2),
If a < x, since p(x)
= p(y) whenever x < y (1, 3),...,(2, 2) (2, 3), (2, 4),...],
.'. p(a) =+ p(x)
Option (b) is correct.
Now since p(a) = T!ue, p(x) = cannot be false.
.'. (d) cannot be true.
@tl
@t.t In a symmetric matrix, the iower triangle must
be the mirror image of upper triangle using the
The possible solution pairs are (a,a ),
(a, b), (a, c), (b, a), ft,b), (b,c), (c, a,), (c, b) and diagonal as mirror. Diagonal elements may be
(c,c). Substitute them one by one in both anythrng. Therefore, when we are counting
equations and see which of them satisfies both symmetric matrices we count how many ways
the equations. are there to fill the upper triangle and diagonal
The given equations are: elements. Since the first row has n elements,
(axx)+(axy)-c .. .(i) second (n - 1) elernents. third row (n - 2) elements
(bxx)+(cxy)-c ...(ii) and so on upto last row, one element.
Substitute first (x, y) = (a, a) Total number of elements in diagonal + upp",
LHS of equation (i) becomes (a x a) + (a x a) = g triangle
*a=b =n+(n*1)+(n-2)+...+1
Now RHS of equation (i) = c = n(n + 1)/2
Therefore LHS * RHS. This means that Norn, each one of these elements can be either 0
(a. a) is not a solution pair. or 1. So total number of ways we can fill these
Similarly try each of the remaining seven possible elements is
solution pairs.
t
n(n+1)
= Power (2. \n2 + n)12)
it will be found that only two pairs (b, c) and (c, 2""2
b) wiII satisfy both equation (i) & (ii) Since there is no choice for lower triangle
simultanecusly. elements the answer is power (2, (n2 + n)12) which
Therefore choice (c) is correct. is choice (c).
32tr GATE Previous Years Solved Papers : [$ | MADE EASY
eabc a abc e
e eabc b bce a
abce
C CE
b U_
1
@t"t @ru
The hasse diagram ofthe given poset is
{1,2, 3, 4,5}
o [ta, b, c, d, e], <]
{1,2,3} {1,3,5}
= (x,z)e Rand(x,z)e S
(Since R and S are transitive)
+ (x,z)e RnS
From above diagram it is clear that
... R n S is transitive also. Since R n S is g is not onto =+ h - g.f is also no'u onto, since lhe
reflexive, symmetric and transitive.
co-domain of g is same as the co-dornain of g.f.
... Rn S is equivalence relation.
The contrapositir.,e version of the above
Note: Asimilar argument cannot be made from
implication is
RuS.
h is onto
= g is onto
@tul which aiso has to be true since direct
contrapositive.
=
Consider the arrow diagram shown below
ABC So option (c) is true.
aa-
t/ \ f
bo-
------*+a I
_i*.2 i
.O\
.ts j
@tat
r aJ o\i The rn al'C is defined in the question. it contains
\-/ only. comparable subsets of A.
h(a)=f.g(a)=61 i.e. the set'C is the set of all comparable subsets
h(b)=f.gft)=0 of the set A. Such a set is called a chain. We
Here f js onto but g is not onto, yet h is onto. have a theorem which says that the length of
As can be seen from diagram if f is not onto, h the longest chain for a set of size n is n+1.
cflnnot be onto. Infact theorem also says that the length ofthe
.'. f should be onto, but g need not be onto. longest anti-chain for a set of size n is n+1.
... Answer is (b). So the correct option is ft).
@,t"t @t"l
(, The set H is closed, since multiplication of f(x)=*+y-3
upper triangular matrices will result only in x*a-3=x=a*x-3
upper triangular matrix. soa=3
(ii) Matrix multiplication is associative, i.e. A * (B Now 3 is unique. and 3 e N
*C)=(A*B)"C.
So I has identity.
(iii) Identity element is II: f(x) = max(x, y)
ll[rool
max(x,a)=y=max(a,x)
I=10 1 0l In N, the only value of a which will satisfy
' n 1l
10, above equation is a = 1.
Since 3 is unique, and 3 e N
and this belongs to H as I is an upper
So II has identity.
triangular as will as lower triangular matrix.
MADE EASY I Discrete and Engineering Mathematics I3s
@t"l
Let A - \1,2, 3,5, 7, 8, 9} EnG
Construct the table for an5, x, y e A such that
x*y= (x.y)mod10
So X =Y
\ 2 3 5 719 or alternatively the solution can be obtained from
3 5 7I I boolean algebra as follows:
X = (EnF)_(FnG)
= EF-FG
= EFn (FG),
15963 = EF.(F'+ G)
' = EFF'+ EFG'
= EFG'
We know that 0 e A. So it is not closed. Therefore, Similarly, Y = (E-(E.c))-(E-F)
(a) is true. = (E- EG) - (E.F')
The identity element = 1 =E.(EG)'_EF'
(2 . 2-rl rnod 10 = 1 =E.(E'+G')-EF'
From the table we see that 2-1 does not exist. = EG'-EF'
Since,(S . 7) mod 10 = 1 = EG'.(EF')'
7 is the inverse of 3 and 7 e A.
= EG''(E'+ F)
(c) is false. = EE'G'+ EFG'
= EFG'
(d) is true since 8 does not have inverse. _Y
Therefore,
@t*l @rnr
(x, y) R (u, v) iff x < u and y > v
The problem can be solved by considering the
(x,x) 7( (x, x) since.x ./ xand.x / x casesm=4andm=5etc.
So R is not reflexive, Let m=4
.'. R is neither a partial order, nor an equivalence S = {1, 2,3, 4}
relation. n = nurnber of 3 element subsets
- *c, = ncr= n
@t"l n= 4
Consider the following Venn diagram for The 4 subsets are {1, 2,3}, {1,2, 4}, {7,3, 4} and
X=(E^F)-(FnG) {2,3, 4}
36 I GATE Previous Years Solved Papers : !$ | MADE EASY
f(11 = rrr*Oer of subsets having 1 as an element RHS = (P A Q) n (P AR) = (pq' + p'q) (pr' +
-q
-r) p'r) = pq'r'* p'qr
f(2) = number of subsets having 2 as an element LHS + RHS
-r) So statement I is false.
f(S)=3andf(4)=3 II. LHS = P n Q A R = p(qr' * q'r) = pqr' + pq'r
1 RHS = (P n Q A (P n R) = pq A pr = pq(pr)' +
I,f(i) =3+3+3+3=12
i=1
(pq)'p. = pq(p'+ r') + (p'+q')pr = pqr'* pq'r
LHS = RHS
both choice (a) and choice (b) are matching the
So statement II is ti'ue.
answer since
Norv let us
3m=3n=12
try m= 5
@trl
No's divisible bv 2 in X = 61
S = {1, 2,3, 4,5}
[= floor (12312)i
n = number of 3 element subsets = 5C, = 10
No's divisible by 3 in X = 41
n=10 No's divisible by 5 in X = 24
The 10 subsets are {1, 2, 3\, {.1, 2, 4}, {1, 2. 5-, u,
No's divisible by 2 and 3 .i,e bv 6 = 2A
3, 4), {1, 3, 5}, {1, 4,51, {2,3, 4}, {2,3,5}, {2, 4.5),
No's divisible by 2 and 5 i.e by l0 = 72
{3, 4, 5}
No's divisible by 3 and 5 . i.e by 15 = 8
f(1) = i121 = f(3) = f(4) = f([) = 6
No's divisibie by 2 and 3 and 5 ..ie bv 30 = 4
5
No's Cir,isible by either 2 or 3 or 5 = n (AUBUC)
)rtll =6*6+6+6+6=Bo
i =1 = n(A) + n(B)+n(C) - n(A) n B) * n(B n C) _ n(A
Clearly 3 m = 3 x 5 15 {is not matchinglf(i)} nC)+n(AnBnC)
=
but 3n = 3 x 10 = 30 {is matching )f(i) = 39; = 61 + 4\ + 24 _ 20 _ 12 _ g + 4 = g0
.'. 3 n is the only correct answer. X = {n ,1 ( n < 123, ir is not divisible b;,,' 2,
Correct choice is (b). 3or5f
The problern can also be solved in a mGre general Cardinaiitl,- = 723 - 90 = 33
way as follows:
g ^..
@el
Lt(r)
i=l
= f(1) + f(2) + ....+ f(m) Let S be a set of n elements say {1, 2,3,..., n}.
* f(2) = ..... = f(m) m- lC, Now the smallest equivalence relation on S must
since f(1) = contain all the reflexive elements {(1. 7), (2,2i),
m
(3, 3),..., (n, n)) and its cardinality is therefore n.
Therefore Iftli = mx (**i)Cz
i=I The largest equivalence relation on S is
mx(m-1)x(m-2) S x S, which has cardinality of n x n = n2.
2 .'. The largest and smallest equivalence relations
3xmx(m-1)x(m-2) on S have cardinalities ofn2 and n respectively.
1x2x3 =3x*Cs Correct choice is ft).
Since n = Number of three elements subsets of a
set of m elernents = -C.q @<"1
m A partition P, is called a refinement of the
Therefore ) ffil - 3x -Cr- 3n partition P, ifevery set in P,, is a subset ofone
i=l
of the sets in Pr.
@rur nn is a refinement of fir, nrand m,
PAQ=pq'+p'q nrandnrare refinements of n,
where A is symmetric difference between p n, and Th are not comparable since neither is a
and q. refinement of the other.
I. LHS = P A Q n R = pA(qr) = p(qr)' + p'(qr) = So the poset diagram for (S', <) would
p(q'+ r') + p'qr
MADE EASY I Discrete and Engineering Mathematics 137
@to
The given set theory expression can be converted
into equivalent boolean algebra expression as
follows:
(p n q n r) u (pc n q n r) u qc u rc
= p.q.r * p'.q.r * q' + r'
=qr(p+p')+q'+r'
-qr+q'+r'
Which is choice (c).
=(q+q').(r+q')+r'/
@to -r+q'+/
In this problem -r+r'*q'
a % b means the mod function (i.e. residue
=1*e'
_I_U
-
i
-
TT
C =C
c2 = c.c=b
@t"l
Letn=2.There are only 2 onto functions as
C3 = C.CZ=C.b=d
shownbelow:
C4 = C.C3=C.d=a
since all ofa, b, c, d have been generated as pow,ers
ofc
.'. c is a generator of this group.
Sirnilarly Forn=2
(l-t_-l_LI
d2 = d.d=b
Option (a) 2n = 22 = I
d3 = d.d:=d.b=c
Option (b) 2"-1=22-7=3
d4 = d.dS=d.c=a Option (c) 2"-2-22-2=2
d is the other generator.
Option (d) 2\2 -2)=2(22 -2\= 4
So only option (c) gives correct answer"
@t*t @tu"t
Given the following details: Since it is given that Vl f(f(,)) =,
S = {1,2.3,4, ...2A1,4\r It means f f = I
. i.e. f = f-1
U<V if the minimum element in the That is f is a symmetric function.
symmetric difference of the two sets is in U. Statement P means that every symmetric
51: There is a subset of S that is larger than function is a identity function which is not true,
every other subset. since there are many symmetric firnctions other
52: There is a subset of S that is smaller than than identity function.
every other subset. Example: {(0, 1), (1,0), (2, 3),(3,2),...(2013,2014),
S1 is true since Q (which is subset of S) is larger (2014,2013)) is a symmetric functionbut not the
then every other subset. identity function.
i.e. Vu u < Q is true since the minimum element Statement Q means that some symmetric
inuA0=u,isinu. function is identity function.
(Note:uAQ=u$'*u'Q=P; This is true, since identity function is one of the
52 is also true since S (which is subset of S) is symmetricfunctions.
smaller then every other subset. Statement R means that every symmetric
i.e. Vu S < u is true since the minimum element function is onto which is true, since it is
in S A u = t)', is in S.
impossible to make an into function symmetric.
(Note: S A u = Su' + S'u = 7u' + 0u =u')
.'. both 51 and 52 are correct. @s"t.
(, e is identity element
dl
tit
1- s
@or
"l*-r,/
{
".
s@(x)) _ h(x) ER
h(s(r)) - s@) .'. R is symmetric but not reflexive and not
transitive.
Wtu>
A = {5, {6}, {7}} @s"1.
1. (, e 2A is true. Any power set contains an Let X = {0, 1, 2, ...10}
empty set. lXl = 11
2. 0 s 2A is true. Empty set is subset of any lP(X)l =211 =2048
set.
3. {5,{6}}e 2A is true. power set of A contain {5, @sot.
X
{6}} as a 2 element subset of A.
4. {5, {6}} c 2A is false. Power set of
contain 5 and {6} as elements.
A not A
1r\
t:t
So {5, {6}} can not be subset of 2A. \,
The number of onto functions from A -+ B
@tal where lAl =mand lBl =nisgivenbythe
f, has 5 elernents formula
43 has all ordered triplets of elements of .C r'- 'C, (n - 1)- + "Cz(n - 2)^ + ... +
= f3contain 5 x 5 x 5 = 53 = 125 elements. (-1)"-1 "c,_11-
Herem=4andn=3
Substituting in above formula we get,
34- 3C1(3 - 1)a + 3C2G - 2)4
=81-48+3=36
!@ sot,
If q,r,s are chosen, then only it will violate the XY
distributive property.
r/?\t*/;\
Number of ways to choose q, r, s in any triplet
order=B!=Bx2xl-6.
.'. p(satisfying distributive property) - 1 -
\/ tv/
\1y
Total possible functions = 202 = 400
p(violate the distributive property) Number of one-to-one functions
=20Pr=20x19
=f- 9o = 0.952 which is between 1/5 and 1.
20x19
.'. Required probability = = 0.95
2Ox2O
MADE EASY I Discrete and Engineering Mathematics 141
@tur @t,l
X#Y=X+Y R = {(p, q), (r,s) | p s = q - r}
-
This is the NAND operation. NAND is known (i) Check reflexive property
to be commutative but not associative.
V(p, q) e Z* x Z* ((p, q), (P, q)) e R
So only 52 is true.
is true iff p - q = q - p which is false.
So relation R is not reflexive.
@<al (ii) Check symmetry property
S = 11, 2, 3. 4, 5, 6)1
If ((p, q), (r, s)) e ,E then ((r, s), (p, q)) eR
U is the power set of S = U = P(S)
((p,q),(r,s))e .R = p-s=q-r
2,3}, ...{1,
U = {{ } {U, {2}, ...{1, 2}, {1, 3}, ...{1,
((r, s), (p, q)) eR =) r - q= s - P
2, 3, 4\, ...{1, 2, 3, 4, 5} ...{1, 2, 3, 4, 5, 6}}
lUl = 26=64 elements. If p -s= e - r is true, then r - I = s -p is
also true by rearranging the equation.
TeU*T'eU
.'. ,R is sytnmetric.
ReU,7\-E=T-R
(a) vX e U(lXl = lX'|) means that every subset @,s"1
of S has same size as its complement. Clearly
.( n\
fln) = /[;] if n is even
this is Faise.
(For example, {1} e U, and complement of f(ru) = f(ru + 5) if n is odd
{1} = {2, 3, 4, 5; 6}) frN*->N+
&) aXeUSYeU (lxl=;,lYl=sandxnY=Q)
Now fl4 = f(z)= f Q)
means that there are two 5 element subsets
of S which have nothing in common. This is
clearly False. (3) = /(3 + 5) - /(8) = r(!) = xnt
Since any two 5 element subsets will have
atleast 4 elements in common. _ tlft(+\
-t_f(2)=(7)
- \.",/e l-
(c) YXeUYYeu (lxl=2,]rl=3 andxt'r=q)
means that every 2 element subset X and
So fl:.) = f(2) = /(3) = f(+) = f(8)
every 3 element subset Y wiII have X-Y = 0
i.e., X c Y. Now let us find f(5) = f(5+ 5) = flro) = ,(+)
This is clearly False as can be seen from the
example X = {1, 2}, Y = {3, 4, 5} u,here - /(5) so /(5) = /(10)
Now let us find /(9)
XEY.
(d) YX eU VY eU (X\Y = l" \ X,) means fle) = f(9 + 5) - f(t+) = tl;lr+) = f(7)
-(
3.i (a) Solve the recurrence equations 3.8 Two girls have picked 10 roses, 15 sunflowers
T(n)=T(n-1)+n and 14 daffodiis. What is the number of ways
T(t;= 1 they can divide the flowers among themselves?
(b) What is the generating function G(z) for the (a) 1638 &) 2100
sequence of Fibonacci numbers? (c) 2640 (d) None of these
[1987:2 Marks] [1999:2 Marks]
3.2 Solve the recurrence equations: 3.9 The minimum number of cards to be dealt from
an arbitrarily shuffled deck of 52 cards to
'l'(n) = -f")*r
r'l
\2)
guarantee that three cards are from some same
suit is
T(r; = 1 (a)B O)8
[1988:2 Marks] (c) e (d) 12
3.14 n couples are invited to a party with the condition (a) i &)i+1
that every husband should be accompanied by (c) 2i (d) 2i
his wife. However, a wife need not be accompanied [2005:2 Marks]
by her husband. The number of different
gatherings possible at the party is 3.20 For each element in a set of size 2n, anunbiased
coin is tossed. The 2n coin tossed are independent.
/ 2n)
An element is chosen if the corresponding coin
(u) '^ l*2"
|\n/ @) B'
toss were head. The probability that exactly n
(zn)l t2n\ elements are chosen is
(c)
=;r
2"
(d I\n/ I
t2n\ I (znt I
[2003: l Mark] (a)
' I\n// I 14" (b) | | 12"
\n)l
3.15 Mala has a coiouring book in which each English
Ietter is drawn two times. She wants to paint Itzn: 1
Common Data for q3.24 & Q.3.25 is drawn at random from the box. The expected
Let x, denote the number of binary strings of length n length of the word drawn is .-. (The ansu,er
that conatin no consecutives 0s. shouid be rounded to one decimai place).
[20i4 (Set-2): 1Mark]
3.24 Which of the follorning recurrerrces does x,
' satisfy? 3.30 The number of distinct positive integral factors
(a) x, = 2x.-, 0) x, = *[rlz] * 1 of 2014 is
(c) x, = xp./21 + n (d) x, = Xr,_i * X..2 [2014 (set-2) : 2 Marksl
Combinatiorits
3.4 (a) 3.5 (d) 8.6 (d) 3.8 (c) 3.9 (c) $.10 (b) s.11 (b) 3.12 (di D.to (c)
3.14 (b) 3.15 (d) 3.16 (a) 3.1? (d) 3.18 (c) 3.19 (b) D"4V (a) &.2L (a) ooo
O.AA (d)
3.23 (a) 3.24 (d) 3.25 (d) t).zo (b) t"27 (a) Qat (a) 3.35 (b)
E{Planations eornbinatiories
ffi(a)*ot. iex'=!o.*'+Io
--ur2r-t4r-t -x'
T(n) = T(n - 1) + n r=2 r=2 r=2
In-In 1= n
For Homogeneous solution -- Yo.r'
L,l r = xlaLl | ,r'
| '+x'!Lt clf -: .!' '
,_
r=2 r=2 r=2
Tnnl-T O
\
=c(1)"=c
= A(r) = -----
1-x-x-
1
=) T(2k) - tl=1
Tl
q=d'=l - ,1r* i; = t
particular solution is
=
Let
T(2k)
So T(zk) = xk
v 1
n(n+l) n: +n "k -v ^k =
t2 2 ) r., = 2 -
[l*!"1
2
For Homogeneous solution
So complete solution is
xk-xk i = 0
t-1= 0
T1n1=C+].(n+1) t= 1
@sot. @or
Let the string be oflength 4 : abcd E : Persons speaks EngJ.ish
Number of substrings of length 0 = 1 (only e) H ; Persons speaks Hindi
Numirer of substrings of length 1= 4 K : Persons speaks Kannada
a,b.c.d Assume that everyone in the room speaks at ieast
Number of substrings of length 2 = 3 one ofthe languages.
ab, bc, cci Given, n(lluHuK)=26
Number of substrings of length 3 = 2 n(E) = 19
abc. bcd n(H) = 15
Number of substrings of length 4 = 1
nfiQ=22
abcd
n(Enli)=g
Total number of substrings
n(H ;', K) = 1i
=1+(4+3+2+1) n(KaE)=13
= 1+ (Sum of 4 natural numher) n(I(nEnH)=r
,
I '
lT-
4x (4 +1) principle of inclusion ar:d exclusion
8.,-
-- -11
-la
2
n(E u H u K) = n(B) + n(H) + n(K) - n(EnH)
Therefore, total number of substrings
(maximum) that can be formed from a chare-cter
- n(H E) - n(Kn E) + n(Kn E n H)
^
28 = 18 + 15 + 22_-9 - 11- 13 + n(K n E n H)
^in+1)
string oflength , * = n(k n E n H) = 28 - 55+ 33 = 61 - 55 = 6
,
Therefore, the number of people w-ho speak all
@t*t three languages are 6.
First aruanging all n zeros in a rorv. There is
on15' 1 wav for ari'anging n zel'os in a row. B5, Es"t.
arranging n zeros in a row. we get xn =2xI)-- .-l |
@t"t @tnl
Number of ways for distributing r similar things T(2\ = 3T(2k-1)+l
among n different things - (n-1+r)Cr Let T12k; =
",
The nuiuber of ways for tlistributing 10 roses - >q=3x.-,+1
(2-1+i0)C10
an)ong the two girls = - 'l 1. =) xn -Jxo.. n-- - Ij
- ,UCr,
= 16C,
= 16 n-3 = 0
Number of wa5rs fbr distributing 14 daffodils n=3
among the two giris Homogenous solution is
r,Cr, = ,tC,o = t-te, = 15
=e-t+', n = Cr(B)"
.'. Total number of wavs = 11 x 16 x 15 =2640 T(zk; = gr13Y
For Particular solution
@t"l Let d be the particular solution
Let the number of cards to be dealt from an d-3d = 1
arbitratily shuffled deck of 52 cards be n. ' 2d=-1
Number of suits = 4
d- .,
1
@&r
The digits are given to be distinct i.e. no repetition. @ral
4 digit even numbers cannot start with 0 and The minimum number of coiours required to
must end with 0,2,4,6 or 8. colour the vertices ofa cycle rvith n nodes
Since there is a condition for 0 in starting as = 2, when n is even
well as ending we will count the even numbers = 3. when n is odd
ending with 0 seperately. lt
So the total number of 4 digit even number = 4 Therefoi'e + l+2 gives 2 when nis even,
digit even numbers ending with zero + 4 digit
"-21l9l
LA ,J
required to do this.
Putn=2,
Therefore the requirement is k2 > 26.
1
The minimum value of k that satisfies this (2*1+r) g. ,r
,L
equationisk=6. (1 - x)' r=0
Et"t want
We every one of the 5 balls to be in the
! {r-1,^L.X --r'
= .L
. r=0
5:-51+5:-5: ).1i + 1; xi
= i=0
D = i(-1)'I
-5 u- r'. = 2i 3: 4i 5: (Since r is a dummy variable, r can be replaced
= 60 - 20 + 5 - 1 - 44 wavs. bv i)
@t'l @t"l
Consider the following diagram. P= Ii=1 + 3 + 5 + 7 +... + (2k- 1)
(3,:i) 1si<2k,iisodd
Q = I i = 2 * 4 + 6+...2k, i is even.
1 S i < 2k,
P is inA.F with a = 1, d = 2 and n = k
Q is in A.P with a = 2, d= 2 ar'd n = k
n
(0. 0) P=-(2a
2
*in-- 1)d)
0,/
and then we can subtract this from total number
of wa5rs to get the ans\&'er. 1./
Now there are SCn ways for robot to reach (4, 4) xl -.)
from (0, 0) and then robot takes the 'IJ' move Let n _,
ox
from (4, 4) to (5, 4). Now from (5, 4) to (10, 10) /"//
the robothas to make 5'IJ'moves and 6'R'moves
z0\ \
<,t 1/
in any order which can be done in l|
5! 6!
*ur.
\ \1
,1,,
.0/
/
- 1lCr ways.
^" o
^2--q
.'. The number of ways robot can move from (0, Let n=3
0) (10, 10) via (4, 4) - (5, 4) move is
-'/Ox
tco
8\ /11\
i
,/o\r<::
" "cu = [n,J.[ ,.,J
.'. Number of ways robot can move from (0, 0) to
\,-'<?)
- _\
{rri 1
(10, 10) without using (4, 4) to (5, 4) move is
tre=5
/ 2ol Is) / 11)
Now, substituting n = 3 in all of the answers
*aYs
[,oJ-[*]'[; J only choice (d) r, = xn_r* *n_2 satisfies the
which is option (d). numbers obtained from the tree counting.
MADE EASY I Discrete and Engineering Mathematics !sI
permutations of 2 ones and 4 twos leI e8.l Le8 ee.l Lee 1001
6! 1
- 2i 4l
= 1-
100
(all the terms in above series except
--15
Similarly (4, 3), (6, 2), (8, 1) and (10,0) are the the first and last terms cancels out)
other four solutions and the number of pennants 99
for each is respectively = 100 = 0.99
s2 I
GATE Previous Years Solved Papers : ([ | MADE EASY
@t"l _,4ii
2r = 0 [no strings of length 1 cont'ain two .,{z-..-i',
,/- z1-zq jf
consecutive 1's] t t*-
' -3-3'/
az= 7 [". strings = 11] \ 31
3
./ ---- -\;_;r'
- -:l
-;--)-2v
h, = 3 [.'. strings are : 011, 110, 111] e_l{
\ \ 3-rv
\\\ \j{-3-3/
a+ = 8 [". strings are: 0011, 0110,0111, 1011,
1100, 1101, 1110, 11111 \"-3-B- 3v,
Option (a): AIl the tick rnarked riumbers satisfy the non-
an =a n-z.+a ll- ,+2i\-2 decreasing order condition.
L
numbers = Nuurl;er of
=) 3{ = dq-r* ar-r* 2+2 = Number of 4-digit
r 6 r o2- 1+ 3 + 4 = 8 which is True. tick rnarks = 15.
-o2'o3't-
Option (b): @rur
8n = 8, ,* 2un,, + 2.n-= Let a,, be the number of n-bit strings that do
= a4= ar* Zarl 22 not contain tlvo consecutive 1's. lve wish to
- 7 + 2 x 3 + 4 = 11 which is False. develop a recurrence reiation for ar.
Option (c): Consider 1 bit strings 0, i
an=zan2*rr r*2" So at=2
=) z.4= Zar+ a,,* 22 Consider 2 bit strings 00, 01, 10, 11
Out of minimum only 00, 01, 10 do not contain
=2x I+
3 + 4 = 9 which is False.
t\ .o consecutive 1's.
Option (d):
an= 2an-r* 2un-r.+ 211-2
So az=3
+ a4= 2ar+ 2ar* 22 oo<?
z0
= 2 x L + 2 x 3 + 4 = 12.which is False. Consider B bit string. *)l
.'. Option (a): a. = d,,-z* o.-1 + 2n-2 is correct.
'o-.,
@sot. Out of minimum six strings onl5, 000, 001. 010,
Dividing 2100 successively by prime numbers. 100 and 101 five strings satisfy do not contain
we get that, the prime factors of 2100 are 2 x two consecutive 1's.
2x3x5x5x7 So o" = 5" Three numbers et, a2,o" satisfy
clearl,v only (b) en= an t* an-2 is correct.
-22xclx52x7l
If l/ = p\ x qh' x ru'' .. . x yo' then the number of @sot.
factors of N are (/tr+t1 (k2+7\... (kn+1) We wish to find coefficient of r12 in (r3 + 14 +
= re(1 +*+*2......13
@sot.
To satisfy the non-decreasing order condition xn
= *rI , ,,,c,x,
allow 1, 2, 3 after 1, allow only 2,3 after 2 and
(1 - x)' ,=u
@sot.
Given en = 6rL2 * 2n * or_, and 0t = 8
We wish to find o*
Norn' oz=6x22+2x2"tctt
as=6x32+2x3+az
= 6 x Z2 + Zx B + 6 x 22 + 2 x 2 +c....
ogs =6x 992 + 2 x gg + 6 x gg2+2 x 99...
..,+6x22+2x2*at
Since 0r = 8
ogg = 6x992+ 2x99+6x982+2x98...
...+ 6 x 22 + 2 x 2 + 8
= 6 x gg2+ 2 x gg + 6 x gg2 + 2 x 99...
...6x22+2x2+6x12+2x1
= 6(72+22+32... gg2)+ 2.(.7 + 2 + 3...99).
^ (99(99+lX2r99+1)r fggtgg*tl
= O'--- 6\2) -2r :
=99x100xi99+99x100
= 100 x 99 (199 r- 1)
., = 100x99x200
=2x99x10r
= 198 x 104
Soif agg=Kx104thenK=198.
ITIT
1
Graph Theory
i
!
4.1 Which of the follov.'ing graphs is/are planar? (see 4.6 The number of distinct simple graphs r,'.;ith upto
Figure) three nodes is
(a) 15 0) 10
(c) 7 (d) e
[1994: l Mark]
4.7 Prove that in a finite graph, the number of
vertices ofodd degree is always even.
[1995:2 Marks]
4.8 Let G be an trndirected connected graph with
distinct edge weights. Let erru" be the edge rn ith
maximum weight &Dd €,ri,, be the edge with
minimum weight. Which of the follor,ving
statements is false?
G3 (a) Ever). minimum spanning tree of G must
[1989:2 Marks] contain e*,.
(a) G1onlv " (b) G1 ancl G2
(b) If e,.r, is in a minimum spanning tree. then
(c) G2 only (d) G2 and G3
its rernoval must disconnect G
4.2 A graph is planar if and oniy if, (c) No minimum spanning tree contains er.n"
(a) if does not contain subgraphs homeomorphic (d) G has a unique minimum spanning tree
to K, and K, ,. ' t2000:2 Marksl
(b) it does not contain subgraphs isomorphic to
K. or K.., 4.9 How many undirected graphs (not necessary
". connected) can be constructed out of a given set
(c) it does not contain subgraphs isomorphic to
Ku and K". u. V = lvr. vo. ..... v,,l of n vertices?
(d) it does not contain subgraph homeomorphic .. n(n-1)
(a) h\2
to Ku or K'' u' 2 ,,,!:]l
[1990 : 2 Nlarks] (c) nl (d) z 2
-
4.3 The maximum number of possible edges in an [2001:2 Marks]
undirected graph with 'a' vertices and 'k' 4.10 Maximum number of edges in a n-node
components is undirected graph without self loops is
[1991:2 Marks] (a) n2 (b) n(n - 1)i2
4.4 -. with minimum number of
A non-planar graph (c) n-1 (d) (n + 1) (n)/2
vertices has 12002 t 1 Markl
(a) 9edges.6vertices
(b) 6edges.4vertices
4.Ll Let G be an arbitrary graph with n nodes and k
components. If a vertex is removed from G, the
(c) 10 edges, 5 vertices
(d) 9 edges,5 vertices number of components in the resultant graph
l Mark] must necessarily lie between.
[1992:
(a)kandn (b)k-1andk+1
4.5 Maximum number of edges in a pianar graph (c) k-1andn-1 (d) k+1andn-k
with n vertices is
[2003: l Mark]
[1992:2 Marks]
MADE EASY I Discrete and Engineering Mathematies iss
4.12 How many perfect matchings are there in a 4.18 Let G be a simple connected planar graph with
complete graph of 6 vertices? 13 vertices and 19 edges. Then, the number of
(a) 15 b) 24 faces in the planar embedding of the graph is
(c) 30 (d) 60 (a) o (b) 8
(c) 9 (d)
[2003:2 Marks] 13
[2005: l Mark]
+.fg A Graph G = (V, E) satisfies
I EI <3 lVl -6. The min-degreeofGisdefined 4.Lg Which one of the following graphs is
NCT piannar?
u. T;tl {degree (v)}. Therefore, min-degree of G
cannot be
(a)
(a) 3 (b) +
(c) 5 (d) 6
[2003 : 2 NIarks]
4,14 The rninimum number of colours required to
u.l (---------J
\ r \,/ ,/'lI
colour the following graph, such that no two (c) (ci)
A
v [2005:2 Marks]
4.20 If aii the edge weights of an undirected graph
are positive, then any subset of edges that
(a) 2 &)3 connects all the r.ertices and has minimum total
(c) 4 (os weight is a
12004:2 Marksl (a) Hainiitonian cycle (b) gid
(c) hypercube (d) tree
4.75 How many graphs on n labeled vertices exist
which have at least (n2 IIT-2006: 1 Markl
- 3n)12 edges?
( r,:-3n
4.2L Consider the undirected graph G defined as
)12
I .,-
(a) 't -t"'C .,
(n- jjn)/z
follows. The vertices of G are bit strings of length
k=0 ru. We have an edge between vertex u and vertex
4.35 The degree sequence of a simpie graph is the 4.39 Let G be a cornplete undirected graph on 6
sequence ofthe degrees ofthe nodes in the graph vertices. If vertices of G are labeled, then the
in decreasing order. V/hich of the foilowing number of distinct cycles of iength 4 in G is
sequences can not be the degree sequence ofany equal to
graPh? (a) 15 (b) 30
' I. 7, 6, 5, 4. 4, 3,2, I (c) e0 (d) 360
II. 6, 6, 6, 6, 3, 3,2,2
12012 z 2 Marksl
m.7,6,6, 4, 4,3,2,2
g,
rv. 7, 7, 6, 4, 2, L, I 4.40 Consider an undirected random graph of eight
(a) I and II (b) III and IV vertices. The probability that there is an edge
(c) fV only (d) II and IV between a pair of vertices is 712. What is the
[2010:2 Marks] expected numbers ofunordered cycles oflength
three?
4.36 K4 and Q3 are graphs with the foliowing (a) 1/8 &)1
structures: (c) 7 (d) 8
,Q3
[2013:1Mark]
4.41 Which of the following statements islare TRUE
for undirected graph?
P: Number of odd degree vertices is even.
Q: Srrm of degrees of all vertices is even.
Which one of the fo-Ilowing statements is TRUII (a) P only (b) Q only
in relation to these graphs? (c) Both P and Q (il Neither P nor Q
(a) Ka is planar u,hile Q3 is not [2013: l Mark]
O) Both K4 and Q3 are planar 4.42 Let G = U, E) be a directed graph where Vis
(c) QB is planar while KB is not
the set ofvertices and Ethe set ofedges. Then
(d) Neither K4 nor QB is planar
which one of tle following graphs has the same
[2010:2 Marks] strongly connected components as G?
4.37 Let G be a simple undirected planar graph on 10 (a) Gr = (V, E1) where Er= {(u,u)\fu,u)e4
vertices with 15 edges. IfG is a connected graph, E)
0) Gz= (V, where Er= {(u,u)l@,u)e 4
then the number of bounded faces in any (c) Ge= (V,E)where Er={(u,ui) lth"r"isapath
embedding of G on the plane is equal to
of length < 2 from u to u in E)
(a) 3 (b) 4
(d) G4 = (V^,D where Vn i-< the set of vertices in
(c) 5 (d) 6
G which are not isolated
120122l Markl
[201a (Set-l): l Mark]
4.38 Which of the following graphs is isomorphic to
4.43 Consider an undirected graph G where self-loops
are not allowed. The vertex set of G is {(i, j) : 1 S
i< 72,1.< j <12). There is an edge between (o, b)
(a)-tr rm
and (c, 0 if la-cl< 1 and lb- al< t.
The number of edges in this graph is_.
[201a (Set-l):2 Marks]
4.44 An ordered n-tuple (d'd2,...,dn) with d, > dr2 ...
> dn is called graphic if there exists a simple
(c) (d) undirected graph with having degrees
n vertices
dt,d2,...,d,respectively. Which of the following
6-tuples is NOT graphic?
120L2:2 Marksl
s8 I GATE PreviousYears Solved Papers: ffi | MADE EASY
(a) (1, 1, 1, 1, 1, 1) (b) (2, 2.2,2,2,2) 4,50 Let G be a connected planar graph with 10
(c) (3, 3, 3, 1. 0, 0) (c) (3, 2. 1, 1, 1, 0) vertices. Ifthe number ofedges on each face is
[2014(Set-1):2Marks] three, then the number of edges in G is
4.45 The maximum number of edges in a bipa-rtite
. graph on 12 vertices is _. [2015 (Set-1) : 2 ]Iark-.1
[2014 (Set-2): l Mark] 4.51 A graph is self''complementary if it is isomorphic
4,46 A cycle on n vertices is isomorphic to its to its complement. For all self-cornplernentary
complement. The value of ru is _. graphs on n vertices. n is
[2014(Set-2):2Marks] (a) A multiple of 4
(b) Even
4.47 The number of distinct minimum spanning trees
for the weighted graph below is (c) Odd
(d) Congruent to 0 mod 4, or 1 mod 4
2
[2015(Set-2):2Marks]
4.52 In a connect'ed graph,
bridge is an edge whose
a
removal disconnects a graph. Which one of the
following statements is True?
(a) A tree has no bridges
[2014 (Set-2):2 Marks] (b) A bridge cannot be part of a simple cycle
(c) Everl'edge of a ciique with size > 3 is a bridge
4.48 If G is a forest rvith n-vertices and /t connecteci
(A clique is any complete subgraph of a graph)
components, how many edges does G have?
(d) A graph rvith bridges cannot have a cycle
@) lnth) 0i lntkl
(c) n-lz (d) n-k+7 [2015(Set-2):2Marks]
[201a (Set-3):2 Marks]
4.53 Consider binary tree Tthat has 200leaf nodes.
a
4.49 Let 5 denote the minimum degree of a vertex in a Then, the number of nodes in Tthat have exactlv
graph. For ali planar graphs on n vertices with two children are
6 > 3 which one of the following is TRUE?
[2015 (Set-3): l Mark]
(a) In any planar embedding. the number of faces
n 4.54 Let G be connected undirected graph of 100
rs at least -2 +2
vertices and 300 edges. The weight of a minimum
ft) In any planar embedding, the number of faces spanning tree of G is 500. When the weight of
each edge of G is increased by five, the weight
rs less
-n
than -2 + 2 of a minimum spanning tree becomes _.
(c) There is a planar embedding in which the [2015(Set-3):2Marks]
number of faces is less than 1+ 2 4.55 The minimum number of colours that is sufficient
2
(d) There is a planar embedding in which the
to vertex-colour any planar graph is _.
[2016 (Set-2): l Mark]
number of faces is at most =L
ti+1 lrrt
[201a(Set-3):2Marks]
MADE EASY I Discrete and Engineering Mathematics
!se
@Graph Theory
4.t (c) 4.2 (d) 4.4 (c) 4.6 (c) 4.8 (c) 4,e (d) 4.10 (b) 1.Lt (c) 4.12 (a)
4.13 (d) 4.L4 (c) 4.15 (d) 4.16 (a) 4.17 (d) 4.18 (b) 4.rs (a) 4.20 (d) 4.2L (c)
4.22 (c) 4.23 (c) 4.24 (h) 4.2s (b) 4.26 (d) 4.27 (c) 4.28 (b) 4.2s (b) 4.30 (d)
4.31 (a) 4.32 (b) 4.33 (c) 4.34 (a) 4.35 (d) 4.36 (b) 4.37 (d) 4.38 (b) 4.3e (d)
4.4a @) 4.41 (c) 4.42 (b) 4.44 (c) 4.48 (c) 4.49 (a) 4.51 (d) 4.52 (b)
Graph Theory
Et*l @t*l
Ku is smallest non-planar graph in terms of
number of vertices.
The number of vertices in K, is 5 and number of
@s"t.
G, is k, , which is a well-known non-planar Maximum number of edges in a connected,
graph. planar, simple graph with n vertices is 3n - 6.
G,:
@r"l
Assume that the vertices are unlabelled. Number
of distinct simple graphs with 1 node = 1
Graph G, is isomorphic to the foliowing graph:
(r.
Number of di.stinct sirnple graphs with 2
nodes = 2
ara
The above graph is planar. So G, is planar. (r) (No edges.)
(i, i;d*;
Number of distinct simple graphs with 3
nodes = 4
(, . . o (Noedges)
G,, is isomorphic to Kr. " which is well known (i1) t H(1edge)
non-planar graph. Therefore, G, is a non-planar
(iii) .__ (2e<tses)
graph.
(iv) (3 edgest
components is
(a-k+1)(a-k)
Let Vu and Vo respectively the set of vertices of
even degree and the set ofvertices ofodd degree
in an undirected graph G = O, E) then
60 I
GATE Previous Years Solved Papers : (fl I MADE EASY
) dee(v) =2s
) deg(\.,)+ ve\io
)deg(v)= veVo
@t"l
veV Ivlaximum components will resuit after removal
Since deg (v) is even for v€V", ihe first sum in of a node if graph G is a star graph as shorvn
belou'.
the right hand side of the equality is even. The
?
total sum must be 2e. which is even, so the second \.. ,,,
sum must be even too. But ail of its terms are '\
)i(i -,/
odd. so there must be an even number of them. ,/ul\
a'i'z'l\
Etot a
c-;-d
@t"l
') The number of perfect matchings in a complete
(d) Since all edge weights are distinct G has a graph of n vertices, where n is even, reduces to
unique minimum spanning tree. the problem offinding unordered partitions ofthe
vertex set of the type p(2n; 2,2,2,... n times)
@tal _ (2n) !
In a graph G with n vertices, maximum number (2!)" n!
= "(1-') .
of edges possible For n = 3, 2n = 6, i.e. complete graph Ku, we
2
There are two ways for a edge, (the edge may have
appear in graph or may absent in Craph). So there 6!
Number of perfect matchings =
are two options for each edge. (2!)3 3!
n(n_1)
Totalnumberofgraphswithnvertices = 2 2
6x5x4x3x2x7
=15
2 x2x2x 6
@rtr @ral
The graph containing maximum number of edges Given lnl <slvl-o ...(i)
in a n-node undirected graph without self loops Let 6 be the minimum degree of the graph.
is complete graph. Now 6 cannot exceed the average degree ofthe
The number of edges in complete graph with n- graph,
. n(n- 1) 2tEI
k
node-'n2 ls so. 6= lvl ...(ii)
Substitute eq. (i) in eq. (ii) and get
MADE EASY I Discrete and Engineering Mathematics 161
,
d< ,-t' -n
tu(3ivl-6) co
@<*t n'-n
An assigninent of the colors 7,2, 3 and 4 to the
vertices of the graph is shown belorv such thai n1
@t"t
NIax number of edges in a connected graph
is n - 1, which doesn't form any cycle.
a@
nt-n (^ nt-n ^ n'-n ^
2 n'-rn+_(:2 [t"--
...+-L
2 a2-r,
22 2
adjacent cells in K-L{ap (adjacencv has to seen Now consider subsets of 3 elements say
just as we do for minimization). That will give {1. 2, 3}. Since we want exactly 2 elements in
us a Bipartite graph. chromatic number for this common, we choose these in 3C, ways and then
-2. we can add or not add remaining n-3 elements.
Also from the same we can conclude that we This can be done in 2"-3 ways.
'need ,for a'n'bit string, to traverse NO MORE .'. Total number of subsets with at least 2
than (n - 1) edges or'n'vertices to get a path elements common with 3C, x
{1, 2, 3} is given by
between two arbitrary points. 2r-3.
So ratio is 2ln. Similarly, \rye can argue that the number of
Alternate Method degrees of4 element subsets is aC, x 2"-a and for
The hamming distance relation on bit strings 5 element subsets is 5C, x 2" 5 and so on.
has a digraph which wiil be always an n-cube Out of these 2n-2 - 2.2n 3 is less than 3C, x 2n-3
where n is the number of bits.
= 3 x 2n-3.
Chromatic number of n-cube = 2 (since n-cube Then3C, x 2n 3- 3 x 2" 3is same as
is always bipartite). AIso the diameter of n- a[^ y !n-a - 6 X 2"-1 = B x 2n-3
cube = n. and rC, ><. 2n 4 - 3 x 2"-s is greater than
So the ratio of chromatic number to diameter sgrx 2n-5 = 10 x 2r-5 * 2.5 x 2-z
of the n-cube = 2ln. .'. rnaximum degree in this graph is occurring
for 3 element and 4 element subsets both of which
@t> have3x2" 3degree.
Let S contains n elements then S have 2" subsets.
Graph G contains 2n r-ertices. @firat
Let S = {v, vr,..., vrrt. Two vertices of G are The number of connected component of G is
adjacent if and only if the corresponding sets determined by the degree and edges ofvertices
intersect in exactly two elements. there are n + 1 vertices whose degree is zero, so
so lVilni\,tl=2 they can form n t 1 connected component. The
For this to happen, the subset must have at least
remaining vertices of the graph G are all
2 elements.
connected as a single component. So total number
There are n sets which contains a single elements
ofconnected component is n + 2.
for V, to \ who doesn't intersect another set such
that it contains two elements. Therefore the
degree of all these n vertices is zero. G also
@tu
K. and Kr., are the smallest non planar graphs.
contains a vertex $ whose degree is zero, So the Ku has 5 vertices and 5C, = 10 edges and K3, ,
number of vertices whose degree is zero is n + 1. has 6 vertices and 3 x 3 = 9 edges. So, the non
planar graph with minimum nurnber of edges is
@t.l Kr., with 9 edges and 6 vertices.
Let the set be S = {1, 2, 3, 4, ..., n}
Consider a subset containing 2 elements of the Note:Kois the non planar graph with minimum
form {1, 2}. Now {1, 2} will be adjacent to any number of vertices.
subset with which it has exactly 2 elements in
common. These sets can be formed by adding zero
@rar
In topoiogical sorting the partial ordering ofthe
or more elements from remaining n - 2 elements,
DAG, must be preserved i.e. if a S b in the DAG,
to the set {1, 2}. Since each of these elements
then in the topological order, b must come after
may be either added or not added, number of ways
a, notbefore. Consider the ordering 3 2 4 I 6 5 .
of making such sets containing 1 and 2 is 2"-2.
1 < 4 in the given DAG but 4 is coming before 1
.'. Vertices with 2 elements will have in 3 2 4 1 6 5 order which means that 3 2 4 7 6 5
2"-2 degrees.
is not a topological order of the given DAG.
MADE EASY I Discrete and Engineering Mathematics 163
@tul I. 7, 6, 5, 4, 4, 3.2, 1
A tree with I node is not possible, since it is given 6,5, 4, 4,3,2,7 (Step 1)
that ever;, node has exactly 1 child. 5,4,3. 3,2, 1,0 (Step 2)
I
ioa.
I
is the tree has 0 nodes. i.e., choice (a). Sequence is a graph (Step a)
5. 5. 2.2.2. 1 (Step 1l
@rul @rat
The planar embedding of K., and Q" is shown The graph given is Ko.
below: In K6, every cycle of length 4 corresponds to
selecting 4 vertices out of 6 vertices. r.vhich can
3
be done in 6C* ways and then ordering the 4
vertices in circrilar permutation in 3! ways (since
vertices are Iabeled). So final answer is
6C+x3l-90'
@t"t r'LI."n,,,.,.\
/ \,
Use the Hauell-hahimi algorithm.
The sequence of steps in the algorithm for each
z)
graph is shown below: Total there a.re six possible minimum spanning
trees. [3 x2=6]
(u) tf, ff ffr is simple graph
b) (?'z?,2'2'2)
-
(1 1 2 2 2\
,=+ (2,2.2,1 ,.t,) @r"l
{ l. L l. I ) lS SlmDle :lraon The nr.rmber of edges in spanning forest ol a graph
= u_/
G with n vertices and k cornponents = Rank (G)
(c) (Q9stool - 12 2 O O O)
</
=+ (1, 1,0,0) =n-k.
cannot be a graoh since
(d) (3.uj,1,0)
neUative degree not possible
/l n n i n\
@tul
- I r,u!vr r,u/
-,
(1,1,0,0,0) is simp e graph
' )des = ze
=
Given 5> 3 also 6< 2eln e> n5/2
@s"t. =
+e>3ni2
tsipartite graph {u, u \ where u and v are Euler's formula:
partition on vertices: r = e - n * 2 > 3nl2 - n* 2> nl2 + 2
(a) {1, 11}
= 1 x 11= ll edges rnaximum So tlre number of faces is atieast nl2 + 2
(b) {2, 10} + 2x 70 = 20 edges maximum
(c) {3, 9} =+ 3 x 9 = 27 edges maximum @s"t.
(d) {4, 8}
= 4 x 8 = 32 edges maximum Number of vertices (n) = t0
(e) {5, 7l
= 5x 7 = 35 edges maximum d(r,) = 3
(0 {6,6}=6 x 6= 36edgesmaximum Number of edges (e) = ?
.'. N{aximum number of edges in a bipartite r = e - v + 2 (euler's formula for connected
graph on 12 vertices = 36 edges. planar graphs)
r=e-70+2=e-8 ...(1)
@rsl Since every region is bounded b5, exactly 3 edges
If a graph is isomorphic to its own complement, and since every edge is exactl;, double counted,
then it is a self complementary graph. In a self we have the equation
complementary graph e=3i12=r=2e13
Substituting this in equation (1) we get,
n(n -l\ 2el3=e-B
4
2e=3e-24+e=24
MADE EASY I Discrete and Engineering Mathematics 167
@tar @ s"t.
An n-vertex self-complementary graph has G has lVl = fOO vertices and
exactly half number of edges of the complete lEl =3ooedges
graph i.e. n(n-1)/4 edges. the weight of MST of G = 500
In MST:
Since n(n--1) must be divisible by 4, n must
Number of vertices = 100
be congruent to 0 mod 4 or 1 mod 4.
Number of edges = 99
@rtl If each edge of G is increased by 5 then MST
weight also increased. For each edge of old MST
An edge is called bridge iff it's removal will
increased with 5.
disconnect the graph into components.
Total 99 edges. So 99 x 5 = 445 is increased
In a cycle there are two paths between every
Total weight of new MST
pair ofvertices and so removal ofan edge from
= 500 + 445 = 99b
a cycle does not disconnect the cycle. So a bridge
cannot be part of a simple cycie. @s"t.
Four color theorem says that every planar graph
@sot" can color with 4 colors i.e. four colors are sufficient
no : Number of leaf nodes (degree 0) to properly color any planar graph.
n, : Number of nodes with degree 1
EIII
ru, : Number of nodes with degree 2
We have following two equations for binary tree
5.10 Seven (distinct) car accidents occurred in a week. child. What is the probabiiity that a randomly
What is the probability that they all occurred on picked child belongs to a family with two
the same day? children?
1 1
(a) 3t23 b) 6t23
(a)
T e)F (c) 3/10 (d) 3/5
7
[2004: 1 Mark]
@V
1
(d) -
2', 5.16 Let X and Y be two exponentially distribuied and
[2001:2 Marks] independent random variables with mean cv. and
p, respectively.lf Z = min fi,Y), then the mean
5.11 Four fair coins are tossed simultaneously. The of Zts given by
probability that at least one head and one tail (a) (1/(ct + B)) (b) min (cr, 0)
turn up is (c) (s0/(s + 0)) (d)cr+B
(.)
1 1 {2004 :2 Marksl
G &)
8
5.17 An examination paper has 150 multiple-choice
7 15
G) (d) questions of'one mark each, with each question
, 16
having four choices. Each incorrect answer
{2002 z 2 Marksl fetches - 0.25 mark. Suppose 1000 students
5.12 Let P (E) denote the probability of the event E. choose all their answers randomly with uniform
Given P (A) = 1, P(B) = 712, and A and B are probablity. The snm total of the expected marks
independent, the values of P (A I B) and PG lA) obtained by all these students is
(a) o (b) 2550
respectively are
(c) 7525 (d) e375
(a) 1l4, Ll2 k 7l2, tl4
(c) 712. t (d) 1, Ll2 [2004:2 Marks]
[2003: l Mark] 5.18 Two n bit binary strings, S, and S, are chosen
randomly with uniform probahlity. The
5.13 A program consists of two modules executed probability that the Hamming distance between
sequentially. Let f, (t) and f, (t) respectivel5, denote these strings (the number of bit positions vihere
the probability density functions of time taken the two strings differ) is equal to d is
to execute the two modules. The probability (a) "Cu/2" (b) "cdl2,1
density function of the overall time taken to (c) d/2" (o il2d
execute the program is given by [2004:2 Marks]
5.19 A point is randomly seiected with unifonn
(a) f, (t) + f, (t) (t) If,(")r,(*)a"
0
probabilitv in the X-Y. Plane w'ithin tire t'er:tangle
with corners at (0. 0), (1, 0), (1, 2) and (0, 2). If p
Gl ir,1*;rr1t - x)dx (d) max {f1(t), f2(t)} is the length of the position vector of the point,
0 the expected value ofp2 is
[2003:2 Marks] (a) 2tB (b) 1
@) at\ (d) 5/3
5,14 If a fair coin is tossed four times. What is the
[2004:2 Marks]
probability that two heads and two tails will
result? 5.20 Let f(x) be the continuous probability- density
(a) 3/8 function of a random variable X. The probabiiit5,
b) 1t2
(c) 5/8 (d) 3/4 thata<X<b,is
(a) f (b-a) (o) f(b) - f(a)
[2004: l Mark]
b b
5.15 In a population of N families, 50% of the families
1.; Jrt")a" 14 Jxf(x)tlx
have three children, 30% of the families have two
children and the remaining families have one [2005: l Marki
70 1
GATE PreviousYears Solved Papers: !f,1 I MADE EASY
5.2L Abagcontains 10blue marbles, 20 green marbles 5.26 Suppose we uniformly and randomly select a
and 30 red marbles. A marble is drawn from the permutation from the 20! permutations of 1, 2,
it is put back in the
bag, its colour recorded and 3,...,20. What is the probability that 2 appears
bag. This process is repeated 3 times. The at an earlier position that any other even number
probability that no two of the marbles drawn have in the selected permutation?
the same colour is
tu)-
1
1
(a) 1i36 &) 1/6 (u)
z 10
@) lta (d) ii3
IIT-2005 : l Markl (c)
9!
(d) Ncne of these
zor
5.22 An unbiased coin is tossed repeatedly until the
[2007:2 Marks]
outcome of two successive tosses is the same.
Assuming that the trials are independent, the 5.27 In a rnulti-user operating system on an avelieqe.
expected number oftosses is 20 requests are made to use a particulal resoiil"ce
(a) 3 o)4 per hour. The arrival ofrequests {blows a Pcisson
(c) 5 . (d)6 distribution. The probability that either one,
IIT-2005 :2 Marksl three or five requests are made in 45 minutes is
given by :
5.23 In a certain town, the probability that it wiII rain (a) 6.9 x 106 x e-20 &) 1.02 x 106 x e-20
in the afternoon is known to be 0.6. Moreover, (c) 6.9 x 103 x e-20 (d) 1.02 x 103 x e-20
meteorological data indicates that if the
UT-2007:2 Marksj
temperature at noon is less than or equalto2Soc,
the probability that^rit will rain in the afternoon 5.28 A sample space has two events A and B such
is 0.4. The temperature at noon is equally likeiy that probabilities
to be above 2SoC, or atlbelow 25"C.
P(An B)=tlZ. P(A) = 1/3, P(B) = Ug.
What is the probability that it wiII rain in the
What is P(A u B)?
afternoon on a day when the temperature at noon
(a) tll72 (b) 10/12
is above 25'C?
(c) 9172 (d) 8/12
(a) 0.4 (b) 0.6
(c) 0.8 (d) 0.e UT-2008: l Markl
UT-2006: 1 Markl 5.29 What is the probabiliti, that in a randomly chosen
group of r people at least three people have the
5.24 [4ren a coin is tossed, the probability of getting
same birthday?
a Head is p, 0 < p < 1. Let N be the random
variable denoting the number of tosses till the
(a) 1- 365.364...(365-r+1)
first Head appears, including the toss where the 365'
Head appears. Assuming that successive tosses
365.364...(365*r+1)
are independent, the expected value ofN is &) 1* ,Jbi)
(a) 1/P o) 1/(1 - P)
(c) 1/P2 (d) 1/(1 - P2) 364.363...(364 - (r - 2) +7)
'c2.365.
364',-2
[IT-2006 :2 Marks]
5.25 Suppose there are two coins. The first coin gives (c)
, 365.364...(365-r+1)
heads with probability 5/8 when tossed, while the 365'
second coin gives heads with probability 1/4. One (r
'c, .365 . 364.363...(3 64 - - 2) + 1)
of the two coins is picked up at randomwith equal 364',-
probability and tossed. What is the probability of
obtainingheads?
365.364...(365-r+1)
(d)
365"
(a) 7/8 b) il2
(c) 7176 (d) 5/32 IIT-2008: 2 Marksl
IIT-2007: l Markl
MADE EASY I Discrete and Engineering Mathematics 171
5.40 Suppose a fair six-sided die is roiled once. If the 5.46 Let S be a sample space and two mutually
value on the die is 1, 2 or 3 then die is rolled a exclusive events A and Bbe such thatA u B = S.
second time. What is the probability that bhe sum If P(.) denotes the probability of the event, the
total ofvalues that turn up is at least 6? maximum value of P(A) P(A is
(a) 70127 b) 5t12 [2014 (Set-3):2 Marks]
(c) 213 (d) 1/6 5.47 Suppose Xrfor i = 1,2,3 are independent and
-.
12012:2 Marksl identically distributed random variables whose
5.41 Suppose p is the number of cars per minute probability mass functions are PrlXr=01= Pr[Xi
passing through a certain road junction between = l1 = 712 for i = l, 2, 3. Define another random
5 PM, and p has Poisson distribution with mean variable Y= XrXr@ X, where @ denotes XOR.
3. Wha+" is the probability of observing fewer than Then Pr[Y = 0 lX, - 0] =
3 cars during any given minute in this interval? [201"5 (Set-3) rZ Marks]
(a) 8/(2e3) (b) 9/(2e3)
5.48 A probability density function on the interval
(c) L7l(2eB) (d) 261(2eB)
[o, 1] is given by Tlxz and outside this interval
[2013:1Mark] the value of the function is zero. The value of o
5.42 Suppose you break a stick of unit length at a is
point chosen uniformly at random. Then the (Set-l): l Mark]
[2016
expected length of the shorter stick is_.
(Set-l):1Mark] 5.49 Consider the following experiment.
[201a
Step 1. Flip a fair coin twice.
5.43 Four fair six-sided dice are rolied. The probability Step 2. If the outcomes are (TAILS, HEADS)
that the sum of the results being 22 is X7296. then output Yand stop.
The vaiue of X is Step 3. If the outcomes are either (HEADS,
[2014(Set-l):2Marks] HEADS) or (HEADS, TAILS), thenoutputNand
5.44 The security system at an IT office is composed stop.
of 10 computers of which exactly four are Step 4.If the outcomes are (TAILS, TAILS), then
working. To check whether the system is go to Step,1.
functional, the officials inspect four of the The probability that the output of the experiment
computers picked at random (without is Yis (up to two decimal places).
replacement). The system is deemed functional (Set-l):2 Marks]
[2016
if at least three of the four computers inspected -
are working. Let the probability that the system 5.50 Suppose that a shop has an equal number of
is deemed functional be denoted byp. LED bulbs of two different types. The probability
Then looP of an LED bulb lasting more than 100 hours
given that it is of Type 1 is 0.7, and given that it
r 2oL4(set-z) : I Markl
is of Type 2is 0.4. The probability that an LED
5.45 The probability that a given positive integer lying bulb chosen uniformly at random lasts more
between 1 and 100 (both inclusive) is NOT than 100 hours is_.
divisible by 2,3 or 5 is
[2016 (Set-2): l Mark]
[2014 (Set-2):2 Marks]
IIII
MADE EASY I Discrete and Engineering Mathematics 173
5.1 (c) 5.2 (c) 5.3 (d) 5.4 (c) b.c (d) 5.6 (b) 5.7 (c) 5.8 (c) 5.9 (d)
5.10 (b) 5.11 (c) 5.Lz (d) 5.13 (c) 5.t4 (a) 5.15 (b) 5.16 (c) 5.t7 (d) 5.18 (a)
5.r9 (d) 5.20 (c) 5.2t (b) 5.22 (a) 5.23 (c) 5.24 (a) 5.25 (c) 5.26 (d) 5.27 (b)
5.28' (b) 5.28 (c) 5.30 (c) 5.30 (a) 5.32 (b) 5.33 (a) 5.s4 (a) 5.35 (a) 5.36 (c)
5.37 (d) 5.38 (a) 5.39 (c) 5.40 (b) 5.41 (c)
Prob*Sillty
@rtc; @tal
(a) P(A n B) = P(A) P(B) is false since this is true P(Rain today) = 9.5
if and only ifA and B are independent events. P(Rain tomorrow) = 0.6
&) P (A u B) = P(A) + P(B) is false since P(A n P(Rain today u Rain tomorrow) = 0.7
B) is zero if and only if A and B are mutually P(Rain todayn Rain tomorrow) = ?
exclusive. P(rain today n Rain tomorrow)
I B) - P(A n B)/P(B) is true.
(c) P (,q. = P(Rain today) + P(rain tomorrow) - P(Rain
(d) P (A u B) < P(A) + P(B) is false. today n Rain tomorrow)
Since P(A u B) < P(A) + P(B) So; 0.7 = 0.5 + 0.6 - P(Rain today n Rain
Et* 25
tomorrow)
P@ain today n Rain tomorrow)
= 0.5 + 0.6 - 0.7 = 0.4
tory / ,,N
I \t;B So, the probability that it will rain today and
2 tomorrow is 0.4.
,* / \ru @or
Bag contains 10 white balls and 15 black balls' Probability of getting an odd number in rolling
Required probability
'3 1
10x15 ofadie=
1
6=r.
,U
C, 25x24 2
Now using binomial distribution
-=- P(Exactly one odd number among three
outcomes)
E,.i]
P(atleast one of dice will have 6 facing
= 1 - P(none of dice have 6 facing up)
=
,6,Il]'[l)'
'\2) \2)
- [s 51 25 11
- l-l-X-l=1--=-
L6 6.1 36 36 = srIl']' =-d8
\2)
@, E,&l
The probability that the bottom card of a
If all the points have X < 5, then expectation of a
,i
because there random variable X is surely less than 5. So
randomly shuf{led deck is ace =
, according to this there should be atleast a sample
are 4 aces out oftotal c2 cards. point at which X 2 5.
From the remaining 3 aces out of 51 cards the
and P(E,
^
Er)=
1
:5 @t'l
p(atleast one head and one tail)
(a) P(E, or Er) = 1 - p(no head or no tail)
= P(E1) + P(Er) - P(8, n Er) = 1 - [p(no head) + p(no tail) - p(no head and no
tail)l
11119
= 1- [p (all tails) + p(all heads) - 0]
23 5 30
Ho'"vever given in option (a) is 2/3. =r--l*1-ol=r-2
- =r-
'
l=L
So option (a) is not true. l2n zo _j 16 8 8'
(b) For independent events Or
P(E, n Er) = P(E,) P(Er) Alternate Method:
We need atleast one head (> 1 H) and atleast one
Here. P(E, .,E)=? tail (> 1 T). First we satisfy > 1H as follows.
1H,37
2H,27
_111
P(Er) P(E2) 3H. 1T.
= ,*i= 6 and 4H,07
So;(P(E, nEr)* P(81) P(E2) now to satisfy the second condition of > 1 T, we
have to remove 4 H, 0 T.
So event E, and E, are not independent.
So, the favourable cases are only 1 H, 2 H and 3
Option (b) is not true. H.
(c) Since E, and E, are not independent The probability of this by binomial distribution
'
So option (c) is true. formula is
oc,,**Q*tc.,=7
(d) P(E,nEr) 3 = 2'2"21g
P(EI/E2) =
-F.'- =;
So option (d) P(E1/E2) = 4/5 is false.
@or
@ro Given P(A) = f
Constraints are
P@) = tl2
Since both events are independent
(, P(E1) = P(Er) = x
(n) P(E, u Er) = 1 P(AlB)=P(A)=1
P(B lA) =P(B) = 112
(iir) E, and E, are independent so
P(E, n Er) = P(Er) P(Er)
=1X1=12
@t"l
Let the time taken for first and second modules
Now,
be represented by x and y and total time = t.
P(E, u Er) = P(E,)+P(Ez) - P(E, n Er)
.'. t = x + y is a random variable.
1 =x*x-x2. Now the joint density function
I = 2x-x2
x2-2x+1 =0 g(t) = Jo'f(x,
y)dx
(x- 1)2 =9
rt
x =1 = Jnf(x, t - x)dx
So; P(Er) =P(E 2) =.x= 7
rt
= Jn i (x) f, (t - x)dx
@rur which is also called as convolution of f, and f,
Sample space = 77
abbreviated as f, * fr.
All accidents on the same day = 7 ways (all on
Correct answer is therefore, choice (c).
Monday, all on Tuesday. . .)
So. requiredprobability = ! = + .
" '7', 70
MADE EASY I Discrete and Engineering Mathematics l7s
tc, = 114-311"6
O!)
= marks
111,6
21 168 Total marks expected for 150 questions
75
@,tul = 1/16 x 150 =
5 marks per student
100 Families
50 (3
,,,N
child)
Total number of children
30 (2 child) 20 (1 child)
Total expeited marks of 1000 students
So
- !!8 ,1000 = 9375 marks
=50x3+30x2+20x1=230
Favorable cases =^The number of children who
Et"lIf hamming distance between two n bit strings
come from 2 children families is d, we are asking that d out of n trials to be
=30x2=60 success (success here means that the bits are
So the probability that a randomly picked child
different). So this is a binomial distribution with
belongs to a 2 children families
n trials and d successes and probability ofsuccess
= 601230 = 6123
P = 214=ll2
@t.l (Since out of the 4 possibilities {(0,0), (0, 1), (1,
0), (1, 1)) only two of them (0, 1) and
f(x) - x.e-M, x)- o
(1, 0) are success)
X and Y are two independent exponentially
distributed random variables. Let )', and 1., So p(X = d) - 'C, (712)d Gl2)n-d
parameters of X and Y respectively. tcu
=
P(X>x)=s-Lt, x)O 2n
-().. +)..,
=€
)-Y
'
1
P(X=2)=Zlq
- I x' 1.dx Similary for X = 3 only THH and HTT are
J
0 favourable out of total 8 outcomes.
r So, p(X = 3) = 218
lx"lo11 .l
X 2 4 5
lv'l' 8 4
D
Given P(RA) = 6.6 (Fiti the first 2 places with 2 of the 10 odd
by rule of total probability P(RA) = numbers and then the remaining 17 piaces with
11 remaining 17 numbers) and so on until'2'is in
-x0.4+-xx - 0.6
11th place. After that it is not possible to satisfy
6oir, 1
1.02x106xe-20
-!/8- 11
@,m
114 P(A U B) = P(A) + P(B) -P(A n B)
crinz H
= (1 - P(A')) + (1 - P(B)) - p(A n B)
1511 7
= (1 - 1/3) + (t - ll}) - tlz
P(H) = -x-+-x-
2824 16
= 4/3 - ll2
= 516 = 1.Oll2
@.i{d}
Number of permutations with '2' in the first @t{el',
position = 19! P(at least three people have the same birthday)
Number of permutations with '2' in the second = 1 - P (all have different b'days)
position=10x18!
- P(exactly
two people have same b'day)
(Fill the first space with any of the 10 odd Now, P(a11 have different b'days)
numbers and the 18 spaces after the 2 with 18 of
the remaining numbers in 18! ways) _ 365.364...(365-r+1)
365.
Number of permutations with'2'in 3"d position
=10x9x17!
78 I
GATE Previous Years Solved Papers : !$ | MADE EASY
P(exactly two people have same b'day) p(z < -1) = p(z 2 1) ... (ii)
364.363...(3 64 - (r - 2) + 7) Comparing (i) and (ii) we can say that
= "c2'365' 364'.-2 a =r + oy=3
['C, ways to choose who those two people with oy
same b'day are, 365 ways to choose what the
b'day is] @tur
Now, It is given that
P (at least three people have the same birthday) P(odd) = 0'9P(even)
365.364...(365-r+1) Now since lp(x) = 1
365' p(odd)+p(even)=1
Which is option (c). + 0.9p (even)+p(even)= 1
@tol + p(even) =
Lg
1
= 0.5263
Let C denote computes science study and M
Now, it is given that p (any even face) is same
denotes maths study. The tree diagram for the
probiem can be represented as shown below: i.e. p(2) = P(a) = p(6)
Now since,
Monday Tuesday WednesdaY
/
11
, .rC \ ^\,,C = E o(even)= 3 (0.5263)
o\v ,.)ru, = 0.1754
It that
is given
Now by rule of totai probability we total up the
p(evenlface >3)=0.7S
desiredbranches (/) and get the answer as shown
below: p(even nface > 3)
= p(f".", "J) = o'75
p(C on monday and C onra'ednesday)
= p(C on monday, C on tuesday and C on p(face = 4,6)
wednesday) + p(C on monday, M on tuesday and +----------.----_tt.75
R(face > 3)
C onwednesday)
= 1x9.4x0.4+1x0.6x0.4 + p (face rsl = dgt":
a'6)
= 0.16 + 0.24 = 0.40 0.75
d4ry1@ _ o,t7b4+0.1.754
@ta). 0J5 0.75
Given 1tx = 1, o*'= 4 = ox = 2 and p, = -1. o" is
unknown
= 0.4677 = 0.468
given, p(X<-l) = pg>2)
Converting into standard normal variates,
@tat
f zSrl
-1-u ) I z>rl
pl
2-u \ 9-- @A;ilr.ts>
-t-
Pl ---
\o*) \or)
)rt >- dectarednotfaulty
/ -r-r)
ol'=
( - z- (-1))
Plzz-l \1-P\ r-3- @.ildr*ED
2 ) Ior) notfaulty -//''
/ 3)
plz>-
uv,/I
P(z < -1) = ...tii
\ The tree diagram of probabilities is shown above'
Now since us know that in standard normal From above tree, by rule oftotal probability,
distribution, p(declared faulty) = pq + (1 - p) (1 - q)
MADE EASY I Discrete and Engineering Mathematics l7e
= p(H,H)= I @rul
4 If first throw is 1, 2 or 3 then samplespace is
p(AuB) - p(at least one head) only 18 possible ordered pairs. Out of this only
o
n (1, 5), (1, 6), (2, 4), (2,5), (2.6), (3, 3), (3, 4), (3, 5)
p(HH, HT, TH; = - and (3, 6) i.e. 9 out of 18 ordered pairs gives a
4
Sum > 6.
So required probability = #ot+ =:u Iffirst throw is 4, 5 or 6 then second throw is not
made and therefore the only way Sum > 6 is if
the throw was 6. Which is one out of 3 possible.
@tel So the tree diagram becomes as follows:
V(x)=E(xz)-[E(x)]2=P
where V(x) is the variance of x,
80 I
GATE PreviousYears Solved Papers: !p I MADE EASY
a,5,6ASum>6 ,1\
4W/ I \ONW
From above diagram 4
1911 15 5
sw / \rxw
p(sum ) 6) = _v_I_v_
2t823 -
36 L2 4w oNw
Required probability
ncr.uc, ncn. uco
Poisson formula for (P = x) given as =---lii-
u4 'ocn
L*
"-r 24L25
"! 2to 2to 210
u = 3 cars/minute p = 0'1190
AT = 1 minute
Sol"=aAT=3x1=3 + 100P = 11'99
= #--t.,'(#).=, = -2<0
MADE EASY I Discrete and Engineering Mathematics 181
lt 1l
-Lr-;l
The p.d.t. for X, X, and X, as given in =,
problem is shown below.
1 _o
x2 lo i x3 --z
;;E; *,I
a
o=,
1
= 0.5
GivenY=XrXr@Xr.
The required probability = pg = 0lX3 = 0) @sot,
p(Y = 0nX =o)
.,.(1)
P(X, = 6;
0.-yH- outPut Y
Now, r< o!_p_ Nstop
p(Xs = o) llz (from p.d.t. of X3)
= ...(2) o\rZ"F?-Nstop
pCY=0nXr=6) DrPr- output Y
o.B-7
= p({,E @ Xr="0 n Xr= 0) The tree diagram for the problem is given above.
=p((XrX2@0)=0nXr=0) The desired output is Y.
=p(XtXz=0nXs=0) Now by rule of total probability
p(output - Y) = 0.5 x 0.5 + 0.5 x 0.5 x 0.5 x
= p(Xr= 0, Xz= 0, Xs= 0) + p(Xr= 0, Xr= 1,
Xs = O)+p(Xr = 1, Xz = 0. Xe = 0) 0.5 +...
Infinite geometric series with
111111111 3 o=0.5x0.5
= -X-X-+-X-X-+-X-X-
222222222 = -8
and r=0.5x0.5
o','I o'l
SopG=0nXr=g;= I ...(3) sop(output = Y) = 1 - 0.5 x
,, = 9'?5
0.5 0.75
@,mlr 0.4
+1osts > 100 hrs
Type 2
1
Given, l9c) =7 a<x<1 P(losts > 100 hr) = 9.5 x 0.7 + 0.5 x 0.4
-0 elsewhere .= 0.35 * 0.2 = 0.55
1
rIII
tft,o =r
Linear Algebra
6.1 If a, b and c are constants, which of the following O) If m < n and B is the zero vector, then the
is a linear inequality? system has infinitely many solutions.
(a) ax+bcy=0 (s) ax2*sy=21 (c) Ifm = n and B is non-zero vector, then the
(c) abx + a2y ) 15 (d) xy + ax > 20 system has a unique solution.
(d) The system will have only a trivial solution
[1987:2 Marks]
when m = [, B is the zero vector and rank
A square matrix is singular whenever: (A) = n'
(a) The rows are linearly independent [1996: l Mark]
O) The columns are linearly independent
. lcos 0 - sin 0-l 0l
(c) The rows are Iinearly dependent 6.6 The matnces I I and [a
(d) None of the above lsin0 cos0l L0 bl
[1987:2 Marks] commute under multiplication
(a) if a = b or 0 = nr, n is an integer
If A and B are real symmetric matrices of size (b) always
n x n. Then, which one of the following is true? (c) never
(a) AAi = I &) A=A-t (d) ifacos0*bsin0
(c) AB = BA ^' (d) (AB)t = ea
[1996 : 21]Iarksl
[1994:2 Marks] 6.7 The determinan t of the matrix
The rank of the following (n + 1) x (n + 1) matrix, ta-81 1l
where a is a real number is ln 2 4 6l
laa'
lo o 4 8l
is
at
Lo o o -1]
1aa' a' (a) 11 &) -48
(c) o (d) -24
[1997:1Mark]
6.8 Let a=(a,/ be an n-rowed square matrix and I,
1aa' a'
be the matrix obtained by interchanging the first
(a) 1
and second rows of the n-rowed Identity matrix.
Then AI, is such that its first
@2
(c) n (a) row the same as its second row
(d) Depends on the value of a (b) row is the same as the second row of A
[1995: l Mark] (c) column is the same as the second column A
(d) row is aII zero
6.5 Let AX = B be a system of linear equations where
A is an m x n matrix and b is a m x 1 column
[1997:2 Marks]
vector and X is a n x 1 column vector of unknown. 6.9 Consider the following set of equations
Which of the following is false? x+2Y=$
(a) The system has a solution if and only if, both 4x+ $Y = 12
A and the augmented matrix [A B] have the 3x+6Y+32=15
same rank. This set
MADE EASY I Discrete and Engineering Mathematics 183
[1998:2 Marks]
6.11 Consider the following determinant
[o o o -1]
12A02:2 Marksl
It a bcl
6.77
l=11 b cal
Consider the following system of linear equations
lr " uul lz
t 1 -allxl
I ltl lcxl
i4 3 -r2llvl=l5l
Which of the following is a factor of A?
(a) a-=b (o) a-b ,
[r -, )1,) Lr]
(c) a+b+c (d) abc Notice that the second and the third columns of
[1998:2 Marks] the coefficient matrix are linearly dependent. For
how many values of cx, does this system of
6.12 An n x n array v is defined as follows;
equations have infinitely man5, solutions?
v[i,i] = i-j for al]i, j, 1 si< n, 1 <j < n (a) o (b) 1
The sum of the elements of the array v is (c) 2 (d) infinitelymany
(a) o (b) n-1
(n+1)
(c) n2 -3n+2 "
(d) n-
, 6.18 Let A, B, C, D be n x , *rr-r""::'"::;:T;:::
[2000: l Markl zero determinant, if ABCD = f, then
B-1is
(a) O-t C-1A-1
lzoool
8 &) CDA
6.13 The determinant of the *at.i* | : ', 3 | t. (c) ADC
ln o 6 ,] (d) does not necessarily exist
(a)4 &)0 [2004:1Mark]
(c) 15 (d) 20
6.19 What values of x, y and z satisfy the following
[2001 : l Mark] system of linear equations?
6.L4 Consider the following statements:
Sr: The sum of two singular n x n matrices may
[iIt ,B ,.1[,] [ul
4llyl=l8l
be non-singular
Sr: The sum of two n x n non-singular matrices
l, , ,ll;l L,rl
(a)x=6,!=3,2=2
may be singular (b)r=12,y=3,2=-4
Which of the following statements is correct? (c)x=6,y=6,2=-4
(a) S, and S, are both true (d)r= 72,y=-3,2=0
ft) S, is true, S, is false IIT-2004: l Markl
84 1
GATE PreviousYears Solved Papers: (S I MADE EASY
rl 1xr-2xr+ 5xu = 2
lo oo oo oo o 1 3 il
o o 1 8.1,,,
-x1-4xr*x, =3
Lo This system ofequations has
What is the value of the determinant ofA? (a) no solution
@) a unique solution
,r, r*.6 1"I s.,6:z I.[ u- G ]" i
;.,6_ zl
(c) more than one but a finite number of solutions
"1.2)[zJr]l,2)|zJs]
1
(c) X ts not a subsPace for Rii Which one of the foilorving cpiicns plovides the
(d) None of the above CORRECT values of the eigenvaiues of the
. t?ts{J7 :2 Marksl n:.atrir?
of equations (a) 1, 4, 3 0r) 3, 7. 3
6.30 The following svstem
Xt*xz*2x"=i (c) 7, 3, 2 (C) 7,2, 3
[2011 :2 Marks]
xr*2x.r+3x. =2
xr * 4xr * ax, ='1 6.35 Let Al:e the 2 x 2 matrix with elements ar, = a,,
has a unique salution' The c'nlv possi-ble variue(s) =321=+1anddz2=.-7'
lbl a is/ale Then the eigenvalues of the matrixAle are
(a) o (a) 1024and-1024
(.o) eithei'0 or 1
ftr rOZ+VE and -1g2 av'[
(c) one of 0' 1 or -1
(d) an-v real number other than 5 ic) +.lE and -4f
[2008: l Mark] tcir 512rro and -512,[
120L2: l Markl
6.31 How manv of the following matrices have an
eigenvalue 1?
6.36 Which one of the following does NOT equal
tr ol [o 1l [1 -1ru"d [-t o I
t
11 x ol
x-i
l"l
[o o]'Lo o]'11 1 .l ,- i -1 ll- t'
l"l
i'- I '.'
51: Each row of NI can be represented as a linear icl lo y - z l'' - z2l tdt y+z y2
6.38 The value of the d ot product of the eigenvectors 6.44 Consider the following2x2 matrixAwhere two
corresponding to an5, pair ofdifferent eigen values elements are unknow'n and ale marked b-v 'a'
of a 4-by-4 s-v-mmetric positive definite rnatrix and 'b'. The eigenvalues of this rnatrix are -1
IS and 7. What a.re the vaiues of 'a' and 'b' ?
[2014 (Set-l) : 1 1\Iark] tl
A=!1
ib ct)
6.39 If the matrix :4 is such that '(O;;=4,ts=6
tzl
tt
(a) a=6,b=4
A=l-qiti e 5l (c) a=3,tr=5 (d) a=5,b=3
tllal
L/,1 [2015(Set-tr):2Marks]
then the d.eterminant of A is equal to 6.45 The larger of the two eigenvalues of the matrix
ft ql
[2014(Set-2):lMark]
-. l' "ii.
The product of the non-zero eigenvalues of the
12 1l
[2015 (Set-2): l Mark]
matrix
6.46 Pei'form the follorn ing operations on the matrix
1 000 1l
0 111 ol Is I 15.l
0 111 0l )t 9 tosl.
0 111 ol Lr, 2 1e5 ]
1 000 1.1
1. Add the third row to the second row.
2. Subtract the third column from the first
[2014 (Set-2):2 Marks] column.
The determinant of the resultant matrix is
6.4L Which one of the following statements is TRUE
about every n x n matrix with only real [2015 (Set-2):2 Marks]
eigenvalues?
[r -1 21
(a) if the trace of the matrix is positive and the
6.47 In the gi.'en matri* |g
-t o one of the
determinant of the matrix is negative, at least l.
one ofits eigenvalues is negative. [r z 1)
ft) If the trace of the matrix is positive, aII its eigenvalues is 1. The eigenvectors corresponding
eigenvalues are positive.
to the eigenvalue 1 are
(c) If the determinant of the matrix is positive,
(a) {a(4,2,7) la * 0,a e lR}
all its eigenvalues are positive.
(d) If the product of the trace and determinant of b) {aGa,2,l)la * 0,a e 1R}
the matrix is positive, all its eigenvalues are (c) {a(Jt. C.t )la * 0.a e R}
positive.
[2014 (Set-3): l Mark] (d) {o(_JT, 0,1) la + o,a e R}
6.43 The minimum number of arithmetic operations if the diagonal clements of U are both 1, then the
required to evaluate the polynomtal P(X) = )F + lower diagonal entrl' ! r" of L is _.
4* + 6X + 5 for a given value of X, using only [2015 (Set-l): l Mark]
one temporary variable is
[2014 (Set-3): l Mark]
-.
MADE EASY I Discrete and Engineering Mathematics 187
6.49 If the following system has non-trivial solution, 6.51 Consider the systems. each consisting of m linear
Px+qY*rz=0 equations in n variables.
qx+ry*pz=0 I. If m < ru, then ali such systems have a
rx+p!*qz=O solution-
then which one of the following options is TRUE? fI. If nr. > n, then none of these sytems iras a
' (a) P-q+r=0orP=Q=-r solution.
tb) p + q-r= 0 orp = -Q=r III. If m = n, then there exists a system which
(c) p+e*r= 0orp=q=r has a soiution
(d) P- Q*r= 0orp =-q=-r Which one of the foliowing is CORRECT?
(a) I, II and III are true
[2015 (Set-3):2 Marks]
(b) Onl-v II and III are tr,-re
6.50 Trvo eigJenvalues of a 3 x 3 reai matrix P are (c) Only III is true
(d) None of them is true
Q+ '[;) and 3. The deterriinant of Pis [2016 (Set-2] : 1 i\{arkl
[2016 (Set-l): l Mark] Suppose that the eigenvalues of rnatnxA are 1,
2, 4. The determinant of (A-1)r is
[2016 (Set-2): l Mark]
IIIT
6.1 (c) 6.2 (c) 6.3 (d) 6.4 (a) 6.5 (c) 6.6 (a) 6.7 (b) 6.8 (c) 6.e (b)
6.10 (a) 6.11 (b) 6.tz (a) 6.13 (a) 6.74 (a) 6.15 (c) 6.17 (b) 6.18 (b) 6.19 (c)
6.20 (d) 6.21 (b) 6.22 (c) 6.23 (c) 6.24 (b) 6.25 (b) 6.26 (d) 6.27 (a) 6.28 (b)
6.2e (b) 6.30 (d) 6.31 (a) 6.32 (d) 6.33 (d) 6.34 (a) 6.35 (d) 6.36 (a) 6.41 (a)
6.44 (d) 6.47 (b) 6.49 (c) 6.51 (c)
Explanations Linear Algebra
Lc ct )
soh-rtion and if Ll is zero t ector then the
l, is the matrix obtained b.v inter-changrng the
system have oniy a trivial soiution.
first and second rou, of the Identity Matrir I.
(iir) If matrix A and matrix [AB] have same
rank which is less than the number of So T,.,=1,
[o rr
n
variables. then ihe system has infinite I I
L]
(i I
@t"l x*2v=5
{r: + 8r-= 12
n_[.ntt -sin0l
1\= 3x+6)- +32=75
[sine coso _] Above set of equations calf be rvritten as
la 0'l -1 u or-x.l .]
I 8 olly =lizl
rrl._l
s [cos0 -sin0-][a
= =i.,0 .o.e -l[o
0-]
[3 6'3,][x_ 115.]
b-] Augmented matrix [AB] is given as
12 R2 ,R- -.1R1
AB = BA iff
- b sin 0 = -a sin 0 l---R.-R. lR,-
andasin0=bsin0 1363 151
Both are same equation which is tr 2o -1
DI
(a-b)sin0=0
whose solution is a = b or,0 = * nfi lo o o -8 Il- R,-R1
[oo3 ol
@<rl [r 2o --1
Dl
lo o 0l
l
[a -8 1 1l [ooo -81
lo 2 4 6l The rank of matrix A is 2 and rank of matrix
lo o-r 8l [AB]is 3.
Lu o o -1]
Therefore, ihe system is inconsistent and has no
solutions.
MADE EASY I Discrete and Engineering Mathernatics l8e
@r,i @t"l
The rix is
le 91tvel miLatri ir The matrix V can be defined as
Ir 4 87 0 -1 -2 ("-r)
I
0 30 1 0-1 ("-z)
!o 10
t4 2 31 2 :
l"
ILd 72 24 21t1 :
("-r) ("-z) : 0
-d 3iR1
nce.R1,=-o
Sinr
So above isantisymmetric matrix and the sum
lnk,+44I
anl
Ran
of the elements of ant' antisymmetric matrix
rw tr
Nov
ow ari'ank of o
try frfortt ara
is 0.
I 4 8l
It +l
OR
in) 0 ol
=-3x
=-o IIr Alternate Method:
"l 2l
I
2 tt 14
1"1
I dl n(n-*t)
14
>.ii-j
L/L/ J =.).
Ll , -in
=- -.1 x-74=52+
X_-lt j--7 i=l )=7
Rannk
... R :fsgiiver)nm aatr:ix ,)
ol
n(n +1) n:(n + l)
= -22 x/?--_------ -0
@tr
The determinant of a matrir can't be affected bv
elemerrta 11' r'ow, operations
@r"l
lzoool
So: llI bi bcl
lr
The matlix is
lE L 7 2l
l
-\= ca1 I
lcnbl i2420
Rr-+Rr-R,
Le06r_
Finding the determi.nant by expanding the first
R, -'R, - R,
row of the matrix
, bc
i, (b-u) ir 72
(ca-bc)i
I
D ol
^= l0 Detelminant = ZIO 2 o = r*riu 1j
]o (. - u) (ab - bc)
6 1l
io
It a bc =2x:1x(2)={
= lo (b-a) -c(b-a) Therefore, the dete:rminant of given matrix is 4.
0 (c - a) -b(c - a)l
@t"l
S, is true
- l(u --,)
_ -c(b - a)l
-u(c - a)]
Consider two singular matrices
l(" ") [r o.lu"u [o o']
=
" Lo rl
-t,l
' utll
= l(b-utr.- '11 -b ^= L, o.]
Sum ofA and B is given as
-(b-a)(c-a)(-b+c) However (A + B) is a non-singular matrix
= (b-a)(c-a) (c-b)
=(a-b)(b-c)(c-a) [r ol
so' 51 is true'
So(a-b)isa factor of A. Lo r]'
I Now, consider two non-singular matrices
I tr o-l
C=l- i.llandD=l
[-r o I
I
l. L0 L0 -11
e0 I
GATE Previous Years Solved Papers : ffi | MADE EASY
i0 5s-1
0.1 -0
c+D= 2
[o oi o.= ll5 is the solution
However'(C+ D) is a singular matrix. So S, is .'. There is only one value of u for which infinite
also true. solution exists.
Therefore, both S', and S, are true.
@ttr
@t"l A,B,C,Disnxntnatrix.
tl il GivenABCD = I
The given matrix is
I i ;l =+ABCDD-'C-'= D-1 C
1
@tsor. B 1 - (A 1D-1C-) 1
Nlatrix is
[r 2 BJ r9-l - (Q-t) 1. (D-1) 1. (-\-1) 1
lo
tl 2 4z s4l = CDA
lo
lr o -2 1o4l
io o o -1.1 @t"l
The given matrix is upper triangular matrix and [r 2 tsl[.]
the eigen values of the rnatrix are diagonal r'r q r l,,i- [ul
I I
xl a "
'J -' i- l
rl
elements for upper triangular matrix.
L
9 I ? l' ]L ] L
12
So the eigen values of the matrix A are 1, 2, -
1xtr+2*y+3nz =$
2, -7. 1x.x+3*y+4*z -8
2xx+2*),*3-kz - 1.)
@tur Putr=6,y=6,2 = -4, the above three
The augmented matrix fo r the given system is
equations are satisfied
lzl -41 0l
@tul
l+ B - 721 5l
Li2 -8 |
7) 310 00 000
Performing Gauss-EIimi nation on the above 131 00 000
matrix 013 10 000
0 01 31 000
lz t -4 :l A_
l+ B -12 bl I Rc 2Rr
[r 2 -B -t)
Rq-1/2R1
I
-l
;oooo 181
lo1-
l"
a 4 cx, 0 0 0 0 0 ... 0 1 3
1
l0 3t2 - 4 5-2c I A can be expanded using first row as IAn | =
Lo 6 7 - ut2) 3* lA,_r I +1* lA, .
zI
trl We find that the remaining sub-matrix is same
R"-zt2P,
lz
I
r -+lI o I
I
as the given matrix with a LOWER order.
i0 i __1 l5_2crl say lA, I is denoted as 7,,.
lo o olto-,1 Then recurrence relation is
L lz )
Tn.= 3Tn t* Tn_z
--- for infinite solution it is necessa ry that at
Now
least one row must be completely zero
= Tn- STn t- T, z= 0
This is a Homogertous system whose solution
is
MADE EASY I Discrete and Engineering Mathematics
!el
l-"n
ry_ ^f g+u6 l' *C,lo-vol tq r -,1
r,,-L,t t
'r 2 ) '\ 2 ...rir [-r nl'l I
)
Ii:j 2Rr
l0
Now putting the initial conditions Lo 0io,l
Rank [A i B] = 2 (numbe r of non zero rows in
rr-tDr
rr= trl -o ls li
=r and T"= * -
tAtBl)
i, ,l = Rank [A] = 2 (number of non zero rows in tAl)
rve get, Rank [A I B] = Rank [4 = 2 = numberofvariables
1 a.'61"-'r 3J5,71 I 3-.; ; ieJE-z .'. Unique solution exists. Correct choice is (c).
t 2 I I 2,15 I I 2 | 3rJ
l
A= |
l-1 1131
Ar=tBI =3r,a a.=l] 1l=t 0 0 ii I
11 3i l0 _2 0 l]
can put n = 1 and n = 2 in those ansrvers which ,1
Expanding A by third row (which contains lot
are in the required format i.e. equation (l) anci of zeros)
see that only choice (d) goes to 3 and 8 respectively.
lo 1 0l
@tol a= -rrl-rI
1
'l
- 11 _.)
1 0i
"X=,
Girr*. -[-o'-ra-7 f -o_] 1l
and X2- X + I = O ...(, = -1x1x l-1
11 0l
we need to find X 1.
X-1 =I-X
o.] I o
lz -i strl
[t
tt-lt
[o
1.1
t_] [-o:+o-1 r-o]
l, -z slzl
[-' -4,lr]
I i-o -1-l Using gauss-elilmination method on above
la'-a+l o _l
matrix we get,
Which is option (b).
lz -1 slrl
@r*l l, -2 slzl n"- - ln.
Rt + lR1
2',
-x+5y--1
w-rz
[-, -4,lr] -_----i-?
= 9
,-J
x+3y-3 lq -1 o 1l
The augmented matrix is l; -71 2 u2 u2l
Io -912 512 7 t2:l
[-r
t b -11 I
lz -l 1l
I -, i , R; gR: ,l0 I
d
j _712
i
Ir B iB u2 U2l
100
I
o I
Ltl
*n,+n,. io
Ir -tlz I
li;l;l lo
nl,
tlrl
I
Rank([A]) = 3
Since Rank (tA I el) = Rank ([A]) = number of
variables, the system h as unique solution.
e2 I
GATE Previous Years Solved Papers : [S I MADE EASY
@or @or
F o
I -a
ir Theorern: The ma-ximum value of xT Ax where
-l
A= il-4
i
LI
-
;)
|
i
the maximum is taken over all x that are the
unit eigen-vectors of A is the maximum eigen
The characteristic equation ofthis rnatrix is given
value cf A.
bv
Find the eigen value of ;\.
ia*;'ti = o
lz-x lr-r
i
1 .l=0
--1.i -o
|
|| -4 b-^l I
ir 2-).i
i2- 5i + 5=0
10
-)')(S-i")-4 = 0
),2-7),+6 = o
-r: - [l
i. = t 5-rdo 5 t?l
.'. The eigen values ofA are
1.6
1 and 6.
The eigen values of A
I
'z j
@tul [r t2 1.J
[r1 2 1l
l, o
i o 2 D
R. R, lo 1 1 1l
[c10-l lr
103 a-2
R, I
[1 4a 4l 3l
R,
p=lr o rl
[o r o.] -.t12 1l
Since P is a square matrix ln 1 1 1l
Sum (eigen values) = Trace (P)
L0 U a-b
I
I
0.1
=a+a*a=3a
Nowaslongasa-5*0, rank (A) = rank (A lel
Product of eigen value,s
= lPl = a(a2 - 1) - a= a3-2a -o
Only choice (a) has sum of eigen values = 3a ... a can take any real value except 5.
and product of eigen values = a3 - 2a. Ciosest correct answer is (d).
So (a) is the correct option.
MADE EASY I Discrete and Engineering Mathematics Ie3
I -0 -k,-, R . -h,-, R,
k'i r-r k,
,Lr-...-k^
k,
R..
L1 - 1.1
h
lt. o'l Eigen (A) are the roots of the characteristic
L0 0l polynomial given below:
I - . rt - u
I r -r-^l
@l(*l! (1-l)(-i-1.)-1 = 0
51 and 52: -(1-f.)(1+i")-1 = 0
Since M has zero determinant, its rank is not L2-2 = 0
full i.e. if M is of size 3 x 3, then its rank is )" = tJZ
not 3. So there is a linear combination of rows Jz
EigenvaluesofAare and' -rE 'esp""tive1y'
which evaluates to 0 i.e. hrRr+ k,rRr+...+lznRn
linear combination of columns
= 0 and there is a
So eigen values of A1e = (.[ I' and (-./2 )'o
as shown below:
Option (b):
@sol,
The value ofthe dot product ofthe eigenvectors
lr, x'l h x+l x'+71
-t
corespondingto any pair of different eigenvalues
l', rl4plr
l, ,'l
, lt
y+l "l
v'+11
z+l z'+ll
of any symmetric positive definite matrix is 0.
Option (c):
@sot.
lzl
I * x'lI
lr lo x-y x'-v'l
, "rl a=i-nln e 5l
l, , y'l-*#rlo y-z y'-"'l
Itrr'l h z z' I
Lrl
Option (d): A = [Xs,r [Y]r,e
lt , *'l
So size ofA is [3 x 3]
lz x+y x'+y'l
l, , y'l-#-12 y+ z y'* r'l lz
tt 18 io-l
lrr r'l lr z z'| A= _4|
_36 _20
lz ris 85
I
l, 2.rl 10 00 1 x.
Ak=Xh
@,,spt; =)fr*t:U= kxr= kxu
Performing gauss elimination on the augmented * x2+ x3+ xn = kxr= ltxr= kxn
matrix shownbelow: (i) k*0
say, xL= x5 =a
Ia
20 1l x2= x3 = x4 -b
l+ 07 ,l :) x7+ x5 = hxr= 2a = ka
I' 11 ,I . t-_
2
L' -27 ol -tt-
hxr= 3b=kb
= x2+ x3+ xn=
We can reduce it to k=3
Ir 11 3'lll [r 1 1
ol
dl
(ii) h= 0
lo -1 -3 -81 lo -1 -B -81 = Eigen value k = 0
Iu 015 271 l-l
l0 0 15 ,rl .'. There are 3 distinct eigen values: 0,2.3
Lo 015 2t)tl LOo 0 ol Product of non-zero eigen values: 2 x 3=6
Rank (A)r-o
Rank (A/ B)=3
MADE EASY I Discrete and Engineering Mathematics les
This is true, since if this was is not true then (4-r)(1 - ).)-10=0
all eigen values would be positive and l, ^l=
1.
determinant also therefore positive. )"2-5i-6=0
ft) If the trace of the matrix is positive, all its (1.- 6) ()" + r; = s
eigenvalues are positive. +),=6,-1
This is false. since the sum of positive and .'. The Larger eigen value is '6'.
negative eigen values could also be positive.
(c) If the determinant of the rnatrix is positive, @s"t.
all its eigenvalues are positive. Since operations 1 and 2 are elementary
This is false, since product of 2 negative operations'ofthe type ofR, + k\ and Cit kCj
numbers can be positive. respectively, the determinant will be unchanged
(d) If the product of the trace and determinant from the original determinant.
of the matrix is positive, all its eigenvalues So the required determinant
are positive.
Trace and determinant both could be negative to le
li 4 4bl
give a positive product and determinant is = lttl 9 lobl
negative then all eigen values need not be positive. lie 2 fi51
@s"t. ls 4 45t 13 4 0i
c.-15q
V={a,b,c,d,e,fg lt e losl lr e ol =o
1 Vt= {a, b, c, C} and Vr= {e, i L, !} lr, 2 :sbl lis z 0l
@s"t. @or
P(X)=fr++K+6X+5 [r -1 2)
= x(xa + 4x + 6) + 5 = X(X(x+ 4)0 + 6) + 5
mta=lo 1oi
= x(x(x(* + 4)) + 6) + 5
Only one temporary variable can be used.
lrzr)
temP = {*;g Given eigen value .1. = 1.
temp=temp+4; (A-i,DX=o
Lex Xbe the vector. Then
temP =f,*1"-rt
temP ={*1u*r, [t-t -1 2
l
temp=temp+$; 0 1-)" 0 lX =0
temP ={*6*r, 1 2 L-X J I
ternp=temp+5
.'. 7 arithmetic operations needed. put),=1
@or [o -10 'l['l [-x. + 2x"l
Trace = Sum of eigen values
l0 2 ol0llr"!= o=lo l=o
1*a=6 L1 L,;
j l*r+z*, l
= a=5 putting xr=k
Determinant = Product of eigen values
(a-4b)=-7 we get xz = -kl2 and x. = -k14.
5-4b=-7
%l GATE PreviousYears Solved Papers: !f,1 I MADE EASY
Iil lp
JI s
11
So the eigen vector = nl trzl LetA=le r pl. Thesystemis Af;=O
[-r,n] tt p q)
Lr
_1 This is a homogenous system. Such a system
The ratios are xrlxr- -.1= = -2 has non-trivial solution iff lA l=9.
-112
, lporl
and xrlx" -
-rl2
---=-=-2 t'l . pl
-q+ So,
la psl =o
lr
Only option (b) (-4, 2, i) has the same ratios
and therefore is a correct eigen vector. p(qr - p2) - q(q2 - pr) + r(pS - 12) =0
or p3+q3+r3-3pqr=0
Alternate Method: p=q= r satisfies the above equation.
AX= )"X Also ifp
+ q + r = 0 then a can be transformed
Check one-hy-one each eigen vector until the into one of the row as completely 0's as shown
equation is satisfied. For example, below.
tu;, lo ,
l
]
loool
[r
tilttl-1 zll-+1 l-t)
=lq , pl -0
Choice (b):
lo ,2 o1.lLll 21.1
l= , l(true) 7><1 l'p sl
L1 L 1l Therefore t,he correct option is (c) which is p
*q*r=0 orp=q=r.
and so on...
only choice (b) satisfies and so it is the correct @$:ol.
answer. Two eigen values are 2 + i and 3 of a 3 x 3
matrix. The third eigen value must be 2 - i
@.,suf; Nowlll., = lal
L,, o I [r u,,f = ldl= Q+ i) (2-i) x 3= (4-i2) x B
-l
I
t t-t
lz 21
lL,, L,r)Lo 1l-L+ gl =5x3=15
l
i., If at every point of a certain curve, the siope of (a) rl2 o) nJro
(c) Jntz (d) fi
the tangent equals -2* ,h"curve is IIT-2006: 2 Marksl
v
(a) Astraightline (b) Aparabola 7.1 If (r) is defrned as follows, what is the minimum
(c) A circle (d) An ellipse value of /(r) for x e (0,21?
. (n
I: There exrsts 0el-. -ln\ such that /'(0)
7.tz what is the value
"t lT[,
-*)'", \6 3)
-0.
e' . (n
(a) o @) II: There exists 0el:. :ln) such that /'(0)
(d e-ttz (d) 1 \6 3)
+0.
[2010: l Mark]
(a) I only @) Ilonly
7,13 Given i = J-, what will be the evaluation of (c) Both I and II (d) Neither I nor II
the definite integral [20la (Set-l): l Mark]
frt2COsX+lsinr 7,17 The function f(x) = r sin r satisfies the following
Irr dx?
J
cos.r - -
, sln r equation: f'(x) + f(x) + t cos.r = 0. The value of ,
(a) o &)2 is
(c) -i (d) i [2014 (Set-l) :2 Marks]
[2011:2 Marks] 7.18 A function /(r) is continuous in the interval [0,
7.14 Consider the functibn f(x) = sin (x) in the interval
-.
21, It is known that /(0) - f(2) - -1 and /(r) = l.
xe fnl4,7nla].The number and location(s) of the Which one of the following statements must be
local minima of this function are true?
(a) One,atnl2 (a) There exists a y in the interval (0, 1) such
&) One, at\nl2 that /(y) = fO'+ 1)
(c) Two, atnl2and\nl2 @) For every] in the interval (0, 1), f0) = f(2 - y)
(d) Two, atnl4and}xl2 (c) The maximum value of the function in the
l Markl interval (0, 2) is 1
l20L2z
(d) There exists a y in the interval (0, 1) such
7 .15 Which one of the following functions is continuous that f(y) = -f(2 - y)
atx=3? [2014(Set-l):2Marks]
l-'
(o
if x=3 7.19 A non-zero polynomial/(r) of degree 3 has roots
(a) f(x) = J"-1' if x>3 at x = l,,x = 2 and x = 3. Which one of the
lx+s following must be TRUE?
lo , if x<3
I
if x=3
(c) /(0) + f(4)> 0 (d) /(0) +/(4) < 0
(b) f(x) = l+. [201a (Set-2): l Mark]
1s-* if x*3
(c) f(x) = Jx+3, if
.o-
x<3 7.20 If Jn lxsinxldr = kn, then the value of k is equal
l*-+ if x>3
(d) f(x)=+,ifx*3
x"
[2014 (Set-3): l Mark]
-27'
[2013:1Mark] 7,21 The value of the integral given below is
7.zB '!.*$90* =
7.26 If fornon-ze rcx, af (x)- r[i) = l-ru where
[2015(Set-l):2Marks] o+bthen i,roo* *
7 .24 I'ef f(x) - r.ots) and A denote the area of the region
bounded bv f@) and the X-axis, when r varies (a) --L-[rn. 2-2st*!!1
from -1 to 1. Which of the following statements
o'-b"L 2)
is/are True? 1 [a0ln2-25)- 47b1
-'-
1. f is continuous in [-1, 1]
&) a'-b'l ' 2)
|
EE@catcurus
7.1 (d) 7.2 (d) 7.3 (b) 7.4 (b) 7.5 (b) 7.6 (c) 7.t (b) 7.8 (a) 7.9 (a)
7.10 (b) 7.tL (d) 7.12 (b) 7.13 (d) 7.L4 (b) 7.15 (a) 1.tG (c) 7.18 (a) 1.ts (a)
7.2t (a) 7.22 (c) 7.24 (c) 7.25 (c) 7.26 (a)
Calculus ,
. dy
-:- = --
2*t So the curve is an ellipse with a=1 and b = Ji
1.9..
dxv
vdY = -z*a"
EI,I$,,,,
Integrating both side The formula used to compute an approximation
offirst derivative ofa function fat a point xo is
y'^x'
L - f (xn +h)-f (xo)
22 -r)Y-L^
f'1xo;= -t--f-
Y2 e, So an approximation for the second derivative of
2 a function f at a point xo is
100 i GATE Previous Years Solved Papers : lfl I MADE EASY
f "(x) =
f'(xo)-f'(xo -h) Ertul
h
(ri*o +h)-r(x0)) (r(".)-r(xo -h)) In the integral 'f O - n' cosx d.x
1., ro.t2
So. x= -: -= I e 2dx =0.5
2 .l2n r*
is a point of local minimum. So there is no point
So, the required integral
of local maximum.
o12
Ltrow tabulate the values of f at end point of
interval and at local maximum if any (in this liza*=o.5xJ2n
case no point of locai maximum). ' = JTEI2
which is option (c).
@*>
For the function 25l8x the minimum value will
Clearly the absolute maximd is at r = 2 and come when x is maximum since it is a decreasing
absolute maximum value is 10. function.
The maximum value of x is 3/2.
@tut At x =312 the function has the value
The function y = lxl in the interval [-1, 1] is f(x) = 251(8*3lz)
=2.0833=2+(tll2)
So, - > f(x) > 2(7112) for x S 312
x + 1,lx> 2
But since for this function x> 312, putting 3/
-1 y, 1
2 in this function we get the minimum of this
lx I is continuous and differentiable everywhere function which is
except at x = 0, where it is continuous but not 312+ll(312) = 13/6 = 2.L66
differentiable. Now comparing the minimum value 2.0833 of
Since [-1, 1] contains 0, in this interval it is the first function with minimum value 2.166 of
continuous but not differentiable. the second function, we get the overall minimum
of this function to be 2.0833 = 2(1172) which is
option (b).
MADE EASY I Discrete and Engineering Mathematics i 101
@.,{a) rnl4l-tanx -
[= Jo
| 1 + tanx
I x I is continuous and differentiable every where
except at x = 0, where it is continuous but not /* \
1-tanl a-"ld*
-dx
differentiable.
= I:'^ \4 )
(n
l+tanl --xl \
Since 0 is a real number, for ali real values it is
continuous but not differentiable. \4 t
@tal tanA-tanB
Since tan (A- n; =
1+tanAtanB
-. x-sinx -.
Ilm --
1-sinx/x
x+-x+cosx = ltm
"+-1*cosx/x tanl - tanx
lim (r - sinx/x)
_1 4
x+-' tanltanx
- x+-'
tr*]1+.ilt I= J;'
1+
dx
sin x
1- iim
x
cos x
1+ lim
X+€ x
- 1-o
1
= _ ln'1
1+0 - Jo
1
@,or
Y = 3xa- 16x3 +24x2 + 37 rnl4 (r+tanx)-(r-tanx)
= dx
dv
Jo (r+tanx)+(t-tanx)
-*
dx
= lZxr-48x2 +48x=0 rxts 2tanx -
-l Jo2
x(12x2-48x+48)=6
x=0 tn)
= Jn -dx
1
tanx dx
or L2x2-48x+48=0
x2-4x+4=o = [tog(sec *)I'-
(x-2)z =g
d2v = l.[.".1]-/n(sec
\, 4) \ o)
n? = 36xz-96x+48
Nowat x = 0 = r"(Jr)-rn(r)
_ lnbr,2\_o =Ltn2
d2v
---:- = 4R>O \/2
dx"
... f(x) has a minimum at x = 0 @r'ei
I-qU =oandt&l =48*o ri,, l)'"
n-*\Ii - n) = Lim [f , ll"-l'
n-*[\ - n/ J
Ldo'l.=, Ld*'l*=,
So x = 2 is a saddle point (point of inflection)
= ILiml
t- /1-:l1\"12
L"--\
I
@ral @&)
According to Demoivre's theorem
cosx+isinx=ei' sinO cosO tano
sin(n/6) cos(n/6) tan(n / 6)l
I
nl2
=g
f(n'16)
=l eri" d*
0
Since if we put 0 = nl6 in above determinant it
will evaluate to zero, since I and II row will
become same.
7
t_t 1"12 rl"in_"ol
_ 1- f(dS) = 3
"zi" I
=t
L 2,
I
.lo
ziL Since if we put 0 = nl3 in above determinant it
will evaluate to zero. since I and III row will
=,1t-, -1](since etn = co.r + isinn = -n) become sarne.
So f(n/6) = f(n/3). Also in the interval [nl6,nl3]the
-2
= 2ii
-1 function f(0).is continuous and differentiable
-- (note that the given interval doesn't contain any
odd multiple of nl2 where tan 0 is neither
@rur continuous nor differentiable).
Since all the three conditions of Roll's theorern
are satisfied the conclusion ofRolls theorem is
true i.e.
lx+3
t_
t-
L'l
,if x<3 @s"t.
/(r) = r sinr
lim/(r) hm_
-.,o
f (x1 = rr cos.r * sinr
=
r+3- x-3 O f"(x) = (-r sinx + cosr) * cosr
o,q
t)Td
f"(x)+/(r)+tcosr=0
=
tl =+ -r sin-r * cosr + cos,r + r sin-r * I cosr = 0
(2+ l) cosr= 0
lim/(r) lim x -1 =
= t+l=Q
r+3n =
o-l:.4 L--Z
-
A1so, I
= [sinl]', = (0 - 1) = -t
2n @t"t
= J lmir,rla, =an 1
0 f(x) = ;r
Vr
n2ft
Statement 1: f is continuous in [-1, 1]. Let us
= Jl-rsin*ldr+ J lrsinxld, =
0n
ian
check this statement.
n2n We need to check continuity at x = 0
= Jxsinr d, + J -(rsinr)dr =
0,I
lem
Let limit
-.
hm-1
= r--u
d.I
(-xcosx + sin;r)li - (-xcosx + sin x)12' = lzn _1
-. r
4n=hn = Irrn: =4
h..o llh
1- _ ,
It-+
Right lirnit = I1III-
,.
hrfi----: 1 -. 1
*.o'l/x - h-o V0+h
@,:te\
Integrating by parts once we get, ,. 1
= llfl1--
h'o ={o
fr <lh
f, r''
J."'cos, or = [x'(sinx)lJ - zi xsinx dx ht limit
0 0
s false.
104 I GATE Previous Years Solved Papers : ffi | MADE EASY
Statement 2: f is not bounded is [-1, 1]. Since Equation (1) x a - equation (2) x U
x
.r lol
- 9*i9'
= -"
z'li-" ' rr I
= lixr = l--b'Lx
.fl!-A*+25tb_ a)l
So A is non zero and finite. -l
- I /tr l.dx
@(")
[ :- 2 2 I
Let ,' = liT(1+r')'' = o--o-l"rx
"l - o.Il.a* -blx.dx+2itb-o,Ir.a*l
i i l
log ;r = limlog(1 * *')"-'
- t1'-b'-
--Li rrnz - ]a
2
+ z5rb - or-l
,.
=lrmi
l iog"lli + "r') l r
.--i rt l
f' = --l-[, rn2-2ia*!!1,
-/* form app15; 11ospital's lule e't-b-l 2)
r
-,. (2x)
I -.tr'
'.ilm -:---L--::*- = -^L [oon2- ,ur*!!1
=) lOg -y = e'-b"- l 2)
=? t'=
log .' tim 21 @s"t.
;'-'; ii + r:)e'
Again we are getting
,. sin(x - 4)
-/- form apply f'
r-l r-{
Hospital's rrrle
Letr-4=lnotasr-+4
los rim -;j
r.= r--- -
fl *.r')e' + e^ .2x
So the requires limit is ii*!1-(il = 1
1J0
_2 t
log.v= - -0 = .'r'=1
@s"t.
@l r"l If /(;r') + /(-:r) is degree 10
-/ | \
/- f(r) = arcxta + anxs ....... + anx + ao
ctl(.r)+bll-'
\ .r,l -:-25
1
..(i)
x f(-x) = oro*ta - asx9. . .- o7x + ao
Soiving equations (1) and (2) simultaneor,rsly we Clearly degree of (g(r) - g(-r)) is 9.
get flr) as follows: I!II
E "il * 1;
LiKg3il E HH
Theory of Computation
Contents
3. TuringMachine:RE,RECandUndecidability .........................149
fteory of'CompUtation
1994 1 4 2A10 1 3 7
1 'i4
1995 1 2 2011 3 3 9
5
1996 3 2 2012 4
7 1 6
1997 3
1998
1
7 2A13 2 3 I
5 3 11 2014 Set-1 2 2 6
1999 3 1
5 2014 Set-2 2 2 6
2000 Z 1
4
20a1 2014 Set-3 2 2 6
3 2 7
2002 I o
2015 Set-1 1 2 5
1 18
2003 3 6 2015 Set-2 1 3 v
{5
2AA4 1 4 I 2015 Set-3 1 1 3
2005 7
2006
14 2016 Set-1 3 2 I
2 5 12 2016 Set-2 3 4 11
!
!
I
1.1 How many substrings (of a1l lengths inclusive) L.7 The regular expression for the language
can be formed from a character string of iength recognized by the finite state automation
n? Assume all characters to be distinct. Frove
your answer.
[1989 : 2 Marks]
L.2 Let R, and R, be regular sets defined over the
alphabet then
(a) Rr n R, is not regular [1994:2 Marks]
&) Rr u R, is not regular
(c) I* - R, is regular Which of the following definitions below generates
(d) Rr* is not regular the same language as L
(a) N2
&) 2N o
(c) 2N (d) N!
' 12001: l Markl
Let S denote the set ofseven bit bnrary strings
in which the first, the fourth, and the la,qt
l.ZE Consider a DFA over Z = bits
{a,b} accepting all strings are 1. The number of strings in S that are
which have nurnber of a's divisibte b,ir 6
and accepted by N{ is
number of b,s divisible by g. What is the
minimum numtrer of states that the DFA will
1
(a) (b) a
(d7 (0a
have?
(a) 8 .' (b) 14 [2008:2 Marks]
(c) 15 (0 aa 1.30 Consider the NFA M shr:rwn beiow.
[2001 :2 Marks]
1.26 Consider the foilowing lang-.iages:
L, = {ww iw e {a.b} *}
L, = {wwR I w e {a, b}*, wRis ihe reverse of w}
L, = {02i1 i i. ,r, integer}
Lo = {0i2li i" un integer} 9*
Which of the languages are reguiar?
Let the language accepted by M be L. Let
(4 L, and L, &) Only L*Loand L,
L, L,e
!n15, the language accepted by the NFAM1,
(c) Only L, and Ln (d) On\, L, obtained
by changing the accepting state ofli
to a non_
[2001 :2 Marks] accepting state and by changing the non_
1.27 The finite state machine described
by the accepting state of M to accepting states.
Which
foilowing state diagram with A as starting
state, of the following statements is true?
where an arc label is x/y and x stands for
1-bit (a) Lr={0, U*-L
input and y stands for 2-bit output ft) L, ={0, Un
(c) L. cL (d) L, = 1,
[2008:2 Marks]
1.31 Which one of the following regular expressions
is NOT equivalent to the reguiar expression
(a *
b + c)*?
(a) (a* + b* + c*)* &) (a*b*go.1*
(a) Outputs the sum of the present (c) ((ab)* + c*)* (d) (a*b* +
and the
previous bits ofthe input "*;*
UT-2004: l IVIarkl
@) Outputs 01 whenever the input sequence
L.32 Let M = (K, X, 6, s, tr) be a finite state automaton.
contains 11
(c) Output 00 whenever the input where
sequence
contains 10 K = {A, B}, X,= {a, b}. s =A, F
= {B},
(d) None of the above 6(.{, a) = A, 6(A, b) = B, 6(8, a) B and
= 6(8, b; = 4
[2002:2 Marks]
r10 I GATE Previous Years Solved Papers : !S I MADE EASY
A grammar to generate the language accepted State X is the starting state of the automaton.
b5, M can be specified as G = (V, :, R, S), Where Let the language accepted by the NFA with Y as
Y=KuX,andS=A the only accepting state be L1. Similarly, Iet the
tr4rich one of the following set of rules will make language accepted by the NFA with Z as the only
L(G) = L(M)? accepting state be L2. Which of the following
(a) {A-+aB. A+bA, B-+bA, B-+aA, B-+e) statements about L1 andL2 is TRUE?
ft) {A-+a-A, A-+bB, B-+aB, B-+bA, B+e) (a) Ll = L2 (b) L1 c L2
(c) {A-+bB, A->aB, B-+aA, B-+bA, B-+t) (c) L2 c L1 (d) None of these
(d) lA-+aA, A+bA, B-+aB. B-+bA, A-+e) [IT-2005 : 2 Marks]
IIT-2004 : 2 Marksl
Consider the regular grammar:
1.33 The follorving finite state machine accepts all S+XalYa
those binary strings in which the number of 1's X-+Za
and 0's are respectively Z --s Sale
1 Y+Wa
W-->Sa
where S is the starting symbol, the set of
terminais is {a} and the set of non-terminals is
{S, W, X, Y, Z}. We wish to construct a
deterministic finite automaton (DFA) to recognize
(a) divisible by 3 & 2 (tr) odd and even the same language. What is the minimum
(c) even and odd (d) divisible by 2 & 3 number of states required for the DFA?
12004:2 Marksl (a) 2 (b) 3
(c) 4 (d) 5
1.34 Which of the foilowing statements is TRUE about
the regular expression 01*0? UT-2005 : 2 Marksl
(a) It represents a finite set of finite strings. 1.38 A language L satisfies the Pumping Lemma for
(o) It represents an infinite set of finite strings. regular languages, and also the Pumping
(c) It represents a finite set ofinfinite strings. Lemma for context-free languages. Which of the
(d) It represents an infrnite set of inlinite strings. following statements about L is TRUE?
IIT-2005 : l Markl (a) L is necessarily a regular language.
1.35 The language {0" 1" 2" I 1 < n < 106} is @) L is necessarily a context-free language, but
(a) Regular not necessarily a regular language.
&) Context-free but not regular. (c) L is necessarily a non-regular language.
(c) Context-free but its complement is not (d) None of the above
context-free. [IT-2005 : 2 Marks]
(d) Not context-free. 1.39 Consider the machine M
IIT-2005 : 1 Markl
1.36 Consider the non-deterministic finite automaton
(NFA) shown in the figure.
0
jg i
(a) {w e
two b's)
{a, b}* | every a in w is followed by exactly
(d) {w e {a, b}* w does not contain 'aa' as a 1.43 Consider the regular grammar below
substring) S-+bSlaAIe
. t2005:2 Marksl A-+ aS lbA
The Myhill-Nerode equivalence classes for the
1.40 The foilowing diagrain represents a finite state
Ianguage generated by the grammar are
machine which takes as input a binary number
(a) {* e (a + b)* | #,(w) is even} and {we (a+b)*
from the least significant bit
|
#^(w) is odd)
0/0
(b) {we (a + b)* l#o(w) is even} and {w e (a + b)* |
#o(w) is odd)
(c) {w e (a+b)* l#,(w) =#o(w)} and{we (a+b)*
Qo Qr
|
Po
zta
---
^/i=\
b
Pr
L
):-
--\
\
,
b
n.
(b) + so <
\
\ \a
\^/ .{
\b
I
Dr
-'\
\acj
-.,'
SO
a,b
1
P
a,b
s,'
,\ x_^
\rE\
(c) so) b la ((ss
b\ \_,
e
r'/b
The automation rn'hich recognizes the language
^L
L(P) n L(Q) is:
(d) so
A)
b
x
f s,)
S"
\ \-w
,b2
.a
a.ir
IIT-2007 : 2 Marksl
1.59 Which deterministic finite automaton accepts
the language represented by the regular
expression R?
k) a b (d)
a b
+P a S -+P S a
a R S
a S R List-II
R(F) a P R(F) a P 1. e+0(01*1+00)*01*
S a P S a P
2. e+0(10*1+00)*0
3' e+o(10'*1+10)*i
[2008:2Marks] 4. e+0(10*1+10)*10*
L.67 Match List-I with List-II and select the correct Codes:
answer using the codes given below the lists: ABCD
List-I (a)2784
(b)1324
1 (c)t294
(d)3214
[2008:2 Marks]
A. 1.68 Which of the following are regular sets?
1. {anfo2m i n>O.m>0}
2. {a"b- ln=2m}
3. {a"bT In+m}
4. {xcy I x, y e {a, b}*}
(a) 1 and 4 only (b) 1 and 3 only
(c) 1 only. (d) 4 only
[2008:2 Marks]
1.69 Which one of the following languages over the
alphabet {0, l} is described by the regular
B. expression: (0 + 1)*0(0 + 1)*0(0 + 1)*?
(a) The set ofall strings containing the substring
00
&) The set of all strings containing at most two
0's
(c) The set of all strings containing at least two
0's
(d) The set of all strings that begin and end with
either 0 or 1
[2009: t Mark]
C. 1.70 The following DFA accepts the set of all strings
over {0, 1} that
0 0
GATE Previous Years Solved Papers : !f,t I MADE EASY
116 I
(c) 00 01 10 11 q
00 1 0
What is the set of reachable states for the input
01 1
string 0011?
10 0 (a) {qo, e1, e2} &) {qo, qr}
11 0
G) {Qs, Q1, Q2, Qs} (d) {qJ
q [2014 (Set-l): L Mark]
(d) 00 01 10 11
l20l2z 2 Marksl
118 I GATE PreviousYears Solved Papers: lft I MADE EASY
1.95 Which one of the following regular expressions l.g7 Consider the following two statements:
' represents the language'. the set of all binarlt L If all states of an NFA are accepting states
strings hauirug two consecutiue 0s ancl two then the langauge accepted by the NFA is
con'secutiue ls?
r*.
(a) (0+1)*001 1(0+1)* + (0+1)*1100(0+1)* II. There exists a regular language A such that
(0+1)*(00(0+1)*11 + 11(0+1)*00)(0+1)* for a1I languages B, AaB is regular'
&)
(c) (0+1)*00(0+1)* + (0+1)*11(0+1)* Which one of bhe following is CORRECT?
(d) 00(0+1)*11+11(0+1)*00 (a) OnIy I is true
(Set-l):1Mark] (b) Only II is ture
[2016
(c) Both I aud II are true
1.96 The number of states in the minimum sized DFA (d) Both I and II are false
that accepts the la4guage defined by the regular [2016 (Set-2):2 Marks]
expression (0+1)* (0+1) (0+1)* is
l Mark] IIII
[2016 (Set-2):
-'
Finite Automata : Regular Languages
f[!![! t.Lz (b)
7.2 (c) 1.3 (a, c) 1.4 (b) 1.6 (d) 1.8 (a) 1.e 1.10 (c)
(b) 1.11 (d)
1.13 (d) L.14 (d) 1.15 (a) 1.16 (c,d) 1.17 (d) 1.18 (b) 1.1e (b) Lza (c) t.zr (b)
t.25 (d) t.26 t.27 (a) 1.28 (b) L.29 (c) 1.30 (b)
1.22 (d) t.23 (a) 1.24 (b) (d)
1.34 (b) 1.36 (a) L.37 (b) 1.38 (d) 1.3e (b)
1.31 (c) L.32 (b) 1.33 (a) 1.35 (a)
1.40 (b) L.4t (d) L.42 (a) 1.43 (a) 7.44 (c) r.45 (b) 7.46 (a) r.47 (c) 1.48 (d)
1.50 (a) 1.51 (c) 1.52 (c) 1.53 (b) 1.54 (a) 1.55 (d) 1.56 (c) r.57 (b)
1.4e (b)
1.61 (c) 1.63 (a) i.s+ (d) 1.65 (a) 1.66 (a)
1.58 (b) 1.5e (a) 1.60 (c) 1.62 (a)
1.70 (c) t.1t 7.72 (c) 1.73 (a) 1.74 (c) L.75 (b)
1.67 (c) 1.68 (a) 1.69 (c) (b)
L.1e (d) 1.81 (d) t.82 (c) 1.83 (a) 1.84 (h)
1.76 (a) 1.77 (b) 1.78 (c) 1.80 (a)
1.86 (a) 1.89 (c) 1.90 (a) t.92 (b) 1.e3 (d) t.s4 (c) 1.e5 (b) r.s1 (b)
1.85 (a)
C) o', B_5C
@ B--r-rB--5C
just remove this From C to reach C
Since C is dead state so
C o)D o)C
c 1>B o>c
From D to reach C
@tbr
(a) The set of all strings over L is I* which is
countably infinite.
&) Set ofall ianguages over X is 2t. . According
to Cantor's theorem if S be an countably So the numbers l, 2, 4, 8,.... 2n... written in
infinite set, then its power set 2s is binary can be recognized by a deterministic finite
uncountable.
state automaton.
So 2>* is uncountable because X* is
countably infinite. @,&;d)
(c) Set of all regular languages over X is (c) The string 1101 doesn,t belong to set
countably infinite. represented bv (10)* (01)* (00 + 1 1)* because
(d) Set of all languages over X accepted by once 11 appears in string then 1 and 0 only
turing machine is the set of all RE appears in pairs.
languages which is countably infinite. (d) (00 + (11)* 0)* can generate only strings with
even number of 1's and hence cannot generate
@ (a) r.e. (regular expression) = 0*(1 + 0)* can
1 101.
t/),x.\
e) 0l which is regular language.
Regular expression for S, is 00(00)*
\ /l
L L, = {0m1n 0m+n I m 2 1 andn2 1} is context free
language not regular. (m occurs in two places,
sothere is comparison of count).
@rt So, S, is correct but S, is not correct.
The minimum state finite automation that
recognizes the language represented by regular @or
expression (0 + 1) (0 + 1) ... n times is n + 1' For an arbitrary NFA with N states, the
This language contains sirings with exactly maximum ,rr*L"t of states in an equivalent
length n. minimized DFAis 2N.
@t*t @tar
According to rules ofregutrar expressions L, = {wrn'lwe {a, b}*}
(rr+r2)*=(r,*rr*)* is context sensitive language (CSL) (since there
Therefore (a + b*)* = (2 + b)* is infinite string matching in straight order).
So S=T L, = iwwR I we (a, b)*, wR
is ihe reverse of w)
@tur is context free language (since there is infinite
The language generated by the grammar
string matching in reverse order).
S-;0S0l00is L, = {02i I i is an integer} = (00)*
L={02, 04, 06, 08, ...}
is regular language which contains all strings
= {g2n+z I n.> 0} iraving even number of 0's.
=+ =102"1n,>-Lr=00(00)* Ln = {0i2 | i is an integer}
So above language is regular but not 0+.
is context sensitive language (CSL) (since the
power is infinite and non linear).
@cr
L = {a" in is odd}
MADE EASY I Theory of Computation
tr 123
@s;tat
The state diagram represents the FSM which
outputs the sum ofthe present and previous bits
' ofthe input.
State A represents previous bit is a 0 and B and
C represents previous bit is a 1.
1,0
final state.
.'. Correct answer is (c).
@t"l
The given finite state machine accepts any string
w e (0, 1)* in which the number of 1s is multiple
@or of 3 and the number of 0s is multiple of 2.
The given machine M is
@or
Given regular expression is infinite set (because
of *) of
finite strings. Aregular expressioncannot
generate any infinite string (since string is
always finite in length by definition).