Himachal Pradesh University (HPU) 2012 M.A Mathematics Hichal Pardesh University, M.Sc thetics, Advanced Discrete thetics - Question Paper
M.A./M.Sc. exam
Mathematics
(Advanced Discrete Mathematics)
Paper : M-403
Time : three hours, Maximum Marks:- 80
The candidate shall limit their answers precisely within the answer- book (40 Pages) issued to them and no supplementary/ continuation sheet will be issued.
Note : Attempt five ques. in all, selecting at lowest 1 but not more than two ques. from any part.
Section-1
Please go to the attachment.
Thank you
Total Pages : 5
|
Total No. of Questions 9] (1062) 4539 M.AJM.Sc. Examination MATHEMATICS (Advanced Discrete Mathematics) Paper: Time : Three Hours! (Maximum Marks : 80 The candidates shall limit iheir answers precisely within the answ er-book (40 pages) issued to them and no supplementary, continuation sheet will be issued. Note : Attempt five questions in all. selecting at least one but not more than two questions from any Section. SECTION-1 1. (a) There are two fruit shops dose to each other. One has a sign that says Good fruit is not cheap while the other has a sign that says Cheap fruit is not good. Going only by the sign boards, which shop should one prefer? 5 (b) Translate into symbolic language and test the validity of the argument: If 6 is even, then 2 does not divide 7. Either 5 is not a prime or 2 divides 7. But 5 is prime. Therefore 6 is odd. 5 |
(c) Write a compound statement that is true when none, one or two of the three statements p.q.rtre true. Justify your answer. 6 2. (a) If seven integers are selected from the first ten positive integers, show that there must be at least two pairs of these integers with sum II. 5 (b) Sania Mirza prepares for the French Open Championship by pitying some practke games over a period of 70 days. She plays at least one game a day but not more than 123 games altogether. Prove that there is a period of consecutive days during which she plays exactly 16 game*. - 6 (c) Prove that the number of r digit binary sequences with odd number of l's is 2f~l. S 3. (a) If (A. v. a) is an algebraic system defined by a lattice (A. ). prove that both ti join and meet operations are associative. 6 (b) If (L, 5) is a distributive lattice and a,b.c L such that a vb*avc, a b = a a c. prove that b c. 5 (c) Write the Boolean expression [(x + yf * i/z)X in disjunctive normal form. 5 |
453SV3.00<y777/233 2
IP.T.O.
45393.000/777/233
|
4. (a) Determine the number of integers between I and 300' that are divisible by any of the numbers 2. 3. S and 7. 5 (b) In a class of 100 students, the number of Moderns who got. in A. in the ficu. equals the number of students who got an A in the second examination. The total number of students, who got an A in exactly one examination is SO and S students did not get an A in either examination. Determine (he number of students who got an A (i) in the Tint examination only, (ii) in both the examinations. 6 (c) A pcAygon has 54 diagoruts. Find the number of its sides. S Solve the recurrence relation ar * + a_2 for / > I with aM a1 = |. S {? (b) Pind the generating function of the recurrence relation o,~ 5a,+ 6oj ' 2'+ r. ri 2, with the boundary conditions a0 = o, * 1. Hence solve it 7 (c) Solve the recurrence relation a,2 - 3a* * 1. given that as3. 4 6. (a) For the relation R * {(1. 2). (2. 3). (3.4)| on the set A a {I, 2, 3. 4). find the reflexive and symmetric closures. S (b) On the set Z of all integers define a relation R by saying that 9 R b if 5 divides a - b. a, b e Z. Prove that R is an equivalence relation. Al*> find all the equivalence classes. 6 |
(c) For a, b A = (I. 2. 3.4, 6, 8. 10} say that a R b if <2 divides b. Prove that R is a partial order relation. Also draw its Hasse diagram. 5 SKCTION-m 7. (a) In a graph with n vertices. if there is a path from a vertex v, to a vertex Vj. prove that there is a path of no more than n - I edges from v4 to vY 5 do) If an undirected gn>ph possesses an Eulerian circuit, prove (hat it is connected and each of its vertices has even degree. 6 <c) n cities are contacted by a network of A highways, where a highway is a road betw een two cities that docs not pass through any other city. If k > - IX" - 2) prose that one can travel between any two cities through connecting highways. 5 S. (*)/If G is a linear graph with n vertices, n Z 3, such that y>/ degfu) + dcg(v) 2 n for every pair of non-adjacent vertices u and v in G, prove that G has a Hamiltonian circuit. 6 (b) If G is a linear planar connected graph with m vertices and it k 3 edges, prove that n 3m - 6. 6 (c) Rod the chromatic number of (i) Complete graph of/i veniccs: (ii) (he bipartite complete graph Ka 4 453yj,00(V777/233 4 |
(a) If G is a tree with n vertices and e edges, prove that en-l. (b) A tree has 2f vertices of degree 1.3n vertices of degree 2 and/t vertices of degree 3. Find the number of vertices and edges in the tree. (c) IfG is a connected graph and the removal of any edge leaves a disconnected subgraph consisting of two components, each of which is a tree, prove th* G itself 6 is a tree. 453Jkl3100G0r77/233 |
453Stf3,000777/233 3
[P.T.O.
|
Attachment: |
| Earning: Approval pending. |
