MATH1081 Past exams (with answers ). PDF

Preview

Summary

MATH1081 Past exams, a good practice material for the final exam. Hope you guys can get high marks !...

Description

MATH1081 Discrete Mathematics PAST EXAM PAPERS AND SOLUTIONS Copyright 2019 School of Mathematics and Statistics, UNSW

Contents PAST EXAM PAPERS JUNE 2012 . . . . NOVEMBER 2012 JUNE 2013 . . . . NOVEMBER 2013 JUNE 2014 . . . . NOVEMBER 2014 JUNE 2015 . . . .

. . . . . . .

4

SOLUTIONS TO PAST JUNE 2012 . . . . NOVEMBER 2012 JUNE 2013 . . . . NOVEMBER 2013 JUNE 2014 . . . . NOVEMBER 2014 JUNE 2015 . . . .

EXAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

PAPERS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

31 . 32 . 37 . 42 . 49 . 58 . 63 . 69

3

5 8 11 14 18 21 25

4 PAST EXAM PAPERS

The solutions to the examination papers contained here have been written by many members of staff of the School of Mathematics and Statistics. While every care is taken to avoid errors, we cannot guarantee the solutions are error-free. Please report any serious errors to the Director of First Year Mathematics. Exam papers from 2015 semester 2 to 2018 semester 2 will be provided on Moodle for practice before the exam.

5 MATH1081 Semester 1 2012 1.

i) You are given the following information about the sizes of the sets A, B and C: |A ∪ B ∪ C | = 31, |A ∩ B| = 4, |A ∩ C | = 7, |B ∩ C | = 6, |A| = 18, |B| = 11, |C| = 15. Find |A ∩ B ∩ C |. ii) Let A and B be general subsets of some universal set U . Use the laws of set algebra to simplify A ∪ ((B ∪ Ac ) ∩ B c ). State any set laws that you use. iii) For the set A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, the function f : A → A is defined by the rule that f (x) is the inverse of x (mod 11). For example, f (2) = 6 since 6 is the inverse of 2 modulo 11. a) b) c) d)

Find f (10). Is f a bijection? Give reasons. Compute f −1 ({1, 3, 5}). What is the special relationship between f and f −1 for this particular function?

iv) A partition of a natural number n is a list of strictly positive numbers which sum to n, written in decreasing order. Thus p = [4, 3, 3, 1, 1] is a partition of 12, as is q = [3, 3, 2, 1, 1, 1, 1]. Given two partitions of n, say t and u, we define t  u if we can obtain t from u by further subdividing some of the elements of u. Thus, in the example above, q  p, since the 4 can be further split into 2, 1, 1. This makes the partitions of n into a poset Part(n) (you may assume this). a) b) c) d)

2.

List the seven partitions of 5. Draw the Hasse diagram for this poset Part(5). Does the poset Part(5) have a greatest element? Find two elements a, b of the poset Part(5) such that the least upper bound of a and b does not exist.

i) Find all integer solutions to the congruence equation 42x ≡ 39 (mod 99), which lie in the range 0 < x < 120. ii) a) Give a formal definition of a graph. What is a simple graph? b) State and prove the Handshaking Theorem. c) Give an example of two non-isomorphic graphs whose vertex degree sequences are the same. iii) Consider the graph G consisting of the vertices of a cube and its edges. a) Draw a planar representation of this graph, labelled with vertices 1, 2, 3, 4, 5, 6, 7, 8 so that the path 123456781 is a Hamiltonian circuit, and so that 1 and 6 correspond to opposite vertices in the cube. b) Is the graph G bipartite?

6 c) With the above labelling, write down the first four rows of the adjacency matrix A of the graph. d) Without computing the matrix product A3 , compute the (1, 3) entry and the (1, 6) entry of A3 . iv) Use Dijkstra’s algorithm to construct a tree giving shortest paths from A to each of the other vertices in the following weighted graph. You should produce a table clearly giving the shortest distances from A to each vertex, but you are not required to explicitly write out all the steps of the algorithm. A 3 B 2 C 3

2

1

D

3.

1

3 1

2

3 4

3

E

2

1 F

3

G

2

H

i) Construct a truth table for the propositional formula ((∼p) → (q ∧ r)) ∧ (r → p) . ii) State, with reasons, whether or not each of the following statements is true or false. a) An integer n is a multiple of 6 if n is a multiple of 3. b) An integer n is a multiple of 6 only if n is a multiple of 3. iii) You are given a theorem, together with the basic ideas needed to prove it. Write up a detailed proof of the theorem. Your answer must be written in complete sentences, with correct spelling and grammar. It must include a suitable introduction and conclusion; reasons for all statements made; correct logical flow and any necessary algebraic details. Theorem. For every positive real number a, the equation e−x = ax has a real solution x > 0. Basic ideas. If f (x) = ax − e−x then f (0) is negative and f ( 1a ) is positive.

