Department of Information Science and Electronic Engineering
Zhejiang University
Final Examination
11193011Discrete Mathematics
Assoc.Prof.Dr.Thomas Honold
M.Sc.Jingmei Ai
Fall Semester,2014
Name:
Matric.No.:
Question123456
Marks Obtained
Maximal Marks151515201520100
Time allowed:120minutes
Instructions to candidates:
•This examination paper contains six(6)questions.
•Please answer every question and subquestion,and justify your answers.
•For your answers please use the space provided after each question.If this space is insufficient,please continue on the blank sheets provided.
•This is a CLOSED BOOK examination,
except that you may bring1sheet of A4paper(hand-written only)and a Chinese-English dictionary(paper copy only)to the examination.
Question1(15marks)
a)Is(p1↔p2)∨p1a tautology?
b)Are(p1→p2)→p3and p1→(p2→p3)logically equivalent?
c)Fermat’s Last Theorem(FLT)states that the equation x n+y n=z n has
no integer solution with xyz=0and n≥3.Express FLT as a formula of
predicate calculus with domain Z.
Note:You may use the basic operations of ordinary arithmetic,including
powers‘x n’and the comparison operators’=’,’≤’.No further abbreviations
are allowed.The domain(universe of discourse)must be the set of all integers. Question2(15marks)
Three black balls,three red balls and three yellow balls are arranged in a3×3 matrix in such a way that there is no monochromatic row or column(“monochro-matic”refers to balls of the same color).Balls of the same color are considered as indistinguishable.In how many ways can this be done?
Question3(15marks)
Suppose a1,a2,...,a10are integers satisfying1≤a1≤a2≤···≤a10≤40.Show that there exist distinct3-subsets{i,j,k}and{r,s,t}of{1,2,...,10}such that
a i+a j+a k=a r+a s+a t.
Question4(20marks)
Let G be the simple graph whose vertices are the subsets S⊆{1,2,3,4,5,6,7} with|S|=3,two vertices S and T being adjacent if and only if S∩T=∅.
a)How many vertices and edges does G have?
b)Is G regular?If applicable,determine its degree.
c)Is G connected?
d)Is G bipartite?
Question5(15marks)
a)Find a particular solution of the recurrence relation
a n=3a n−1−4a n−3+4n.
Hint:The recurrence relation has a solution of the form a n=cn+d,where
c,d are constants.
b)Determine the general solution of the recurrence relation in a).
Question6(20marks)
A list a=(a0,a1,...,a n−1)of integers is said to have a(contiguous)zero subsum
if there exist0≤i≤j≤n−1such that a i+a i+1+···+a j=0.
