DEPARTMENT  OF  COMPUTER  SCIENCE

COMP2121 Discrete Mathematics

Date:May    8,2024

1 Logic and Proofs(19 points)

(a)(5  pt)Assume that the following premises are true:

It is not sunny this morning and the temperature is lower than yesterday.

Agatha goes on a day trip only if it is sunny in the morning.

If Agatha does not go on a day trip then she does some gardening that day.

If Agatha is not home for dinner then she has not been gardening that day.

Show that the above premises lead to the conclusion that Agatha will be  home for dinner that day.

(b)(5 pt)A formula where the-operator is only applied to atomic propositions and using connec- tives ^,V is said to be  in negation normal  form.Simplify the following formula to negation normal form.:→Vx[Ny[(x

(c)(5 pt)Suppose the domains of all variables are the same,and the following statements are true: Vx[P(x)→┐(Q(x)^R(æ)],3x[P(x) へQ(æ)],and                Vx[S(x)→R(æ)].

Use the rules  of inference to  argue whether the  following  statement  is  true:3x-S(x).

(d)(4 pt)Prove the following Proposition

Prop. :For every positive integer n,there exist n consecutive composite integers,

by means of a Constructive Existence Proof.Note that a composite integer is a positive integer that has at least one divisor other than  1 and itself.

Hint:Consider a sequence of numbers in the immediate vicinity of(n+1)!.

2   Sets   and   Relations(17   points)

(a)(4  pt)For  arbitrary  finite  sets  A,B  and  C,prove  that

(A∩B)U(AnC)=(AnB)u(AnC)u(BnC).

Note that A denotes the complement of set A,and similarly for the other sets in the question.

(b)(6 pt)Let S be a subset of {1,2,…,2n}such that S has n+1 elements.Prove that there are different elements a,b∈S such that a divides b.

(c)Let  set  S  be  defined  as

Consider the relation R defined on the  set  S  as aRb if and only if  ∈Q.Here  Q  denotes the set      of      rational      numbers.

(i)(4  pt)Prove  that  R  is  an  Equivalence  Relation.

(ii)(3pt)Show that the guralence Claso1-5 n Ris gienby

3 Functions(10 points)

(a)(5   pt)Let    A    and    B   be    finite    sets.Letf:A→B    and    g:B→A   be    functions    such    that gof=IA,where  IA  is  the  identity  function  on  A(the  function  that  maps  every  element  in  A to itself).Show that f is an injection and g is a surjection.

(b)(5     pt)Show      that      Zk=1     k²·2k=0(n²·2”)for     n∈Z+.

Hint:You  may  use  the  identity  that  for   real   r>1.

4      Counting(19     points)

This question pertains to a series of counting problems faced by staff and students at Mars Uni- versity.

(a)A Math student Amy has factorized a positive integer n as n=pi¹·p2²·.·prm,where P1,…,Pm are distinct prime numbers and k1,.…,km are positive integers.

(i)(3 pt)In how many ways  can Amy write n  as the product  of two positive integers that have no  common  factors  assuming  that  the  order  matters(i.e.,that  for  example  4·9  and

9·4  are  regarded  as  different)?

(ii)(5 pt)Suppose  Amy  is  interested  in  the  specific  number  n=720.In  how  many  ways  can Amy  write  n=720  as  the  product  of  any two positive  integers(irrespective  of whether they  have  common  factors  or  not)assuming  that  the  order  does  not  matter(i.e.,that  for example 4·9  and  9·4  are regarded  as  the  same)?

Conjecture  a  formula  for  the  above  problem  for  general  n=pi¹·p2·..·Pm.

(b)(5  pt)Nine  members  of  the  University  Staff  Club  plan  to  meet  every  day  for  dinner.They willhave to sit in a 9-seat round table for dinner with the only constraint being that no two members  who  sat  together(in  neighbouring  seats)on  one  day  willsit  together  in  future.For how many days is this possible?

(c)(6   pt)Toby   is    studying   the    Theory   of   Diophantine   Equations    in   his   Number    Theory   Meets Algebra  course  and  wants  to  know  the  number   of  integer   solutions  to  the   equation

X1+x2+33+x4=28,

that obey the condition

-10≤xi≤20          for          i=1,..,4.

Use  the  Method   of  Stars-and-Bars   and   the   Inclusion-Exclusion   Principle   to  help   Toby   figure out   the   answer.

5    Probability(15 points)

(a)(4   pt)What's   the   probability   that   the   top   and   bottom   cards   of   a   randomly   shuffed   deck   are both   kings?Note   that   all   permutations   of  the   52   cards   in   the   deck   are   equally   likely   in   a random    shuffle.

(b)(5  pt)Suppose  people's  birthdays  are  independently  and  uniformly  distributed  over  the  seven days of the week from Sunday to Saturday.Let p(n)denote the probability that in a randomly chosen group of n people,at least two of them are born on the same day of the week.Give a closed-form  expression  for  p(n).Check  that  your  formula  gives  p(2)=1/7.

(c)(6 pt)Let X and Y be real random variables.For any fixed value y of Y,Bob considers a random  variable  X|y  that  takes  values  x  with  distribution  p(X|y)=x)=p(X=x|Y=y) and corresponding expected value E(X|y).He then defines a random variable E(X|Y)that takes values E(X|y)for y ranging over all possible values of Y.Similarly,he defines another random variable Var(X|Y)which takes values Var(X|y)for y ranging over all possible values of Y.Here E(·)and Var(·)denote mean and variance respectively.

Prove that these random variables satisfy the following identity:

Var(X)=Var(E(X|Y))+E(Var(X|Y)).

6    Graph Theory(20 points)

(a)A polyhedron is a geometric solid consisting of flat polygonal facesjoined at edges and vertices. In this question,we are especially interested in convex polyhedra,which have the property that any line segment connecting two points on the polyhedron must be entirely contained within the polyhedron.Every convex polyhedron can be projected onto the plane without edges crossing forming an undirected graph called the polyhedral graph.A regular polyhedron is one in which allthe faces are congruent (identical in shape and size)regular polygons (all angles congruent and all edges congruent)and the same number of faces meet at each vertex.A dodecahedron is a regular convex polyhedron consisting of 12 regular pentagons.

(i)(5 pt)How  many  convex  regular  polyhedra  are  there  such  that  each  face  is  a  triangle? Hint:Consider the relation between the number of faces and number of edges,and identify the possible degrees of a vertex in the regular polyhedral graph.

(ii)(1 pt)State an upper bound for the vertex connectivity of each of the polyhedral graphs from    part(i).

iii)(5 pt)You are given a solid dodecahedron and you color each pentagon with one of three colors  -red,blue  and  green.Prove  that  there  must  be  two  adjacent  pentagons  that  are colored with the same color.

(b)An  isomorphism  of  graphs  G  and  H  is  a  bijection  between  the  vertex  sets  of  G  and  H,f: V(G)→V(H)such  that  any  two  vertices  u,v ∈V(G)are  adjacent  in  G  if  and   only  if  f(u) and  f(v)are  adjacent  in  H.If  an  isomorphism  exists  between  two  graphs  G  and  H,then  they are  said  to  be  isomorphic  and  denoted  as  G~H.

Determine whether the following statements are True or False.Prove your answers.

(i)(2  pt)If two  simple,undirected  graphs  G  and  H  have  the  same  number  of  vertices  and edges and have the same chromatic number,then they are isomorphic.

(ii)(2  pt)If  two   simple,undirected   graphs   G   and   H   are   isomorphic,then   they   have   the   same chromatic     number.

(c)(5  pt)Let  G=(V,E)be  a  k-regular  bipartite   simple  undirected  graph  with  equal   sized  bipar- titions,for   some   k≥1.That    is,V=V₁UV2   with   V₁∩V₂=Ø   and    |Vi|=|V₂|,and   all    edges   in the graph connect vertices in V₁to vertices in V2.Use Hall's Marriage Theorem to show that G has a perfect matching.