Bihar engineering university computer science question paper solution. BEU pyq solution. Discrete mathematics 2022 question paper solution.
3. (a) Prove the following:
(i) There is a real number x such that x>1 and 2*> x10.
(ii) There is an integer n such that 2n2-5n+2 is prime.
(b) Disprove that for all real numbers a and b, if a < b, then a² < 2.
4. (a) Show that pv (q^r) and (pq)^ (pvr) are logically equivalent. This is the distributive law of disjunction over conjunction.
5. (a) Use mathematical induction to prove this formula for the sum of a finite number of terms of a geometric progression with initial term a and common ratio r
(b) Write short notes on the following:
(i) Forward proof
(ii) Disjunctive and conjunctive normal form
(iii) Fundamental theorem of arithmetic
6. (a) An odd number of people stand in a yard at mutually distinct distances. At the same time each person throws a pie at their nearest neighbour, hitting this person. Use mathematical induction to show that there is at least one survivor, that is, at least one person who is not hit by a pie.
(b) Prove Bernoulli’s inequality that if h>-1, then 1+nh ≤ (1+h)” for all non- negative integers n.
7. What is pigeonhole principle? Using it, prove the following:
(a) During a month with 30 days, a baseball team plays at least one game a day, but no more than 45 games. Show that there must be a period of some number of consecutive days during which the team must play exactly 14 games.
(b) The sequence 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 contains 10 terms. Note that 1032+1. There are four strictly increasing subsequences of length four, namely, 1, 4, 6, 12; 1, 4, 6, 7; 1, 4, 6, 10; and 1, 4, 5, 7. There is also a strictly decreasing subsequence of length four, namely, 11, 9, 6, 5.
8. (a) In a Round-Robin tournament, the Tigers beat the Blue Jays, the Tigers beat the Cardinals, the Tigers beat the Orioles, the Blue Jays beat the Cardinals, the Blue Jays beat the Orioles and the Cardinals beat the Orioles. Model this outcome with a directed graph.
b) Let G = (V, E) be a simple graph. Let R ( be the relation on V consisting of pairs of vertices (u, v) such that there is a path from u to vor such that u = v. Show that R is an equivalence relation.
(c) Determine whether the following given pair of directed graphs, shown in Fig. 1 and Fig. 2, are isomorphic or not. Exhibit an isomorphism or provide a rigorous argument that none exists.
9 (a) Use pseudocode to describe an algo- rithm for determining the value of a game tree when both players follow a minmax strategy.
(b) Suppose that T₁ and T₂ are spanning trees of a simple graph G. Moreover, suppose that e₁ is an edge in T₁ that is not in T2. Show that there is an edge ez in T₂ that is not in T₁ such that T₁ remains a spanning tree if e₁ is removed from it and e₂ is added to it, and T₂ remains a spanning tree if ez is removed from it and e₁ is added to it.
(c) Show that a degree-constrained spanning tree of a simple graph in which each vertex has degree not exceeding 2 consists of a single Hamiltonian path in the graph.
Discrete mathematics solution 2022 available soon