iv) Prove that log10 7 is irrational.

v) Let R be the set of real numbers, let a be an element of R and let S be a subset of R. We say that a is a limit point of S if ∀ε > 0 Consider the set

∃x ∈ S

( x 6= a ∧ |x − a| < ε ) .

o n 1 1 1 1 S = 1, , , , . . . . 2 3 4 5

a) Prove that 0 is a limit point of S . b) Write in symbols the statement that a is not a limit point of S. Simplify your answer so that the symbol ∼ is not used. c) Show that if s is an element of the set S, listed above, then s is not a limit point of S.

7 4.

i) Solve the recurrence an − 7an−1 + 10an−2 = 16n, subject to the initial conditions a0 = 5 and a1 = 4. ii) a) How many words can be made by rearranging all thirteen letters of TO BE OR NOT TO BE? b) How many of the words found in a) consist of six vowels followed by seven consonants? iii) Four friends called Julia, Tony, Wayne and Joe are playing a hand of bridge. A standard pack of 52 cards is dealt out, 13 cards being given to each player. a) Find the probability that the cards dealt to Julia and Wayne include all thirteen spades. b) Find the probability that the cards dealt to Julia and Wayne include at least one complete suit (that is, thirteen spades, thirteen hearts, thirteen diamonds or thirteen clubs). iv) A sum of $111 is to be distributed among eight people. In how many ways can this be done: a) if each person receives a whole number of dollars (that is, $0, $1, $2, . . . )? b) if each person receives a multiple of 5 cents (that is, $0.00, $0.05, $0.10, . . . , $0.95, $1.00, $1.05, . . . )? c) if each person receives a whole number of dollars, and no-one receives more than $15? v) a) When is the average of two integers also an integer? b) Let (xi , yi ), for i = 1, 2, 3, 4, 5, be five distinct points in the plane with integer coordinates. Use the pigeonhole principle to show that the midpoint of at least one pair of these points has integer coordinates.

8 MATH1081 Semester 2 2012 1.

i) Use the laws of set algebra to simplify (A − B) ∪ (A ∩ B ).

ii) Find an example to show that the equality

A ∩ (B ∪ C) = (A ∩ B) ∪ C is not true for all sets A,B,C . iii) a) Suppose that An is a set for n = 1, 2, . . . . Explain briefly the meaning of

∞ \

An .

n=1

b) Find

∞ \

[−1/n, 1/n]. Give a brief reason for your answer.

n=1

iv) Define a relation ∼ on R by x ∼ y if and only if there exists k ∈ Z such that x − y = 2kπ . a) Show that ∼ is an equivalence relation. b) Write R as the union of pairwise disjoint equivalence classes [x], for x ∈ R. c) Find a bijection ϕ : (R/ ∼) → T from the collection (R/ ∼) of all equivalence classes [x] of ∼ onto the unit circle T = {z ∈ C : |z| = 1 } in C. Show carefully that ϕ is both injective and surjective. v) Let A be the poset {{1}, {2}, {4}, {1, 2}, {1, 4}, {3, 4}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, ⊆}. a) Draw a Hasse diagram for A b) Find the upper bounds of the set {{2}, {4}} in A. c) Does {{2}, {4}} have a least upper bound in A? 2.

i) a) Find an integer x such that 50x = −1 (mod 101). b) Find 50−1 (mod 101). c) Find 2300(mod 18). ii) You are given that 1039−1 ≡ 31 mod 2013. (You are NOT required to prove this.) a) Find integers k and ℓ such that 1039k + 2013ℓ = 1. b) Write down the general solution to 1039x + 2013y = 4.

iii) Consider the following graph K . A

B

C

D E Giving reasons for your answers, show that

F

a) K is bipartite,

9 b) c) d) iv) a) b)

K is planar, K has an Euler circuit, K has no Hamiltonian circuit. State Kuratowski’s theorem characterising non-planar graphs. Show that the following graph is not planar. A B

F

C

G

E

D

v) Use Kruskal’s algorithm, to construct a minimal spanning tree for the following weighted graph. Make a table showing the details of each step in your application of the algorithm. a

4

b 7 e

d 6

8

8 h

5 f

2

g

3.

c 3

3

6

7

5

4

9 i

