Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Term 3 2019

MATH1081

DISCRETE MATHEMATICS

1.      i)  Consider the following weighted graph.

 

a)  State the number of paths from  A  to  B .

b)  State the weight of the shortest path from  A  to  B .

c)  State the weight of the longest path from  A  to  B .

d)  State the weight of the minimum spanning tree.

ii)  What is the smallest number of edges that must be removed to disconnect:

a)  a complete graph on  n  vertices  Kn  .

b)  a cycle of length  n   Cn  .

c)  a bipartite graph on  n  and  m  vertices  Kn,m  , where  n ≥ m .

iii)  Find the shortest path from  A  to every vertex in the following weighted graph.

 

iv)  Consider the following undirected graph, known as the Petersen graph.

 

a)  Is the graph bipartite? Give reasons.

b)  Does the graph contain a Euler path? Give reasons.

c)  Does the graph contain a Hamiltonian path? If so   nd one.

d)  Does the graph contain a Hamiltonian circuit? If so   nd one.


2.      i)   a)  Prove that  10n  ≡ ±1 (mod 11)  for any  n ∈ N .

b)  Suppose the integer x  has digits xn xn   1 · · · x1 x0  . Prove that x ≡ 0 (mod 11)  if and only if  P(− 1)ixi  ≡ 0 (mod 11) .

ii)  Let  C  be the unit circle and  N  be the point  (0, 1) . The stereographic projection maps any point  P  on the circle (except  N ) to the  x -axis at the point  X  where it intersects the line through  N  and  P .

 

Let  f : C −{N} 7→ R  be the function that takes a point  P  on the unit circle and outputs corresponding the  x -intercept from the stereographic projection.

a)  If  P = (a, b) C − {N} , express  f (P)  in terms of  a  and  b .

c)  Show that  f  is one-to-one.

iv)  Prove that if n  is any nonnegative integer then  4n + 2  is irrational.

v)  Let  a1 , a2 , a3 , . . .  be a sequence of real numbers.  The de  nition of the limit of the sequence,  limn→∞  an  = ℓ , is

ε > 0   N N   n N    |an | < ε .                      ( )

a)  Write in symbolic form the negation of ( ∗) , and simplify your answer so that the negation symbol is not used.

b)  By working directly from the de  nition, prove that

lim     n     = 1 n∞   5n − 2     5 .


3.      i)  How many dierent ways are there to distribute 80 identical balls and 40 distinct lollipops among 8 children

a)  with no further restriction?

b)  with each child getting at least one ball and exactly  5  lollipops?

ii)  How many 11-card hands can be dealt from a standard deck of 52 cards such that

a)  all cards are from the same suit?

b)  there is at least one value occurring exactly 3 times?

iii)  Consider the set of all  n -digit numbers formed by the digits  1 ,  2 ,  3 , 4 ,  5 ,  6 ,  7 ,  8 ,  9 . Let  an   be the number of such numbers containing an odd number of prime digits, and let bn   be the number of such numbers containing an even number of prime digits.

a)  Write  bn   in terms of  an  . Explain your answer.

b)  Obtain a recurrence relation for  an  . Explain your answer. (You do NOT need to solve this recurrence relation.)

iv)  Obtain the general solution to the recurrence

an − 6an   1 + 9an   2  = 5n · 3n .

v)  You are looking for your dog named“Spot”and you say to yourself:

(1)  If I read in the lounge then Spot was sleeping on my bed.

(2)  I read in the lounge unless I had a Skype meeting.

(3)  I had a Skype meeting only if I had coee.

(4)  Spot was sleeping in the patio whenever I had coee.

(5)  I did not have coee.

Let

a =“I read in the lounge”,

b =“I had a Skype meeting”,

c =“I had coee”,

d =“Spot was sleeping on my bed”,

e =“Spot was sleeping in the patio”.

Write the propositions (1)– (5) in symbolic form using logical connectives. Deduce where Spot is from (1)– (5) using rules of inference.  Show your working and give a reason for each step.