MATH1081 DISCRETE MATHEMATICS Term 1 2019
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Term 1 2019
MATH1081
DISCRETE MATHEMATICS
1. i) Let A = {2, 0, 1, 9} and B = {1, 0, 8, 1} . State
a) P (A - B) ;
b) lA x Bl ;
c) lP (A u B)l .
ii) Let
Sn = { (x1 , x2 , x3 ) e 勿3 : x1 + 2x2 + 3x3 = n and x1 , x2 , x3 < 0 } and define a relation > on Sn by
(x1 , x2 , x3 ) > (y1 , y2 , y3 ) t÷ x2 ≤ y2 and x3 ≤ y3 .
a) Draw the Hasse diagram for > when n = 5 .
b) Prove that > is a partial order on Sn for each positive integer n .
c) Define a relation R on Sn by
(x1 , x2 , x3 ) R (y1 , y2 , y3 ) t÷ x2 = y2 or x3 = y3 .
Show that, for all n < 3 , R is not an equivalence relation on Sn .
iii) a) Find the smallest positive integer n such that 7n = 1 (mod 57) .
b) Hence or otherwise, calculate
╱ 1000 7n \ mod 57 .
iv) Find the number of solutions to the equations
x1 + x2 + x3 + x4 + x5 + x6 = 70 ,
where x1 , x2 , x3 , x4 , x5 , x6 are non-negative integers,
a) with no further restrictions;
b) if xj < 10 for all j .
v) Consider the following propositions:
(1) If the weather was nice and I was not tired then I went for a walk.
(2) If the weather was not nice and I had enough money then I went to the cinema.
(3) I did not go to the cinema.
(4) I did not go for a walk.
(5) I had enough money.
a) Let
n = “The weather was nice”,
t =“I was tired”,
w =“I went for a walk”,
c =“I went to the cinema”,
m =“I had enough money”.
Write the propositions (1)–(5) in symbolic form using logical connec- tives.
b) Use the rules of inference to deduce whether you were tired. Show your working.
2. In parts i) and ii) of this question you should leave your answers in terms of powers, factorials and/or P and C notation.
i) The English alphabet has 26 letters, of which 5 are vowels and 21 are consonants. We will write all our words using upper case (capital) letters. Repetition of letters in words is allowed.
Find the number of 12 letter words (strings) using the English alphabet:
a) with no further restrictions;
b) containing exactly 4 vowels and no repeated consonants;
c) containing the subword “WATER” at least once
(e.g., “ZWATERZWATER” but not “ZWAZTERZZZZZ”).
ii) Let b1 , b2 , . . . , b14 be integers, with repetitions allowed. Define S = {(i, j) e 勿2 l 1 ≤ i, j ≤ 14, i < j} .
a) Write down the cardinality of S .
b) Prove that, for some r e {0, 1, . . . , 44} , there are at least ≠在ree pairs (i, j) e S such that
bi + bj = r (mod 45) .
iii) Consider the following statement:
V a e 勿 V b e 勿 a x e 勿 ax = b (mod 40).
a) Write down the negation of this statement, and simplify your answer so that the negation symbol is not used. You may use the symbol /= in your answer.
b) Is the negation true or false? Justify your answer.
iv) For all positive integers n , let an be the number of ways to tile a 2 x n grid with the following tiles:
5 |
|
white
2 x 1
5 |
|
|
|
grey
2 x 2
5 |
|
|
|
white
2 x 2
5 |
|
|
|
black
2 x 2
The arrow on each tile must always point upwards ( 5 ).
a) Write down a1 and a2 .
b) Clearly explain why
an = 2an ← 1 + 3an ←2
for n < 3 .
c) Solve this recurrence relation subject to the initial conditions that you wrote down in part a).
3. i) Consider the following graph G with vertices S, V1 , V2 , . . . , Vn , T , in which each vertex Vi is adjacent to S and T :
V1
V2
S T
Vn
G
a) Determine the number of Euler paths from S to T in G
α ) if n is even;
β ) if n is odd.
b) How many cycles of length 4 does G contain as subgraphs?
c) What is the degree of each region of G ?
d) State the number of Hamilton circuits in the planar dual G= .
ii) Graphs G1 and G2 are each simple and each have vertex degree se- quence 4, 4, 4, 3, 3 . Explain why G1 and G2 are isomorphic.
iii) Let G be a connected, simple, bipartite graph with vertex partition V = V1 u V2 with lV1 l = lV2 l = n , and suppose that each vertex has degree 4.
a) Determine the number of edges of G , with explanation.
b) Prove that G is not planar.
iv) Consider the following weighted graph:
2
6
6
2
3
a) Use Dijkstra’s Algorithm to find a spanning tree that gives the short- est paths from A to every other vertex of the graph. Make a table showing the details of the steps in your application of the algorithm.
b) Is the spanning tree found in part a) a minimal spanning tree? Explain your answer.
2022-04-29