i) Construct a truth table to verify the following logical equivalence (p ∧ q) → r ≡ ∼ p ∨ (q → r ). ii) You are looking for your keys, and you say to yourself... (1) If I parked the car on the street last night, then my keys are not in the garage. (2) If I took the rubbish out last night, then my keys are in the garage. (3) If I opened the front door with my keys last night, then my keys are hanging in the front door. (4) My keys are locked inside the car or I took the rubbish out last night. (5) I parked the car on the street last night. a) Let s = “I parked the car on the street last night”, r = “I took the rubbish out last night”, o = “I opened the front door with my keys last night”, g = “My keys are in the garage”, f = “My keys are hanging in the front door” c = “My keys are locked inside the car”.

10 Write the propositions (1)–(5) in symbolic form using logical connectives. b) Deduce where the keys are from (1)–(5) using rules of inference. Show your working and give a reason for each step. iii) Prove that for all integers n ≥ 2,      n+1 1 1 1 . 1− 2 1 − 2 ··· 1 − 2 = 2n n 3 2 iv) Let x and y be real numbers. Prove that if x is rational and y is irrational, then x + y is irrational. v) A sequence a0 , a1 , a2 , . . . of real numbers is said to diverge to infinity iff ∀M ∈ R

∃N ∈ N ∀n > N

an > M.

(∗)

a) Write in symbolic form the negation of (∗), and simplify your answer so that the negation symbol is not used. b) Prove that the sequence defined by an =

n 2n

does not diverge to infinity. 4.

i) How many strings of eight lowercase letters of the English alphabet contain a) exactly 2 vowels? b) at least 1 vowel? c) the letters x and y, with x occurring before y, if the letters are all distinct? ii) How many ways are there to distribute a) 18 identical lollipops among 4 children, with each child getting at least one lollipop? b) 9 different teddy bears among 4 children, with one child getting 3 and the other 3 children getting 2 each? iii) a) Find the solution of the recurrence an + an−1 − 6an−2 = 0, subject to the initial conditions a0 = 1 and a1 = 7. b) Find a particular solution of the recurrence an + an−1 − 6an−2 = 4n . iv) Two types of paving slabs are available for laying a straight path of width 1 unit: the 1-unit by 1-unit slab and the 1-unit by 2-unit slab. No slabs are to overlap and no gaps are to be left. Here is an example of a path of length 9 units:

Let pn be the number of ways to lay a path of width 1 unit and length n units. a) Find p1 , p2 and p3 . b) Obtain a recurrence relation for pn . (You do NOT need to solve this recurrence relation.)

11 MATH1081 Semester 1 2013 1.

i) You are given the following information about the sizes of the sets A and B: |A ∩ B| = 7, |A| = 18, |B| = 12. Find, giving brief reasons for your answer: a) b) c) d)

|A ∪ B |, |A − B |, |P (A × B)|, |P (A) − P (B )|.

ii) Let A and B be general subsets of some universal set U. Use the laws of set algebra to simplify (A ∪ B c ) ∩ (A ∪ (B ∪ A)c ). Give the name of any set laws that you use. iii) Find the last 2 digits for each of the numbers: 20135 ,

201320,

20131081 .

iv) a) Find gcd(258, 105). b) Find one pair of integers x, y satisfying the equation 105x + 258y = 12. c) Solve, or explain why there is no solution to: α) 105x ≡ 12 (mod 258) β) 12x ≡ 105 (mod 258).

v) Suppose that f : X → Y is a function. If C and D are any subsets of Y, show that

f −1 (C) ∪ f −1 (D) = f −1 (C ∪ D). 2.

i) Suppose that A = {2, 3, 5, 6, 15, 30, 35, 70, 105, 210}.

a) Draw the Hasse Diagram for the partially ordered set (A, |), where a | b means that a divides b. (You do not have to prove this is a partial order.) b) Find, if they exist, all α) greatest elements β) least elements γ) maximal elements δ) minimal elements c) Find two elements of A that do not have a greatest lower bound and explain why they do not.

ii) A graph H on the vertices A, B, C, D (in that order) has adjacency matrix:   1 2 0 0 2 0 1 0   M =  0 1 0 0 . 0 0 0 2

12 a) Draw the graph H. b) M 3 has the number 12 in position 1,2 (that is, in the first row and second column). What does this mean in terms of the graph? iii) Consider the graph G drawn below. a) Does G have an Euler path or circuit? Give the vertex list for the path/circuit, or explain why they do not exist. b) Does G have a Hamilton circuit? Give the vertex list for the circuit, or explain why it does not exist. c) Is G planar? Draw it as a planar graph, or give reasons why it is not planar. A

B

C

D

F

G

E

iv) Consider the weighted graph drawn below. a) Use Kruskal’s algorithm to construct a minimal spanning tree for the graph. Clearly show all your working. b) Explain briefly why the minimal spanning tree is unique.

5

B

C 2

3

4

2

G

4

A

D

3 4

3.

1

3

3

2

F E 2 formula i) a) Construct a truth table for the propositional (p → (∼q)) ∧ (q → (p ∧ (∼r))) . b) Is the proposition in (a) a tautology, a contradiction, or neither? ii) State, with reasons, whether or not each of the following statements concerning a real number x is true or false: a) x2 > 100 if x > 10;

13 b) x2 > 100 only if x > 10. iii) You are given a theorem, together with the basic ideas needed to prove it. Write up a detailed proof of the theorem. Your answer must be written in complete sentences, with correct spelling and grammar. It must include a suitable introduction and conclusion; reasons for all statements made; correct logical flow and any necessary algebraic details. Theorem. All solutions of the equation 2x3 − 4x + 1 = 0 are irrational.

Basic ideas. If x = p/q then 2p3 − 4pq 2 + q 3 = 0, so q is even. If q = 2r then p3 − 8pr 2 + 4r 3 = 0, so p is even. √ iv) Let a and x be positive real numbers with x ≥ a x. Prove that p p √ √ x+a x− x−a x > a . v) The function f : Z → Z is defined by ( 3n + 2 if n is even f (n) = 2n + 3 if n is odd. Prove that the range of f is { m ∈ Z | m ≡ 1, 2, 5, 8 or 9 (mod 12) } . 4.

i) Solve the recurrence an − 6an−1 + 9an−2 = 2n

subject to the initial conditions a0 = 6 and a1 = −1.

ii) Let S be the set of all 14–letter words formed from the 26 letters of the English alphabet, with no letter used more than once in a word. a) How many such words are there altogether? b) How many of the words in S contain at least one of the subwords JULIA and TONY? c) How many of the words in S contain all five vowels? iii) Find the number of solutions to the equation x1 + x2 + x3 + x4 + x5 + x6 + x7 = 45 , where x1 , x2 , x3 , x4 , x5 , x6 , x7 are non–negative integers, a) with no further restrictions? b) if x4 ≥ 4 and x5 ≥ 5? c) if every xk is a multiple of 3? iv) A club has n members. At a forthcoming election, r of the members are to be chosen to form a committee, and one of the committee members is to be chosen as president. a) By counting in two ways the possible outcomes of the election, prove that rC (n, r) = nC (n − 1, r − 1) . b) Hence, otherwise, find

n X r=1

rC (n, r).

14 MATH1081 Semester 2 2013 1.

i) a) Let f : X → Y be a function, and suppose A ⊂ X and C ⊂ Y. Give a definition of the sets f (A) and f −1 (C ). b) Let f : R → R be the function defined by f (x) = x2 − 2x − 3 for x ∈ R. α) Find f ([−2, 4]). β) Find f −1 ([0, 5]). c) Give an example of a function f : X → Y and two subsets A, B of X such that f (A ∩ B) 6= f (A) ∩ f (B). d) Prove that for any two subsets A, B of X, f (A ∩ B) ⊆ f (A) ∩ f (B). ii) a) Suppose that An is a set for n = 1, 2, . . . . ∞ [ Briefly explain the meaning of An . n=1

∞ [ 1 [ , n]. Give a brief reason for your answer. b) Find n n=1

iii) a) Let n ≥ 2 be an integer. Calculate

n X k=2

1 . k(k − 1)

b) Use your result in (a) to show that 1 is an upper bound of the set (N ) X 1 : N = 2, 3, . . . . k2 k=2

iv) Define a relation ∼ on the set S = {0, 1, 2, 3, 4, 5, 6} by x ∼ y if and only if x3 ≡ y3 (mod 7). a) Show that ∼ is an equivalence relation on S. b) Determine all the equivalence classes of S with respect to this equivalence relation. 2.

i) a) Find the least positive integer n, (n ≤ 6), such that 2007n ≡ ±1 (mod 19). b) Hence, or otherwise, find

20072007 mod 19.

ii) Solve each of the following congruences, or explain why it has no solution. a) 296 x ≡ 8 (mod 692). b) 369369 x ≡ 1 (mod 963963).

iii) Consider the following graph G.

15 b

a c

f e d

Explain why: a) G has an Euler path; b) G has a Hamilton circuit; c) G is not bipartite; d) G is not planar. iv) Let K be the following simple graph.

A

B