MATH1081

Discrete Mathematics
Tutorial Problems

and

Past Exam Papers

With Solutions
Copyright 2020 School of Mathematics and Statistics, UNSW
Contents

PAST EXAM PAPERS 4

JUNE 2012 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
NOVEMBER 2012 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
JUNE 2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
NOVEMBER 2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
JUNE 2014 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
NOVEMBER 2014 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
JUNE 2015 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

SOLUTIONS TO PAST EXAM PAPERS 29

JUNE 2012 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
NOVEMBER 2012 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
JUNE 2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
NOVEMBER 2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
JUNE 2014 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
NOVEMBER 2014 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
JUNE 2015 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3
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 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) Find f (10).
b) Is f a bijection? Give reasons.
c) Compute f −1 ({1, 3, 5}).
d) 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) List the seven partitions of 5.
b) Draw the Hasse diagram for this poset Part(5).
c) Does the poset Part(5) have a greatest element?
d) Find two elements a, b of the poset Part(5) such that the least upper bound of a
and b does not exist.

2. 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
b
3 B
b
2 C
b

3 1 3
2 3
1 D b b
E 3
2
2 1
1 3
b b b

F 4 G 2 H

3. 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 ( a1 ) 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 ∃x ∈ S ( x 6= a ∧ |x − a| < ε ) .

Consider the set n 1 1 1 1 o

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 conso-
nants?
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
b b b

b b b

D E F
Giving reasons for your answers, show that
a) K is bipartite,
 9

b) K is planar,
c) K has an Euler circuit,
d) K has no Hamiltonian circuit.
iv) a) State Kuratowski’s theorem characterising non-planar graphs.
b) Show that the following graph is not planar.
Ab Bb

b b b
F C
G

b b

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.

b 4 a 5 c

7 3 3
6 5

d e 2 f

6 8 8 9
7
g h 4 i

3. 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,
    
1 1 1 n+1
1− 2 1 − 2 ··· 1 − 2 = .
2 3 n 2n

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
n
an =
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) |A ∪ B|,
b) |A − B|,
c) |P (A × B)|,
d) |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.

Ab

b
Cb Db b
B E

b b

F G

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.

Bb 5 Cb
2
3 1 4 2
G
b
4 b b
A D
3

4 3 3 2

b b

3. F 2 formula
i) a) Construct a truth table for the propositional E

(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
rC(n, r).
r=1
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
b) Find [ , n]. Give a brief reason for your answer.
n
n=1
iii) a) Let n ≥ 2 be an integer. Calculate
n
X 1
.
k(k − 1)
k=2

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 ≡

y 3 (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
bc

a bc

bc bc c
f
e bc

bc

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
bc bc

bc bc bc
C E
D

bc

a) Show by redrawing the graph that K is planar.

b) Use Euler’s formula to calculate the number of regions in any planar representation
for K.
c) Find the adjacency matrix of K, ordering the vertices alphabetically.

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

A
bc

7 9
6

B bc bc C
6
6 6
D
bc
4 5 8

4 6

E bc bc F
5

3. i) Construct a truth table to verify the following logical equivalence:

p → (∼ q ∨ r) ≡ (p ∧ q) → r.

ii) Consider the following propositions:

(1) John Doe passed the exam only if he was not late for the exam and had coffee
before the exam.
(2) If John Doe drove to the exam and the carpark was not open, then he was late
for the exam.
(3) If John Doe walked to the exam, then he had coffee before the exam.
(4) The carpark was not open.
(5) John Doe passed the exam.
(6) Either John Doe walked to the exam or he drove to the exam.
a) Let

p = “John Doe passed the exam”,

l = “John Doe was late for the exam”,
c = “John Doe had coffee before the exam”,
d = “John Doe drove to the exam”,
w = “John Doe walked to the exam”,
o = “The carpark was open”.

Write the propositions (1)–(6) in symbolic form using logical connectives.

b) Use the rules of inference to deduce whether John Doe drove or not. Show your
working.
 17

iii) Prove by mathematical induction that for all integers n ≥ 0,

1 1 1 1 n
1+ + + + ··· + n ≥ 1 + .
2 3 4 2 2
Hint: you may use the fact that
1 1 1 1 1
≥ n ≥ n ≥ ··· ≥ n = n+1 .
2n +1 2 +2 2 +3 2 +2 n 2
iv) For all integers x and y, prove that 3|(x2 + y 2 ) if and only if 3|x and 3|y.
v) The definition of lim f (x) = ℓ is
x→∞

∀ε > 0 ∃M ∈ R ∀x > M |f (x) − ℓ| < ε. (∗)

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 definition, prove that
3x2
lim = 3.
x→∞ x2 − 3

4. i) A group of 10 people at a wedding includes the bride and groom. How many different
ways can a photographer at the wedding arrange 6 people in a row from this group, if
the bride and the groom must be in the picture?
ii) How many solutions are there to the equation
x1 + x2 + x3 + x4 + x5 + x6 = 55,
if x1 , x2 , x3 , x4 , x5 , x6 are non-negative integers
a) with no further restrictions?
b) with xk ≤ 11 for every k?
iii) How many 8-card hands can be dealt from a standard pack such that
a) there are exactly 3 aces?
b) at least one value occurs exactly three times?
iv) a) Find the solution of the recurrence
an + an−1 − 12an−2 = 0,
subject to the initial conditions a0 = 3 and a1 = 2.
b) Find a particular solution of the recurrence
an + an−1 − 12an−2 = 3n .

v) When ascending a flight of stairs, an elf can take 1 stair in one stride or 3 stairs in one
stride.
Let an be the number of different ways for the elf to ascend an n-stair staircase.
a) Find a1 , a2 and a3 .
b) Obtain a recurrence relation for an . Give a brief reason. (You do NOT need to solve
this recurrence relation.)
c) Find the value of a6 .
18

MATH1081 Semester 1 2014

1. i) Let S = {1, 2, 3, 4} and T = {2, 3, 5}. Find:
a) (S ∪ T ) − (S ∩ T ),
b) (S − T ) × (T − S),
c) P (S) ∩ P (T ),
d) |P (S) ∪ P (T )|.
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) Briefly explain why there cannot exist two sets A and B such that

P (A − B) = P (A) − P (B).

iv) Evaluate:
20142014 (mod 17).
v) a) Prove that for all real k > 1,
 
1 1 1 1
2
< − .
k 2 k−1 k+1

b) Hence show that for all positive integers n ≥ 2,

n
X 1 3
2
< .
k 4
k=2

vi) Suppose that f is a function from a set X to a set Y .

a) Define what is meant by “f is injective (one-to-one)”.
b) Prove that:
if f (A) ∩ f (B) = f (A ∩ B) for all A, B ⊆ X,
then f is injective.

2. i) Let d =gcd(42,286).
a) Find d and integers x, y such that

42x + 286y = d.

b) Find all solutions to, or explain why there is no solution to, each of the following:
α) 42x ≡ 168 (mod 286)
β) 42x ≡ 286 (mod 168).
ii) Define a relation 4 on S = Z+ × Z+ by

(a, b) 4 (c, d) iff ab | cd.

a) Show that 4 is reflexive and transitive.

 19

b) Is 4 symmetric? Is 4 antisymmetric? Carefully explain your answers.

iii) Consider the following graph G:
Eb

b b
D A

b
F

b b
C B

Giving reasons, show that

a) G is not bipartite,
b) G contains an Euler path,
c) G contains a Hamilton circuit.
iv) a) State Euler’s Formula for a connected planar graph having
v vertices, e edges and r regions.
b) Show that if G is a connected planar simple graph with v ≥ 3 vertices, then

e ≤ 3v − 6.

c) Hence show that a connected planar simple graph with v ≥ 3

vertices has at least one vertex of degree less than or equal to 6.
v) Consider the following weighted graph:

Ab

6 2
1

b b E b
B D
3 3
3
2 4
b

Use Dijkstra’s algorithm to find a spanning tree that gives the shortest paths from A to
every other vertex of the graph. Make a table showing the details of each step in your
application of the algorithm.

3. i) Prove by cases that

5 | x2 + 2y 2 iff 5 | x and 5 | y.

ii) Prove by induction:

For all n ≥ 8, the equation 3x+5y = n has a solution x, y where x and y are non-negative
integers.
20

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. If p is a prime, then p is irrational.
√
Basic idea. If p = a/b, then a2 = b2 p so p|a, then p|b also.
iv) Show that 2n + 1 is prime only if n is a power of 2.
v) Use a truth table to verify the following logical equivalence:

p → (r → ∼ q) ≡ q → ∼ (r ∧ p).

vi) a) Use the laws of logical connectives to simplify

∼ [p ∧ (q → r)].

(You do not need to name the rules you use.)

b) Let the universe U be the set of all integers greater than 1.
Consider the statement which claims that every integer in U has a least divisor in
U:
∀m ∃d ∀k, d|m ∧ (k|m → d ≤ k).
Write in symbolic form the negation of this statement, and simplify your answer so
that the negation symbol is not used.
You may however use the symbol ∤. The result of (a) may be useful.

4. i) a) Solve the recurrence

an = 4an−1 + 5an−2 ,
subject to the initial conditions a0 = −1 and a1 = 7.
b) Find a particular solution of

an − 4an−1 − 5an−2 = 5n , for n ≥ 2.

ii) 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 20 letter words (strings) using the English alphabet:
a) with no further restrictions
b) containing exactly 3 vowels
c) containing the subword “MATHS”
iii) Let A be any set of 10 distinct positive integers less than 100. Define the term “element-
sum” of a set to mean the sum of all the elements in the set.
a) How many subsets are there of A?
b) Show that the largest element-sum of any subset of A is 945.
c) Use the pigeon-hole principle to deduce that there must be at least two different
subsets of A having the same element-sum.
iv) A die is rolled 5 times and the outcomes are recorded as a sequence a1 , a2 , · · · , a5 .
What is the probability that the sum a1 + a2 + . . . + a5 of the five outcomes is 10 ?
 21

MATH1081 Semester 2 2014

1. i) A confectionary company surveys 181 mathematics students to discover their preferences
for Mars Bars, Picnic Bars and Cherry Ripes. It is found that 20 students like all three;
37 like Mars Bars and Picnics; 30 like Picnics but not Cherry Ripes; 24 like Cherry Ripes
but not Mars Bars; and 1 student likes none of these. Altogether, how many of these
students like Mars Bars?
ii) Prove using the laws of set algebra that if A, B and C are sets then

(A − B) − (A − C) = (A − B) − C c .

(You may assume the formula X − Y = X ∩ Y c , for any sets X, Y.)

iii) a) Given the formula
tan A − tan B
tan(A − B) = ,
1 + tan A tan B
show that
tan(k + 1) − tan k
tan k tan(k + 1) = − 1.
tan 1
b) Hence evaluate the sum
n
X
tan k tan(k + 1) .
k=1

iv) Solve the congruence

44x ≡ 20 (mod 126) .

Give your answer as a congruence to the smallest possible modulus, and also as a con-
gruence modulo 126.
v) Let f be a function from X to Y, and let A be a subset of X.
a) Define what it means for f to be onto.
b) Prove that if f is onto, then (f (A))c ⊆ f (Ac ).

2. i) It is given that the relation is a subset of, defined on the set


S = ∅, {w}, {x}, {x, y}, {y, z}, {w, x, y}, {w, x, z}, {x, y, z} ,

is a partial order (do not prove this).

a) Draw a Hasse diagram for this partial order.
b) List all maximal elements of the partial order.
c) Is there a greatest element? If so, state what it is; if not, give reasons.
d) Find two elements A, B in S which do not have a least upper bound. Explain.
ii) A connected planar map has vertices of degrees 6, 5, 5, 2, 2, 1, 1.
a) How many regions does the map have?
b) Draw an example of such a planar map.
c) Does the graph have an Euler path? Give reasons.
iii) a) Use Kruskal’s algorithm to construct a minimal spanning tree T for the following
weighted graph. Make a table showing the details of each step in your application
of the algorithm.
22

b) Is T also a tree showing the shortest path from A to every other vertex? Explain.
B b 5 b C

4
7
3
5 2
b b
1 b b
A E F D
5
6
4 3 2
b b

G 2 H
iv) Let M be the adjacency matrix of the following graph, where the vertices are listed in
numerical order.

1 3 5 1080
b b b b b b b b

2 4 1079 1081

a) It is given that the (1, 1) entry of M 14 is 429. What does this tell you about the
graph?
b) Prove that if n is a positive even number, then the (1, 1) entry of M n is not zero.
c) Find the smallest positive odd n for which the (1, 1) entry of M n is not zero. Give
reasons for your answer.

3. i) Construct truth tables for the propositional calculus formulae

(∼ p) → (q → (∼ r)) and r → (p ∧ (∼ q)) .

Does the first formula logically imply the second? Does the second logically imply the
first? Give reasons for your answers.
ii) A fan of the science fiction show Doctor Which proposes the following argument.
If the TADRIS is out of control, then the Doctor will be lost in spacetime.
If Carla takes charge, then either the TADRIS will be out of control or the
Doctor will not be lost in spacetime.
Either Carla will take charge or the TADRIS will be out of control.
Therefore, the Doctor will be lost in spacetime.
a) Express this argument in symbolic form using logical connectives. Be careful to
define any notation you introduce.
b) Show that this argument is not logically valid.
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. Let a, b, m be integers. If gcd(a, b) = 1 and a | bm then a | m.
Basic ideas: ax + by = 1, so amx + bmy = m, and a | bm so a | LHS.
 23

iv) Let x be a real number. Prove that

jxk lxm
x= +
2 2
if and only if x is an integer.
v) A function f : R+ → R is said to be eventually positive if


∃ M ∈ R+ ∀ x ∈ R+ (x ≥ M ) → (f (x) > 0) .
a) Write down the negation of the above statement, and simplify it so that the negation
symbol is not used.
b) Prove that the function f : R+ → R defined by
1
f (x) = sin2 (πx) −
x
is not eventually positive.

4. i) a) Find the solution of the recurrence

an + 3an−1 − 4an−2 = 0 ,
subject to the initial conditions a0 = 7 and a1 = −3.
b) Find a particular solution of the recurrence
an + 3an−1 − 4an−2 = 10 .
ii) How many solutions has the equation
x1 + x2 + x3 + x4 + x5 + x6 = 78 ,
if x1 , x2 , x3 , x4 , x5 , x6 are non–negative integers and
a) there are no further restrictions?
b) all of x1 , x2 , x3 , x4 , x5 , x6 are odd numbers?
c) at least one of x1 , x2 , x3 , x4 , x5 , x6 is greater than or equal to 30?
iii) The 26 letters of the English alphabet are used twice each to form words of 52 letters.
How many of these words contain the subword UNSW?
iv) Strings of the digits 1 and 2 are to be constructed having sum n. The strings may be
of any length, and order is regarded as important. For example, if n = 10 then three
different possible strings are 1112212, 1122121 and 22222.
a) If the number of 2s in the string is exactly k, how many digits are in the string?
How many strings are possible in this case?
b) Let an be the total number of strings with sum n. Explain why
an = an−1 + an−2 ,
and find the values of a1 and a2 .
c) Using the above results, or otherwise, prove that
⌊n/2⌋
X
Fn+1 = C(n − k, k) ,
k=0

where Fm denotes the mth Fibonacci number,

with F1 = 1, F2 = 1.
24

MATH1081 Semester 1 2015

1. i) Let A = {m, a, t, h} and B = {1, 0, 8}. State the value of
a) |A × B|,
b) |P (A ∪ B)|,
c) |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 ∪ Ac )) ∪ (A ∪ B c )c .

Give the name of each set law that you use.

iii) a) Show that for all real k > 1,

4 (k − 2)(k + 2)
1− 2
= .
k k2
b) Hence calculate, for all integers n ≥ 3, the product
n  
Y 4
1− 2 .
k
k=3

iv) Define a relation ∼ on the set of complex numbers by

z∼w ⇐⇒ |z − 1| = |w − 1|.

a) Prove that ∼ is an equivalence relation on S.

b) Draw a sketch which shows the equivalence class of {2i}.
v) Let X and Y be finite sets of the same cardinality |X| = |Y | = n > 0 and let f : X → Y
be an injective (one-to-one) function from X to Y.
a) Prove that |f (A)| = |A| for all subsets A ⊆ X.
b) Using part a) or otherwise, explain why f is bijective.

2. i) Evaluate
20151082 (mod 11) .

ii) a) Find gcd(105, 342).

b) Find one pair of integers x, y satisfying the equation

105x + 342y = 9

c) Solve, or explain why there is no solution to:

α) 105x ≡ 9 (mod 342)
β) 105x ≡ 8 (mod 342).

iii) Consider the following graph G:

 25

Bbc Cbc

bc bc bc bc
A H I D

bc bc

F E

a) Prove that G does not contain an Euler path.

b) Show by re-drawing the graph that G is planar.
iv) Giving reasons, determine whether or not there is a simple graph for each of the following
sequences of vertex degrees. Draw examples of those that exist.
a) 4,4,3,3,3,2
b) 4,4,3,3,2
c) 4,4,4,3,1

v) Prove that the average vertex degree

1 X
d(v)
n
v∈V (T )

of a tree T on |V (T )| = n vertices is strictly less than 2.

26

vi) Consider the following weighted graph:

A
bc

4 5
1 5
B bc bc C
1
4 3
D
bc
2 2

6 1
bc bc
E 5 F

Use Dijkstra’s algorithm to find a spanning tree that gives the shortest paths from A to
every other vertex of the graph. Make a table showing the details of at least the first
three steps in your application of the algorithm.
 27

3. i) Use the standard logical equivalences to simplify

q ∨ ∼ (p → q).

ii) Consider the statement

If n2 is even, then n ≡ 2 mod 4. (†).

a) Write down the converse of (†). Is the converse true? If so prove it, if not give a
counter example.
b) Write down the contrapositive of (†). Is the contrapositive true? If so prove it, if
not give a counter example.
iii) Suppose that x is a real number, such that x ≥ −1.
Prove using mathematical induction, that, for all positive integers n,

(1 + x)n ≥ 1 + nx.

iv) Prove, using the rules of inference, that the following argument is valid:

p
(∼ p∨ ∼ q) →∼ r
r∨ ∼ p
∴q

v) Consider the following statement in which x, y, z are real numbers.

∀x ∃y ∀z (z > y → z > x). (∗)

a) Write down the negation of (∗) without using the symbol ∼ .

b) Which statement is true, (∗) or its negation? Give reasons for your answer.
28

4. i) A security agency sends messages using 12 letter code words, made up using the 26
letters of the English alphabet.
a) How many code words are possible?
b) If a code word is selected at random, what is the probability it contains exactly one
X?
c) How many code words contain at least one X and at least one Y and at least one
Z?
ii) a) Find the general solution to

an − 3an−1 + 2an−2 = 0.

b) Find a particular solution to

an − 3an−1 + 2an−2 = 2n .

iii) Ten identical chocolates are to be distributed between Anna, Ben and Conny. In how
many ways can this be done if each must receive at least one chocolate?
iv) Suppose that n2 + 1 dots are to √
be located inside a unit square. Prove that at least two
2
dots must lie within a distance of each other.
n
 29

SOLUTIONS TO PAST EXAM PAPERS

30

MATH1081 June 2012 Solutions

1. i) By the inclusion/exclusion principle,

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

Hence
31 = 18 + 11 + 15 − 4 − 7 − 6 + |A ∩ B ∩ C| ⇒ |A ∩ B ∩ C| = 4.
ii)
A ∪ ((B ∪ Ac ) ∩ B c )
= A ∩ ((B ∩ B c ) ∪ (Ac ∩ B c )) Distributive Law
c c
= A ∪ (∅ ∪ (A ∩ B )) Intersection with Complement
c c
= A ∪ (A ∩ B ) Identity Law
c c
= (A ∪ A ) ∩ (A ∪ B ) Distributive Law
= U ∩ (A ∪ B c ) Union with complement
= A ∪ Bc Identity Law
iii) a) f (10) = 10 since 10 × 10 ≡ 1 mod 11.
b) Yes, f is a bijection. Since 11 is a prime, every non-zero element x, 1 ≤ x ≤ 10, has
an inverse.

(Alternatively, one may compute a table of values for f for x from 1 to 10 and
see that the function is 1-1 and onto. )
c) f −1 ({1, 3, 5}) = {1, 4, 9}, since f (1) = 1, f (4) = 3 and f (9) = 5.
d) In this case f and f −1 are the same function.
iv) a) The seven partitions of 5 are [5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1].
b) Diagram as below
[5]

[4, 1] [3, 2]

[3, 1, 1] [2, 2, 1]

[2, 1, 1, 1]

[1, 1, 1, 1, 1]

c) Yes, Part(5) has a greatest element, namely [5].

d) The elements a = [3, 1, 1] and b = [2, 2, 1] do not have a least upper bound: both
[4, 1] and [2, 2, 1] are upper bounds, but there is no least one.
 31

2. i) By Euclid’s algorithm, gcd(99, 42) = 3 and reversing the steps gives

3 = 99 × 3 − 42 × 7.

Now we check that 3|39 is true so there are 3 solutions.

Hence 39 = 99 × 39 + 42 × −91. Thus the solution is x ≡ −91 ≡ 8 mod 33. Thus the
solutions are x ≡ 8, 41, 74 mod 99. In the given range the solutions are 8, 41, 74, 107.
ii) a) A graph consists of a set V of vertices and a set E of edges, and a function which
assigns to each e ∈ E an unordered pair of vertices from V .
A graph with no loops and no parallel edges is called a simple graph.
b) The Handsking Theorem states that the total degree of a graph equals twices the
number of edges.
Proof: Every edge contributes exactly 2 to the total degree. Hence twice the
number of edges equals the total degree.
c) Diagram as below,

b b b b

b b b b

iii) a) Diagram as below,

b
1 b
2

b b
3
8 b
4 b
7
b b

5 6

b) Yes, since {1, 3, 5, 7} and {2, 4, 6, 8} are give a partition of the vertices.
c)  
0 1 0 1 0 0 0 1
 1 0 1 0 0 0 1 0 
 
 0 1 0 1 0 1 0 0 
1 0 1 0 1 0 0 0
d) The (1, 3) entry and the (1, 6) entry of A3 are 0 and 6 respectively.
iv) DIAGRAM

edges available edge chosen vertex(distance)

AF (1), AD(2), AB(3) AF F (1)
AD(2), AB(3), DF (4), F G(5) AD D(2)
AB(3), F G(5), DB(5), DE(4), DG(5) AB B(3)
..... ..... E(4)
..... ..... G(5)
..... ..... C(5)
..... ..... H(5)
32

3. i) Call the full statement S

p q r ∼p q∧r (∼p) → (q ∧ r) (r → p) S
T T T F T T T T
T T F F F T T T
T F T F F T T T
T F F F F T T T
F T T T T T F F
F T F T F F T F
F F T T F F F F
F F F T F F T F
ii) False. For example 3 is a multiple of 3 but not of 6.
a) True. Any multiple of 6 ( = 2 × 3) must be a multiple of 3.
b) True. Any multiple of 6 ( = 2 × 3) must be a multiple of 3.
iii) Proof: Define f : R → R by f (x) = ax − e−x . Then the equation ax = e−x has a
solution if and only if f has a zero.
We have f (0) = −e0 = −1 < 0 and f (a−1 ) = 1 − e−1/a . But as a > 0, −1/a < 0
and hence e−1/a < 1, so that f (a−1 ) > 0. Furthermore, f is continuous (it’s actually
differentiable) and so the intermediate value theorem applies: the continuous function f
changes sign on [0, a−1 ] and so must have at least one zero in (0, a−1 ). Any such zero, x0 ,
say is strictly positive and satisfies ax0 = e−x0 , that is, it is a solution to the equation.

p
iv) Suppose not, and that log10 7 = , where p, q ∈ Z, q > 0 without loss of generality.
q
Then by definition of logarithms 7 = 10p/q or 7q = 10p . As q > 0, 7q > 1, so p > 0. But
the right hand side of 7q = 10p is then even, and the left hand side is odd, contradiction.
Hence log10 7 is not rational.
v) a) Let ε > 0. We need to find an x satisfying the conclusion of the definition. Define
1
N = ⌈ε−1 ⌉ + 1, so that x = ∈ S. Then x 6= 0 and as N > ε−1 , |x − 0| < ε, so 0
N
is a limit point.
b) a is not a limit point of S if

∃ε > 0 ∀x ∈ S (x = a ∨ |x − a| ≥ ε) .

1
c) Suppose s = ∈ S. We need to find an ε for which all other x ∈ S are at least
n
1
ε away from s. But the nearest other member of S will be , so let ε be any
n+1
1 1 1
positive number less than or equal to − = . Then every x ∈ S is
n n+1 n(n + 1)
either s or satisfies |x − s| ≥ ε, so s is not a limit point of S.

4. i) First solve the corresponding homogeneous equation, hn − 7hn−1 + 10hn−2 = 0 whose

characteristic equation is r 2 − 7r + 10 = 0 giving r = 2, 5 and so hn = A2n + B5n .
For a particular solution, we try , pn = a + bn. Substituting and re-arranging we have

(4a − 13b) + (4b)n ≡ 0 + 16n,

 33

whence a = 13, b = 4. Thus the general solution is

an = A2n + B5n + 13 + 4n.

Applying the initial conditions, we have 5 = A + B + 13, 4 = 2A + 5B + 17, whence,

A = −9, B = 1, so the solutions is

an = −9(2n ) + 5n + 13 + 4n.

ii) a)
13!
.
4!3!2!2!
b)
6! 7!
× .
4!2! 3!2!
iii) a) This can be considered as the situation in which we have 2 hands of 26 cards each.
Hand 1 (Julia and Wayne) and Hand 2 (Tony and Joe). The total number of Hands
1 and 2 is     
52 26 52
=
26 26 26
Hand 1 contains all the spades in
   
13 39 39
13 13 13
ways, so the required probability is
39


13 39!26!
52
= .
26
13!52!
 
4
b) Hand 1 will contain all the spades and all the clubs (say) in 1 way. There are
  1
4
ways of choosing 1 suit for Hand 1 and ways of choosing 2 suits and 0 ways of
2
choosing 3 or 4 suits. So by inclusion/exclusion, the number of ways in which Hand
1 contains at least one complete suit is
    
4 39 4
− .
1 13 2
Hence the probability is
4
39
4

1 13 − 2
52
.
26

iv) a) Let xi be the number of whole dollars received by person i, then

x1 + x2 + ... + x8 = 111


with xi ≥ 0. The number of such solutions is 118 7 , using the formula for partitions.
b) Let yi be the number of 5c pieces
received by person i,then y1 + ... + y8 = 111 × 20 =
2220 with yi ≥ 0 which has 22277 solutions.
34

c) Give $15 to each person and
count the number of ways to take back $9 from them
all. This can be done in 16
7 ways.
v) a) Only when the numbers are either both even or both odd.
b) There are 4 types of parity pairs, viz, (even, even), (even, odd), (odd, even), (odd,
odd). There are 5 points so by the pigeonhole principle, at least two points say
(x1 , y1 ) and (x2 , y2 ) have the same parity pair. Hence x1 and x2 are either both
even or both odd and so their average is an integer and similarly for the y ′ s. Thus
the midpoint of the interval joining these points has integer coordinates.
 35

MATH1081 November 2012 Solutions

1. i)

(A − B) ∪ (A ∩ B) = (A ∩ B c ) ∪ (A ∩ B) [definition of “−”]
= A ∩ (B c ∪ B) [∩ distributes over ∪]
=A∩U
= A [identity law]

ii) If A = ∅ and C 6= ∅, then A ∩ (B ∪ C) = ∅ but (A ∩ B) ∪ C = C 6= ∅.

T∞
iii) a) n=1 An = {x|x ∈ An , ∀n ∈ N}
b) 1/n → 0+ as n → ∞, so the sets [−1/n, 1/n], n = 1, 2, . . . , shrink to {0}. Indeed,

0 ∈ [−1/n, 1/n], for all n = 1, 2, . . . .

If x 6= 0, then there exists N = 1, 2, . . . such that 1/N < |x|, so that x ∈

/ [−1/n, 1/n]
for all n = N, N + 1, . . . ,.
iv) a) i) ∼ is reflexive: Let x ∈ R. Then x − x = 0 = 0 × 2π.
ii) ∼ is symmetric: Let x, y ∈ R satisfy x ∼ y. Then there exists k ∈ Z such that
x − y = 2kπ. Because y − x = 2(−k)π, we have y ∼ x, so ∼ is symmetric.
iii) ∼ is transitive: Let x, y, z ∈ R satisfy x ∼ y and y ∼ z. Then there exists k, j ∈ Z
such that x−y = 2kπ and y −z = 2jπ. Because x−z = (x−y)+(y −z) = 2(k +j)π,
we have x ∼ z, so ∼ is transitive. Consequently ∼ is an equivalence relation.
S S S
b) R = {[x]S: x ∈ (−π, π]} = x∈(−π,π] {x + 2kπ : k ∈ Z } or, R = {[x] : x ∈
[0, 2π)} = x∈[0,2π) {x + 2kπ : k ∈ Z }.
c) Let ϕ([x]) = eix , x ∈ (−π, π]. If z ∈ T then there exists a unique θ ∈ (−π, π] such
that z = eiθ , hence ϕ is a bijection.
v) a) Diagram as below

{1,3,4} {2,3,4}
b b b

{1,2,4}

b b
{3,4}
{1,2}
b

{1,4}
b b b

{2} {1} {4}

b) {1, 2, 4}, {2, 3, 4}

c) No. Neither set {1, 2, 4}, {2, 3, 4} is contained in the other.

2. i) a) x = 2 for instance (just guess)

36

b) 50−1 ≡ −2 ≡ 99 (mod 101)

c) 24 ≡ −2 (mod 18), so 2300 ≡ (24 )75 ≡ (−2)75 ≡ · · · ≡ 10 (mod 18).
ii) a) Use the Extended Euclidean Algorithm, or use the hint: we know that 1039 ×
31 ≡ 1 (mod 18), so 1039k − 1 = 2013ℓ for k = 31 and an integer ℓ; in particular,
1
ℓ = 2013 (1 − 1039 × 31) = −16. That is, k = 31 and ℓ = −16.
b) By a), 1039x + 2013y = 4 for x = 4 × 31 = 126 and y = 4(−16) = −64, so the
general solution is (x, y) = (124 + 2013t, −64 − 1039t) where t ∈ R.
iii) a) K is bipartite since it has no odd cycles.
b) K is planar, as the following re-drawing of K illustrates:
B

A D C F

E
c) K has an Euler circuit: it is connected and has no odd vertex degree.
d) K has no Hamilton circuit since such circuit would pass the vertices A, C, and D
and thus the six incident edges, and would therefore have to pass vertex B at twice,
which it may not.
iv) a) Kuratowski’s Theorem states that a graph is non-planar if and only if it has a
subgraph that is homeomorphic to K5 or to K3,3 .
b) Delete the edges BF and CD; the resulting graph is homeomorphic to K3,3 . By
Kuratowski’s Theorem, the graph is not planar.
v) Edge Weight Chosen?
ah 2 Y
ae 3 Y b 4 a 5 c
af 3 Y
7 3 3
ab 4 Y
hi 4 Y e
d 2 f
ac 5 Y
cf 5 N 6
be 6 N g i
h 4
eg 6 Y
bd 7 Y, stop

3. i)
p q r p∧q (p ∧ q) → r ∼p q→r ∼ p ∨ (q → r)
T T T T T F T T
T T F T F F F F
T F T F T F T T
T F F F T F T T
F T T F T T T T
F T F F T T F T
F F T F T T T T
F F F F T T T T
 37

Since (p ∧ q) → r and ∼ p ∨ (q → r) have the same truth values, the conditional

((p ∧ q) → r) ↔ (∼ p ∨ (q → r)) is a tautology. Hence ((p ∧ q) → r) ≡ (∼ p ∨ (q → r)).

ii) a)
(1)s →∼ g
(2)r → g
(3)o → f
(4)c ∨ v
(5)s
b)
(6) ∼ g modus ponens (1), (5)
(7) ∼ r modus tollens (2), (6)
(8)c elimination (4), (7)
Hence the keys are locked inside the car.

iii) Base step:

For n = 2,
1 3 2+1
LHS = 1 − = = = RHS.
22 4 2×2
Hence the result holds for n = 2.
Induction step:
Suppose that the result holds for n = k, i.e.,
    
1 1 1 k+1
1− 2 1 − 2 ··· 1 − 2 = .
2 3 k 2k
We want to prove that the result also holds for n = k + 1, i.e.,
     
1 1 1 1 (k + 1) + 1
1− 2 1 − 2 ··· 1 − 2 1− = .
2 3 k (k + 1)2 2(k + 1)
We have
 
k+1 1
LHS = 1− by the induction hypothesis
2k (k + 1)2
(k + 1)[(k + 1)2 − 1]
=
2k(k + 1)2
k2 + 2k
=
2k(k + 1)
k+2
=
2(k + 1)
= RHS.
Thus the result holds for n = k + 1.
Conclusion:
Hence by induction the result holds for all n ≥ 2.
38

iv) Let x be rational and y be irrational. Suppose that x + y is rational. Then we can write
a c
x= and x+y = for some integers a, b 6= 0, c, d 6= 0.
b d
Thus we can write
c a bc − ad
y= − = ,
d b bd
which is a ratio of two integers, indicating that y is a rational number. This contradicts
the fact that y is irrational. Hence x + y must be irrational.

v) a)
∃M ∈ R ∀N ∈ N ∃n > N an ≤ M
b) Since an ≤ 1, we can take M = 1 and n = N + 1, and the negation of (*) would be
satisfied.

4. i) a) There are C(8, 2) ways to choose the positions for the vowels and then 5 choices for
each vowel and 21 choices for each consonant. Since repeats are allowed, the answer
is
C(8, 2) 52 216 .
b) There are 268 strings of 8 letters, and 218 of these do not contain a vowel. Hence
the number of strings of 8 letters with at least 1 vowel is

268 − 218 .

c) There are C(8, 2) ways to choose two positions for x and y, but then only one way
to place x and y in these positions, since x must come before y. All other letters
must be distinct from each other and from x, y, giving P (24, 6) ways to complete
the string. Hence the answer is

C(8, 2) P (24, 6).

ii) a) First give one lollipop to each child. Then we still have 14 remaining lollipops to
distribute among 4 children. We can do this in C(14 + 3, 3) = C(17, 3) ways.
b) Line the children up in some fixed order (say, alphabetically by their full name).
Then select one of the four children and move them to the start of the line, in one of
4 ways. Let the first child choose three teddy bears, then let each subsequent child
choose two teddy bears. For a given choice of first child, the number of ways this
can be done is
9!
C(9, 3) C(6, 2) C(4, 2) C(2, 2) = 3 .
2! 3!
Hence the answer is
9!
4 3 .
2! 3!
iii) a) The characteristic equation is r 2 + r − 6 = (r − 2)(r + 3) = 0, with roots r = 2, −3.
Hence a general solution is

an = A 2n + B(−3)n
 39

for some A, B. Considering a0 and a1 gives the equations

A + B = 1,
2A − 3B = 7.

Subtracting twice the first equation from the second gives −5B = 5, so that B = −1.
Then the first equation says that A = 2. Hence the solution of the recurrence that
satisfies the given intial conditions is

an = 2n+1 − (−3)n for n ≥ 0.

b) Since 4 is not a root of the characteristic equation, we guess the solution an = c 4n .

Substituting this into the recurrence gives

c4n + c4n−1 − 6c4n−2 = 4n .

Dividing by 4n−2 gives

16c + 4c − 6c = 16,
which says that 14c = 16. Hence c = 8/7 and the particular solution is
8 n
an = 4 for n ≥ 0.
7

iv) a) By inspection p1 = 1 (as we must take a 1 × 1 unit slab) and p2 = 2 (we may take
one 1 × 2 unit slab or two 1 × 1 unit slabs). Similarly, p3 = 3 as we may use three
1 × 1 unit slabs, or a 1 × 1 unit slab with a 1 × 2 unit slab to its right, or a 1 × 2
unit slab with a 1 × 1 unit slab to its right.
b) The recurrence is
pn = pn−1 + pn−2 for n ≥ 2.
This follows by considering the two possible cases for the first slab. If the first slab
is a 1 × 1 unit slab then there are pn−1 ways to tile the remaining 1 × (n − 1) unit
path. Otherwise, the first slab is a 1 × 2 unit slab, and there are pn−2 ways to tile
the remaining 1 × (n − 2) unit path.
40

MATH1081 JUNE 2013 Solutions

1. i) a)
|A ∪ B| = |A| + |B| − |A ∩ B| = 18 + 12 − 7 = 23
b)
|A − B| = |A| − |A ∩ B| = 18 − 7 = 11
c)
|P (A × B)| = 2|A|×|B| = 218×12 = 2216
d)
|P (A) − P (B)| = |P (A)| − |P (A ∩ B)| = 218 − 27
ii)

(A ∪ B c ) ∩ (A ∪ (B ∪ A)c )
= (A ∪ B c ) ∩ (A ∪ (B c ∩ Ac )) De Morgan’s law
c c c
= (A ∪ B ) ∩ ((A ∪ B ) ∩ (A ∪ A )) distributive law
c c
= (A ∪ B ) ∩ ((A ∪ B ) ∩ U ) union with complement
c c
= (A ∪ B ) ∩ (A ∪ B ) identity law
c
=A∪B idempotent law

iii)

20135 mod 10 = 135 mod 100 = 93

201320 mod 100 = (20135 )4 mod 100 = 934 mod 100 = 1
20131081 mod 100 = (201320 )54 · 2013 mod 100 = 2013 mod 100 = 13

Hence the last digits for each of the numbers are 93, 01, and 13.
iv) a)

258 = 2 × 105 + 48
105 = 2 × 48 + 9
48 = 5 × 9 + 3
9 =3×3+0

Thus gcd(258, 105) = 3.

b)

3 = 48 − 5 × 9
= 48 − 5 × (105 − 2 × 48)
= 11 × 48 − 5 × 105
= 11 × (258 − 2 × 105) − 5 × 105
= 11 × 258 − 27 × 105

Thus 105 × (−27) + 258 × 11 = 3. Hence a solution to 105x + 258y = 12 is

x = −27 × 4 = −108 and y = 11 × 4 = 44.

 41

c) α) The equivalent equation is 105x − 258y = 12. All integer solutions are of the
form (
x = −108 − 258
3 λ = −108 − 86λ
105
λ∈Z
y = 44 − 3 λ = 44 − 35λ
Thus x ≡ −108 (mod 86) ≡ 64, 150, 236 (mod 258).
β) The equivalent equation is 12x − 258y = 105, which has no integer solution since
gcd(12, 258) = 6 but 6 does not divide 105.
v) (1) First suppose that x ∈ f −1 (C) ∪ f −1 (D). Then we have x ∈ f −1 (C) or x ∈ f −1 (D),
which implies that f (x) ∈ C or f (x) ∈ D, and therefore f (x) ∈ C ∪ D. This yields that
x ∈ f −1 (C ∪ D). Hence f −1 (C) ∪ f −1 (D) ⊆ f −1 (C ∪ D).
(2) Next suppose that x ∈ f −1 (C ∪ D). Then we have f (x) ∈ C ∪ D, which implies
that f (x) ∈ C or f (x) ∈ D, and therefore x ∈ f −1 (C) or x ∈ f −1 (D). This yields that
x ∈ f −1 (C) ∪ f −1 (D). Hence f −1 (C ∪ D) ⊆ f −1 (C) ∪ f −1 (D).
Combining (1) and (2), we conclude that f −1 (C) ∪ f −1 (D) = f −1 (C ∪ D).

2. i) a) The Hasse diagram is

210
b

b b b
30 70 105

b b b
6 15 35

b b b

2 3 5

b) We have
α) greatest element is 210
β) there is no least element
γ) maximal elements are 210
δ) minimal elements are 2, 3, 5
c) 2 and 3 have no element below them so they have no greatest lower bound.
Or lb({30, 70}) = {2, 5} but this set has no greatest element.
ii) The graph is

A D
B C
42

a) The number 12 in position 1,2 of M 3 indicates that there are 12 walks of length 3
from A to B.

iii) a) G has 6 vertices of odd degree, so it cannot have an Euler circut (needs none of odd
degree) or an Euler path (needs exactly 2 of odd degree).
b) A Hamilton circuit exists, for example ABCF GDEA.
iv) If we replace the edges BA, AE by a single edge BE, then the resulting graph is home-
omophic to G. This can then be redrawn as

Bb Db Fb

b b b

C E G

Hence it is isomorphic to a K3,3 with edge sets V1 = {B, D, F } and V2 = {C, E, G}.
Hence by Kuratovski’s Theorem, G is NOT planar.
a)
b) Kruskal’s algorithm proceeds as follows
Edge Weight Chosen?
BG 1 Y
CG 2 Y
CD 2 Y
DE 2 Y
EF 2 Y
AB 3 Y, stop
EG 3 N
GF 3 N
DG 3 N
AF 3 N
etc

B b
C
b

2
3 1 2
G
A b b b
D

b b

F 2 E
Total weight of the spanning tree is 12.
 43

c) All the edges of weights 1 and 2 are included after 5 steps. At the next step the only
edge of weight 3 that does NOT form a circuit with the previous subgraph is AB.
Hence there is no choice at any stage of the algorithm and so the resulting minimal
spanning tree is unique.

3. i) a) The truth table is given below.

(I) (II)
p q r ∼ q p → (∼ q) ∼ r p ∧ (∼ r) q → (p ∧ (∼ r)) (I) ∧ (II)
T T T F F F F F F
T T F F F T T T F
T F T T T F F T T
T F F T T T T T T
F T T F T F F F F
F T F F T T F F F
F F T T T F F T T
F F F T T T F T T
b) The proposition is neither a tautology or a contradiction.
ii) a) This statement is true: if x > 10 then x2 > 10x > 100.
b) This statement is false. For example, let x = −11. Then x2 = (−11)2 = 121 > 100,
but x < 10.
iii) Proof. For a contradiction, suppose that a rational solution of the equation exists. Let
x = p/q be a rational solution of the equation, where p, q are coprime integers. Since x
is a solution, we have
 3
p 4p
2 − + 1 = 0.
q q
Multiplying by q 3 gives
2p3 − 4pq 2 + q 3 = 0,
which implies that q 3 = 4pq 2 − 2p3 . Hence q 3 is even, and it follows that q must be
even (since the cube of an odd number is odd). Write q = 2r where r is an integer.
Substituting this into the above expression gives

2p3 − 16pr 2 + 8r 3 = 0,

and dividing by two and rearranging shows that

p3 = 8pr 2 − 4r 3 ,

which is even. Hence this implies that p is even, so 2 is a common factor of p and q.
This contradicts our assumption that p and q are coprime. Therefore the equation has
no rational solutions, as required.
iv) Proof. Since a > 0, we know that a4 > 0, and hence

(2x − a2 )2 = 4x2 − 4a2 x + a4 > 4(x2 − a2 x). (∗)

√
By assumption we have x ≥ a x, which implies that x2 ≥ a2 x, and hence that x > a2 .
Therefore we may take positive square roots of both sides of (∗) to obtain
p
2x − a2 > 2 x2 − a2 x.
44

We rearrange this inequality as

√ q √ √ √
(x + a x) − 2 (x + a x)(x − a x) + (x − a x) > a2 .

This can be rewritten as

q q 2
√ √
x+a x− x−a x > a2 .

√ √
Clearly x + a x > x − a x since x and a are both positive, so we may take positive
square roots of both sides to conclude that
q q
√ √
x + a x − x − a x > a,

as required.
v) First suppose that n is even, and write n = 2k where k ∈ Z. Then

f (n) = 3n + 2 = 6k + 2,

which proves that f (n) ≡ 2 (mod 12) or f (n) ≡ 8 (mod 12), depending on whether k is
even or odd, respectively.
Now suppose that n is odd, and write n = 2k + 1 where k ∈ Z. Then

f (n) = 2n + 3 = 4k + 5.

Now there are three cases depending on the value of k (mod 3). We have

5
 if k ≡ 0 (mod 3),
f (n) ≡ 9 if k ≡ 1 (mod 3)


13 ≡ 1 if k ≡ 2 (mod 3).

Combining these cases shows that the range of f is

{m ∈ Z | m ≡ 1, 2, 5, 8 or 9 (mod 12)},

as claimed.

4. i) We first solve the homogeneous recurrence

an − 6an−1 + 9an−2 = 0

This has characteristic equation r 2 − 6r + 9 = 0, that is (r − 3)2 = 0, so that r = 3, 3.

Hence
hn = A3n + Bn3n .
Next we try a particular solution in the original recurrence.
This will be of the form pn = c2n .
Substituting in gives
c2n − 6c2n−1 + 9c2n−2 = 2n
which solves to give c = 4 and thus pn = 4.2n = 2n+2 .
 45

The general solution of the original recurrence is therefore

an = A3n + Bn3n + 2n+2 .

We finally use the initial conditions

6 = a0 = A + 4, so that A = 2.
−1 = a1 = 3A + 3B + 8, so that B = −5.

Hence our final solution is

an = 2.3n − 5n3n + 2n+2 .
ii) a) 14 letters can be chosen from 26 with no repetitions and order being important in
26!
P (26, 14) = ways.
12!
b) Let J and T respectively denote the words containing the subwords “JULIA” and
“TONY” .
For |J|: there are P (10, 1) = 10 places for the subword “JULIA” and then we need
to arrange (in order) 9 letters from the remaining 21. Hence

|J| = 10.P (21, 9).

Similarly
|T | = 11.P (22, 10).
For |J ∩ T |: there are 7 places that we can put the words “JULIA” and “TONY”
and the order matters so the number of ways they can be placed is P (7, 2), then
there are 5 more letters from the remaining 17 for the rest of the word, so

|J ∩ T | = P (7, 2)P (17, 5).

Now using the Principle of Inclusion-Exclusion we have the required

|J ∪ T | = 10P (21, 9) + 11P (22, 10) − P (7, 2)P (17, 5).

Note that there are other ways of doing the counting that give the equivalent answers

10! C(21, 9) + 11! C(22, 10) − 7! C(17, 5)

21! 22! 17!
10 + 11 − 42 .
12! 12! 12!
c) First put the 5 vowels in order in the 14 spaces, then 9 of the 21 consonants. So the
number of ways this can be done is

P (14, 5)P (21, 9).

Different counting gives the equivalent answers of

14! 21!
C(14, 5) 5! P (21, 9) = C(21, 9).14! =
9! 12!
iii) a) Here we are considering x1 + x2 + · · · + x7 = 45 with all xk ≥ 0.
This is equivalent to placing 6 lines and 45 dots into 51 positions, so the number of
ways is
C(45 + 7 − 1, 7 − 1) = C(51, 6).
46

b) Now x4 ≥ 4 and x5 ≥ 5. We can place 9 dots into these places and then the number
of ways to arrange the remaining 36 dots is

C(42, 6).

Alternatively, let y4 = x4 − 4 and y5 = x5 − 5 and all other yk = xk , then we have

y1 + y2 + · · · + y7 = 45 − 9 = 36 with all yk ≥ 0.
c) Now there are 45/3 = 15 groups of “3 dots” to be placed with 6 lines, so the number
of ways is
C(21, 6).
Alternatively let zk = xk /3 for all k, so that z1 + z2 + · · · + z7 = 15 with all zk ≥ 0.
iv) a) Choose the r people for the committee in C(n, r) ways, then choose one of them in r
ways to be the president, giving rC(n, r) ways. Alternatively, choose the president
in n ways, then choose r − 1 of the remaining n − 1 for the rest of the committee,
giving nC(n − 1, r − 1) ways,
Hence rC(n, r) = nC(n − 1, r − 1).
b)
n
X n
X
rC(n.r) = nC(n − 1, r − 1)
r=1 r=1
Xn
=n C(n − 1, r − 1)
r=1
n−1
X
=n C(n − 1, k) putting k = r − 1
k=0
= n(1 + 1)n−1 by the Binomial Theorem
n−1
= n2

Alternatively, this sum counts all the “committees of size r with president” for all
sizes r, which can be interpreted as selecting the president (in n ways) and then
selecting a subset of the remaining n − 1 members and there are 2n−1 such subsets.
 47

MATH1081 November 2013 Solutions

1. i) a)
f (A) = {y|∃x ∈ A, y = f (x) }
−1
f (C) = {x|∃y ∈ C, y = f (x) }.
b) α) f ([−2, 4]) = [−4, 5].
β) f −1 ([0, 5]) = [−2, −1] ∪ [3, 4].
c) Suppose that X = {0, 1}, Y = {0}, f (0) = f (1) = 0. If A = {0} and B = {1}, then
A ∩ B = ∅, so f (A ∩ B) = ∅, but f (A) ∩ f (B) = {0}.
d) Let y ∈ f (A ∩ B). Then there exists x ∈ A ∩ B such that y = f (x). Because x ∈ A,
y ∈ f (A) and because x ∈ B, y ∈ f (B). Consequently, y ∈ f (A) ∩ f (B). This
proves that
f (A ∩ B) ⊆ f (A) ∩ f (B).
∞
[
ii) a) An = {x|∃n = 1, 2, . . . , such that x ∈ An }.
n=1
∞
[ 1
b) If x > 0, then there exist n = 1, 2, . . . such that 1/n < x < n, so (0, ∞) ⊆ [ , n].
n=1
n
∞
1 [ 1
On the other hand, [ , n] ⊆ (0, ∞), so [ , n] ⊆ (0, ∞), proving the equality
n n=1
n
∞
[ 1
[ , n] = (0, ∞).
n
n=1
iii) a)
n n  
X 1 X 1 1
= −
k(k − 1) k−1 k
k=2 k=2
n−1 n
X 1 X1 1
= − =1− .
k k n
k=1 k=2

b)
N N
X 1 X 1 1
≤ =1− < 1.
k2 k(k − 1) N
k=2 k=2
for N = 2, 3, . . . .
iv) a) If a ∈ S, then a3 = a3 (mod 8) and so a ∼ a. Therefore ∼ is reflexive.
Let a, b ∈ S and suppose that a ∼ b. Then a3 ≡ b3 (mod 7) and so, b3 ≡
a3 (mod 7), that is b ∼ a. Therefore ∼ is symmetric.
Suppose that a, b, c ∈ S and a ∼ b and b ∼ c. Then a3 ≡ b3 (mod 7) and
b3 ≡ c3 (mod 7). Consequently, a3 ≡ c3 (mod 7) and so ∼ is transitive.
Because ∼ is reflexive, symmetric and transitive, it is an equivalence relation.
b) To calculate the equivalence classes, first calculate the cubes of elements of S modulo
8.
x| 0| 1| 2| 3| 4| 5| 6|
x3 | 0| 1| 8| 27| 64| 125| 216|
x3 (mod 7)| 0| 1| 1| 6| 1| 6| 6|
so that [0] = {0}, [1] = {1, 2, 4}, [3] = {3, 5, 6}.
48

2. i) a) 2007 ≡ 12 (mod 19), so

20072 ≡ 122 ≡ 144 ≡ 11 (mod 19)
20073 ≡ 11 × 12 ≡ 121 ≡ 18 ≡ −1 (mod 19).
So the required n = 3.
b) 2007 = 3 × 669, so

20072007 ≡ 123×669 (mod 19)

≡ (123 )669 (mod 19)
≡ (−1)669 (mod 19)
≡ −1 (mod 19)
≡ 18 (mod 19)

ii) a) We apply the Euclidean Algorithm:

692 = 2 × 296 + 100

296 = 2 × 100 + 96
100 = 1 × 96 + 4
96 = 24 × 4 + 0

Hence gcd(296,692) = 4 which is a factor of 8, so the equation has 4 solutions mod

692.
We proceed by solving the equation with the gcd removed, namely solve 74x ≡ 2
(mod 173).
Dividing the above by 4 gives

173 = 2 × 74 + 25
74 = 2 × 25 + 24
25 = 1 × 24 + 1
24 = 24 × 1 + 0

Now working backwards we see

1 = 25 − 1 × 24
= 25 − 1 × (74 − 2 × 25)
= 3 × 25 − 1 × 74
= 3 × (173 − 2 × 74) − 1 × 74
= 3 × 173 − 7 × 74

Hence 74−1 ≡ −7 (mod 173) and the solution to

74x ≡ 2 (mod 173) is

x ≡ 74−1 × 2 (mod 173)

≡ (−7) × 2 (mod 173)
≡ −14 (mod 173)
≡ 159 (mod 173)
 49

This can also be written as

x = 159 + 173k, for k ∈ Z, or
x ≡ 157, 332, 505, 678 (mod 692).
b) 3 | 369369 and 3 | 963963. so that 3 | gcd(369369, 963963).
Thus gcd(369369, 963963) 6= 1 and by a theorem
369369x ≡ 1 (mod 963963) has NO solution.
iii) a) G has exactly 2 vertices of odd degree, namely ‘c’ and ‘f ’, so by Euler’s Theorem it
has an Euler path.
Alternatively we can list an Euler path, for example
cbaedaf ebf dcf
b) A Hamilton circuit exists, for example abcdef a.
Alternatively we have n = 6 vertices each with degree at least
n
2 = 3, so by a theorem a Hamilton circuit exists.
c) G contains circuits of odd length, for example abea, so by a theorem it is not
bipartite.
Alternatively, is we put ‘a’ in vertex set 1, then ‘b’ and ‘e’ must be in vertex set
2 since edges ab and ae exist. However ‘b’ and ‘e’ are connected by an edge, so G
cannot be bipartite.
d) If we remove edge cf then the resulting subgraph is homeomomorphic to the follow-
ing graph by absorbing ‘c’ into edge bd.

b
bc

a bc

bc
(c) bc

f
e bc

bc

This is isomorphic to K5 Hence by Kuratovski’s Theorem, G is NOT planar.

Alternatively, if we remove edges ae, bf , f d, we get the graph

b
bc

a bc

bc bc c
f
e bc

bc

d
50

which is isomorphic to K3,3 with vertex sets {a, c, e} and {b, d, f }, so by Kuratovski’s
Theorem, G is not planar.

[Note that trying to get a contradiction to the properties of a planar graph like
e ≤ 3v − 6 or v − e + r = 2 fails.]

iv) a) The graph

Abc

bc
D

bc bc bc
C E
B

bc

is an example of a planar representation for K.

b) Euler’s Formular is v − e + r = 2. Here v = 6, e = 8 so that r = 4.
[Note that this is confirmed by the 4 regions in (a).]
c) The matrix is

 
0 0 1 1 1 0
0 0 1 1 1 0
 
1 1 0 0 0 1
M = 
1
.
 1 0 0 0 0
1 1 0 0 0 1
0 0 1 0 1 0

v) a) Kruskal’s algorithm proceeds as follows: List the edges in increasing weight order,
then include edges that do not form a circuit, until all vertices are reached,
Edge Weight Chosen?
BE 4 Y
DE 4 Y
AF 5 Y
EF 5 Y
AE 6 N
giving the tree of minimal weight 24.
BC 6 Y, stop
BD 6
CD 6
DF 6
AB 7
etc
 51

A
bc

B bc bc C
6

D
bc
4 5

E bc bc F
5
Alterntively, if CD was higher in the list than BC, then the following minimal weight
A
tree results. bc

B bc bc C

6
D
bc
4 5

E bc bc F
5
There are no other possibilities.

3. i)
p q r ∼q ∼q ∨ r p → (∼ q ∨ r) p∧q (p ∧ q) → r
T T T F T T T T
T T F F F F T F
T F T T T T F T
T F F T T T F T
F T T F T T F T
F T F F F T F T
F F T T T T F T
F F F T T T F T

Since p → (∼ q ∨ r) and (p ∧ q) → r have the same truth values, the conditional

(p → (∼ q ∨ r)) ↔ ((p ∧ q) → r) is a tautology. Hence (p → (∼ q ∨ r)) ≡ ((p ∧ q) → r).
52

ii) a)

(1) p →∼ ℓ ∧ c
(2) d ∧ ∼ o → ℓ
(3) w → c
(4) ∼ o
(5) p
(6) w ∨ d

b)

(7) ∼ ℓ ∧ c modus ponens (1), (5)

(8) ∼ ℓ simplification (7)
(9) ∼ (d ∧ ∼ o) modus tollens (2), (8)
(10) ∼ d ∨ ∼∼ o De Morgans law (9)
(11) ∼ d ∨ o double negation (10)
(12) ∼ d elimination (11), (4)

Hence John Doe did not drive.

iii) Base step:

For n = 0,

LHS = 1 and RHS = 1.

Hence the result holds for n = 0.

Induction step:
Suppose that the result holds for n = k, i.e.,

1 1 1 k
1+ + + ··· + k ≥ 1 + .
2 3 2 2

We want to prove that the result also holds for n = k + 1, i.e.,

1 1 1 k+1
1+ + + · · · + k+1 ≥ 1 + .
2 3 2 2
 53

We have
   
1 1 1 1 1 1
LHS = + + ··· + k +
1+ + + · · · +
2 3 2 2k + 1 2k + 2 2k+1
   
k 1 1 1
≥ 1+ + k
+ k + ··· + k by induction hypothesis
2 2 +1 2 +2 2 + 2k
   
k 1 1 1
≥ 1+ + k k
+ k k
+ ··· + k
2 |2 + 2 2 + 2{z 2 + 2k}
2k times
 
k 2k
= 1+ + k
2 2 + 2k
 
k 1
= 1+ +
2 2
k+1
=1+
2
= RHS.

Thus the result holds for n = k + 1.

Conclusion:
Hence by induction the result holds for all n ≥ 0.

iv)
x mod 3
(x2 + y 2 ) mod 3 0 1 2
0 0 1 1
y mod 3 1 1 2 2
2 1 2 2
By exhaustion of cases, we see that (x2 + y 2 ) mod 3 = 0 if and only if x mod 3 = 0 and
y mod 3 = 0. Hence 3|(x2 + y 2 ) if and only if 3|x and 3|y.

v) a)
∃ε > 0 ∀M ∈ R ∃x > M |f (x) − ℓ| ≥ ε
b) We have    
 3x2   9 
 x2 − 3 − 3 =  x2 − 3  .
   

Assuming that x is sufficiently large so that x2 − 3 > 0, we want

9 9
< ε =⇒ x2 > + 3.
x2−3 ε
r
9
Hence, for all ε > 0, we can take M = + 3 such that for all x > M we have
ε
   
 3x2   9  9
 x2 − 3 − 3 =  x2 − 3  = x2 − 3 < ε.
   

This concludes the proof.

54

4. i) There are P (6, 2) ways to choose the positions for the bride and groom, and then P (8, 4)
ways in which to fill in the remaining spaces with four of the remaining guests. Hence
the answer is
P (6, 2) P (8, 4).
Alternative solution: Since the bride and groom must be present, there are C(8, 4) ways
to choose the other 4 people in the photo, and then 6! ways to arrange the six chosen
people (including the bride and groom). Hence the answer is

C(8, 4) 6! .

ii) a) There are C(55+5, 5) = C(60, 5) solutions to the equation with no further restriction
on the xk .
b) Write xk = 11 − yk for k = 1, . . . , 6. The equation becomes

66 − (y1 + y2 + · · · + y6 ) = 55,

that is,
y1 + y2 + · · · + y6 = 11.
Note that when all the yk are nonnegative, we have yk ≤ 11 for all k, which implies
that each xk is nonnegative. Hence, the solutions to this new equation with all
yk nonnegative are in one-to-one correspondence with the nonnegative solutions to
the original equation with all xk ≤ 11. The number of such solutions is therefore
C(11 + 5, 5) = C(16, 5).
iii) a) There are C(4, 3) ways to choose the three aces to include, and then C(48, 5) ways
to select the rest of the hand from all cards in the deck other than the aces. Hence
the answer is C(4, 3) C(48, 5).
b) We will need inclusion-exclusion. Let Sj be the set of all hands in which there
are precisely three j’s, where j ∈ {2, 3, 4, . . . , 10, J, K, A}. Arguing as in part (a),
|Sj | = C(4, 3) C(48, 5)} for all j.
Next, if j 6= k then |Sj ∩ Sk | = C(4, 3)2 C(44, 2), since there are C(4, 3)2 ways to
choose exactly three of each of the two chosen values, and then C(44, 2) ways to
complete the hand, avoiding these two values.
Finally, note that if j, k, ℓ are distinct then |Sj ∩ Sk ∩ Sℓ | = 0 as there are only 8
cards in the hand.
Therefore, by inclusion-exclusion, the answer is
X X
| ∪ j Sj | = |Sj | − |Sj ∩ Sk |
j j6=k

= 13 C(4, 3) C(48, 5) − C(13, 2) C(4, 3)2 C(48, 2).

iv) a) The characteristic equation is r 2 + r − 12 = (r − 3)(r + 4) = 0, with roots r = 3, −4.

Hence a general solution is

an = A 3n + B(−4)n

for some A, B. Considering a0 and a1 gives the equations

A + B = 3,
3A − 4B = 2.
 55

Subtracting three times the first equation from the second gives −7B = −7, so
that B = 1. Then the first equation says that A = 2. Hence the solution of the
recurrence that satisfies the given intial conditions is

an = 2 · 3n + (−4)n for n ≥ 0.

b) Since 3 is a root of the characteristic equation, we guess the solution an = cn 3n .

Substituting this into the recurrence gives

cn3n + c(n − 1)3n−1 − 12c(n − 2)3n−2 = 3n .

Dividing by 3n−2 gives

9cn + 3c(n − 1) − 12c(n − 2) = 9,

which says that 21c = 9. Hence c = 3/7 and the particular solution is
3 1
an = n 3n = n 3n+1 for n ≥ 0.
7 7

v) a) By inspection a1 = 1 (as we must go up 1 stair in one stride) and a2 = 1 (we must

ascend 1 stair in one stride, twice). Similarly, a3 = 2 as we may use ascend three
stairs in a single stride, or we may use three strides which each ascend one stair.
b) The recurrence is
an = an−1 + an−3 for n ≥ 3.
This follows by considering the two possible cases for the first stride. If the first
stride goes up one stair then there are an−1 ways to ascend the remaining n−1 stairs.
Otherwise, the first stride ascends 3 stairs, and there are an−3 ways to ascend the
remaining n − 3 stairs.
c) We have

a6 = a5 + a3
= a4 + a2 + a3
= a3 + a1 + a2 + a3
= 6.
56

MATH1081 JUNE 2014 Solutions

1. i) a) (S ∪ T ) − (S ∩ T ) = {1, 4, 5}
b) (S − T ) × (T − S) = {(1, 5), (4, 5)},
c) P (S) ∩ P (T ) = {∅, {2}, {3}, {2, 3}},
d) |P (S) ∪ P (T )| = 24 + 23 − 4 = 20.
ii)
(A ∪ B)c ∩ (A ∪ (B ∪ A)c ) = (A ∪ B)c ∩ (A ∪ (A ∪ B)c ) commutative law
= (A ∪ B)c Absorption law
= Ac ∩ B c De Morgan′ s law.

iii) Since the empty set belongs to P (A − B) but not P (A) − P (B) the two sets cannot be
equal.
iv) 2014 ≡ 8 mod 17, and 84 ≡ −1 mod 17. Hence

20142014 ≡ 82014 = 8503×4+2 ≡ (−1)503 82 ≡ −13 ≡ 4 mod 17.

1 2 1 1
v) a) RHS = × 2 = 2 > 2 = LHS.
2 k −1 k −1 k
b)
n n   n−2 n
!
X 1 1X 1 1 1 X 1 X 1 1 3 1 1 3
2
< − = − = ( − − )< .
k 2 k−1 k+1 2 k+1 k+1 2 2 n n+1 4
k=2 k=2 k=0 k=2

vi) a) For a, b ∈ X, f (a) = f (b) ⇒ a = b.

b) Suppose a, b ∈ X with f (a) = f (b). Put A = {a}, B = {b}. Then f (A) ∩ f (B) =
{f (a)} =
6 ∅. Thus f (A ∩ B) = f (A) ∩ f (B) 6= ∅. Hence A ∩ B 6= ∅ forcing a = b.
Hence f is injective.

2. i) a) Using the Euclidean algorithm (and underlining the remainders)

286 = 6 × 42 + 34
42 = 1 × 34 + 8
34 = 4 × 8 + 2
8 =4×2

Reversing to find the x and y:

2 = 34 − 4 × 8
= 34 − 4 × (42 − 1 × 34)
= −4 × 42 + 5 × 34
= −4 × 42 + 5 × (286 − 6 × 42)
= 5 × 286 − 34 × 42

So gcd(286, 42) = 2 = 5 × 286 − 34 × 42

 57

b) α) As 2 | 168 there are solutions, in fact 2 of them, modulo 286. Dividing by the
gcd gives 21x ≡ 84 (mod 143). We could use the inverse of 21 modulo 143, which
from the Bezout identity above is −34, but there is an obvious solution, x = 4. It
follows that the two solutions modulo 286 are 4 and 147.
β) Since 168 = 4 × 42, it follows that gcd(168, 42) = 42. And as 42 does not divide
286, there are no solutions.
ii) a) We have (a, b) 4 (a, b) as ab | ab, proving reflexivity.
Secondly if (a, b) 4 (c, d) and (c, d) 4 (e, f ) then ab | cd and cd | ef . So there are
positive integers p and q such that cd = (ab)p and ef = (cd)q. But then ef = (ab)pq,
so ab | ef or (a, b) 4 (e, f ) and 4 is transitive.
b) The relation is not symmetric, as for example (1, 2) 4 (2, 2) since 2 | 4, but (2, 2) 64
(1, 2).
The relation is not antisymmetric either, as for example (2, 1) 4 (1, 2) and (1, 2) 4
(2, 1) but (1, 2) 6= (2, 1).
iii) a) There are odd cycles, e.g. EAD.
b) There are exactly two vertices of odd degree, i.e. D and F; or an example is DE-
ABCDAFCEF.
c) For example ABCDEFA is a Hamilton circuit.
iv) a) v − e + r = 2
b) For a connected planar simple graph G with at least 3 vertices, each region in the
dual graph of G must have degree at least 3, and as the dual and G have the same
2
number of edges, sum of degrees of the dual = 2e ≥ 3r. So e ≥ r = e − v + 2 by
3
Euler’s formula, which rearranges to e ≤ 3v − 6.
c) If all the vertices have degree strictly greater than 6, then the sum of the degrees is
greater than 6v, so 2e > 6v. But from part b), 2e ≤ 6v − 12, contradiction.
v) Starting with the graph containing just A, we have:

step candidate edges (total distance) new edge new vertex v d(v, A)
1 AB(6), AE(1), AD(2) AE E 1
2 AB(6), AD(2), EB(4), ED(4), EC(4) AD D 2
3 AB(6), DC(6), EB(4), EC(4) EB B 4
4 BC(6), DC(6), EC(4) EC C 4

Giving the tree below:

Ab

2
1

b b E b
B D
3
3

C
3. i) If 5|x and 5|y then x = 5k, y = 5ℓ for some integers k, ℓ. Hence x2 + 2y 2 = 5(5k2 + 10ℓ2 )
and so is divisible by 5. For the converse, we note that a2 mod 5 ≡ 0, 1, 4 and so by
58

considering cases x2 + 2y 2 ≡ 0 mod 5 only occurs when x and y are both 0 mod 5, that
is, they are each divisible by 5.
ii) Let P (n) be the given statement. P (8) is true since (x, y) = (1, 1) is a solution in this
case. Let k be an integer for which the statement is true. That is, we suppose there are
positive integers X, Y such that 3X + 5Y = k. Consider the equation 3x + 5y = k + 1. If
Y > 0 then (X ′ , Y ′ ) = (X +2, Y −1) is a solution since 3X ′ +5Y ′ = 3(X +2)+5(Y −1) =
k + 1. In this case P (k + 1) is true. If Y = 0 then 3X = k and so X ≥ 3. Hence
(X ′ , Y ′ ) = (X − 3, 2) is a solution since 3X ′ + 5Y ′ = 3(X − 3) + 5(2) = k + 1. In this
case also P (k + 1) is true. Hence P (n) is true for all n ≥ 8 by induction.
√ √
iii) We give a proof by contradiction. Suppose that p is rational, then p = ab , where a, b
are coprime positive integers. Squaring and rearranging we have a2 = pb2 . Hence p is a
factor of a2 and hence a factor a (since p is prime) and so we can write a = kp for some
positive integer k. Substituting back, we obtain k2 p2 = b2 p and so b2 = k2 p. Hence p is
a factor of b2 and hence of b. This, however, contradicts the assumption that a and b
√
are co-prime. Therefore p is irrational.
iv) We are given that 2n + 1 is prime. Write the integer n as n = 2a N , where N is odd.
(Note that if n is odd, then a = 0 and if n is a power of 2, we have N = 1.) Now using
the standard factorisation for odd powers,

2n + 1 = (22 )N + 1 = (22 + 1)((22 )N −1 − (22 )N −2 + ... + 1).

a a a a

Since this number is prime, the second bracket has to be 1 (since the first is at least 3)
giving N = 1 and so n = 2a .
(I) (II)
p q r ∼q r → (∼ q) p → (r →∼ q) r∧p ∼ (r ∧ p) q →∼ (r ∧ p)
T T T F F F T F F
T T F F T T F T T
T F T T T T T F T
v)
T F F T T T F T T
F T T F F T F T T
F T F F T T F T T
F F T T T T F T T
F F F T F T F T T
vi) a) ∼ [p ∧ (q → r)] ≡∼ p∨ ∼ (q → r) ≡∼ p ∨ (q∧ ∼ r).
b)
∃m∀d∃k (d 6 |m ∨ (k|m ∧ d > k)) .

4. i) a) The recurrence is
an − 4an−1 − 5an−2 = 0.

This has characteristic equation r 2 − 4r − 5 = 0,

that is (r − 5)(r + 1) = 0, so that r = 5, −1.

Hence the general solution is

an = A 5n + B (−1)n .
 59

We now use the initial conditions

−1 = a0 = A + B.
7 = a1 = 5A − B,

which gives A = 1, B = −2, so the final solution is

an = 5n − 2(−1)n .

b) For
an − 4an−1 − 5an−2 = 5n
we see from part (a) that c 5n is already a solution of the homogeneous equation, so
we try a particular solution pn = c n 5n .

Substituting into the recurrence and dividing by 5n−2 gives

25cn − 20c(n − 1) − 5c(n − 2) = 25

5
which solves to give c = and thus
6
5
pn = n 5n .
6
[Note that the general solution to this equation is therefore
5
an = A 5n + B (−1)n + n 5n .
6
Note also that
5
an = 5n − 2(−1)n + n 5n .
6
is also a particular solution, but it does NOT satisfy the initial conditions a0 =
−1, a1 = 7.]
ii) a) In a word of 20 letters, the letters can be chosen from 26 with repetitions allowed
and order being important in 2620 ways.
b) or words of 20 letters containing exactly 3 vowels, we can select the locations for
the vowels in C(20, 3) ways, then select the 3 vowels in these locations in 53 ways,
and finally select the remaining 17 letters from the 21 consonants in 2117 ways, so
the number of ways is
C(20, 3) 53 1217 .
c) As letters are allowed to be repeated, the subword “MATHS” may appear more
than once, so to avoid double counting we need to use inclusion/exclusion.

If “MATHS” occurs (at least once), then we treat “MATHS” as one letter and there
are 15 other letters arranged in the word.
“MATHS” can occur in C(16, 1) places and the other letters can be chosen in 2615
ways (remembering that letters can be repeated), so we get C(16, 1) 2515 words.

BUT this counts words with 2 occurences of “MATHS” more than once, so we sub-
tract these off.
60

Now we have 2 occurences of “MATHS” which can be in

C(12, 2) places and the other letters can be chosen in 2610 ways, giving C(12, 2) 2610
words.

BUT if we subtract these off, then words with 3 occurences of “MATHS” will be
missing, so we add them back in and, as above, there are C(8, 3) 265 such words.

Finally we have to subtract off the words with 4 occurences of “MATHS” of which
there is 1 word.

So the number of different 20 letter words containing the subword “MATHS” is

C(16, 1) 2515 − C(12, 2) 2610 + C(8, 3) 265 − 1.

iii) a) For any particular A with |A| = 10, there are |P (A)| = 210 = 1024 subsets.
b) The largest element-sum of all subsets of all possible sets A is when
A = {90, 91, 92, · · · , 99}
and the largest element-sum of subsets of this is 945 taking the the whole set as the
subset.
c) The smallest element-sum of all subsets of all possible sets A is 0 for the empty set.
Hence there are 945 + 1 = 946 possible element-sums over all possible subsets of all
possible sets A.

For any particular A there will be (far) less than 946 possible element-sums, but
this A has 1024 > 946 subsets, so by the Pigeon-hole Principle there must be at
least 2 subsets of A having the same element-sum.
iv) The number of ordered outcomes of rolling a die 5 times is 65 , and these are equally likely.

Let xi denote the number shown on the ith roll of the die.
Then we want to count the number of solutions of
x1 + x2 + x3 + x4 + x5 = 10 with 1 ≤ xi ≤ 6 for each i.

Let yi = xi − 1 for each i, so we count the solutions to

y1 + y2 + y3 + y4 + y5 = 5 with 0 ≤ yi ≤ 5 for each i.
Now none of the yi can exceed 5 as their total is 5, so the upper limit on yi is not
necessary and we have to count solutions of
y1 + y2 + y3 + y4 + y5 = 5 with yi ≥ 0 for each i.
This is a standard “dots and lines” problem with
C(5 + 4, 4) = C(9, 4) solutions.
Hence the required probability is
C(9, 4)
= 0.0162 (to 4 d.p.).
65
 61

MATH1081 November 2014 Solutions

1. i) The Venn diagram is given by

C U

24

20

M 13 P
17

Let x be the number of studens in the shaded region. From the Venn diagram

180 = 17 + 20 + 13 + 24 + x ⇒ x = 106

Hence the number of students who like Mars Bars is 106 + 17 + 20 = 143.
ii)
LHS = (A − B) − (A − C) = (A − B) ∩ (A ∩ C c )c Given
= (A − B) ∩ (Ac ∪ C) DeMorgan′ s law
= [(A − B) ∩ Ac )] ∪ [(A − B) ∩ Ac )] ∩ C Distributive law
= [A ∩ B c ∩ Ac ] ∪ [(A − B) ∩ Ac )] ∩ C
= ∅ ∪ (A − B) ∪ C = (A − B) − C c = RHS.

iii) a) From the given identity, we have

tan(A − B)(1 + tan A tan B) = tan A − tan B,

so
tan(A) − tan(B)
tan A tan B − −1
tan(A − B)
Put A = k + 1, B = k then the result follows.
b)
n n
X X tan(k + 1) − tan k
tan k tan(k + 1) = −1
tan 1
k=1 k=1
n n
1 X X
= [ (tan(k + 1) − tan k)] − n
tan 1
k=1 k=1
62

Replacing k + 1 with k in the first sum, we have

n+1 n
1 X X
= [ (tan k − tan k)] − n
tan 1
k=2 k=1

tan(n + 1) − tan 1 tan(n + 1)

= −n= − (n + 1).
tan(1) tan(1)

iv) Since the gcd(44, 126) = 2, which divides 20, we can write the equation as 22x ≡ 10
(mod 63).
Euclid gives, 1 = 7.63 − 22.20 and so 10 = 70.63 − 200.22 so x ≡ −200 (mod 63) ≡ 52
(mod 63).
Hence x ≡ 52, 115 (mod 126).

v) a) f onto means that given any y ∈ Y there is an x ∈ X such that f (x) = y.

b) Suppose y ∈ (f (A))c then since y is onto, there is an x ∈ X such that y = f (x). Now
if x ∈ A then y = f (x) ∈ f (A) which is false, so x ∈ Ac . Hence y = f (x) ∈ f (Ac ).
The result follows.

2. i) a) The Hasse diagram is {w, x, y} {x, y, z}

{x, y}
{w, x, z}

{w} {x} {y, z}

∅
b) The maximal elements are {w, x, y} , {w, x, z} and {x, y, z}.
c) There is no greatest element since there is more than one maximal element.
d) {x} and {w} have no least upper bound. Their common upper bounds are {w, x, y}
and {w, x, z} - neither of which can be called least.

ii) a) It is given that the number of vertices 7. By the handshaking lemma, the number
of edges is 11. By Euler’s formula, the number of regions is therefore 2 + 11 − 7 = 6.
b) A possible diagram is:
 63

Figure 1: A planar graph with vertex degrees 6, 5, 5, 2, 2, 1, 1.

c) There is no Euler path since there are more than two vertices of odd degree.
iii) a) Given a graph with n vertices, construct a table of edges sorted in ascending order
by cost. Kruskal’s algorithm is to choose the first n − 1 = 7 edges that do not form
a cycle. The chosen edges form a minimal spanning tree.

Edge(cost) Chosen
EF(1) Yes
HD(2) Yes
FC(2) Yes
GH(2) Yes
EG(3) Yes
EC(3) No
AG(4) Yes
CD(4) No
CB(5) Yes
..
. No

Table 1: A table for Kruskal’s algorithm. Notice that edge EB could substitute for CB to form a
different minimal spanning tree.

B b
5 b C

2
b b
1 b b
A E F D

4 3 2
b b

G 2 H
b) No, since the shortest path from A to B has cost 7 in the graph, the cost of travelling
from A to B in the Minimal Spanning Tree is 15.
iv) a) There are 429 paths of length 14 from vertex 1 to vertex 1.
64

b) Let e = (1, 2) and f = (2, 1). Then for any even integer n there exists an integer k
such that n = 2k and a path (ef )k from 1 to 1 with 2k = n edges. Hence the (1, 1)
entry is nonzero for even powers of M .
c) The shortest odd path from 1 to 1 has length 1080 + 1 + 1080 = 2161. Hence
n = 2161 is the smallest power.

p q r ∼p → (q →∼ r) r → (p∧ ∼ q)
T T T T F
T T F T T
T F T T T
3. i) T F F T T The second statement implies the first
F T T F F
F T F T T
F F T T F
F F F T T
but not conversely.
ii) a) Let d stand for The Doctor is lost in space
t stand for The Tardis is out of control
c stand for Carla takes charge.
Then the syllogism is
t→d
c → (t∨ ∼ d)
c∨t
d
b) Assinging the truth values d = F, t = F, c = T , then with these values, all the
premises are true but the conclusion is false. Hence the argument is not valid.
iii) Since gcda, b) = 1 there are integers x, y such that ax + by = 1. Multiply both sides by
m to obtain amx + bmy = m. Now clearly a | amx and by assumption a | bm, hence a
is a factor of the left-hand side of the equation and so a | m.
j k l m
iv) Suppose x = x2 + x2 , then since x is the sum of two integers, x is a an integer.
Conversely, suppose x is an integer. We consider the casesjx kis even
l mandj x is k odd.
l m If x
x x 2k 2k
is even, then we wrote x = 2k, for some integer k. Hence 2 + 2 = 2 + 2 =
k
j +k k =
l 2km =j x. Ifk x lis odd,m then we wrote x = 2k + 1, for some integer k. Hence
x x 2k+1 2k+1
2 + 2 = 2 + 2 = k + k + 1 = 2k + 1 = x. The result follows.
v) a) The negation is


∀ M ∈ R+ ∃ x ∈ R+ (x ≥ M ) ∧ (f (x) ≤ 0) .

b) Given any positive real number M , we take x = ⌈M ⌉, then x ≥ M and f (x) =

1 1
sin2 (π⌈M ⌉) − ⌈M ⌉ = − ⌈M ⌉ < 0. Hence by part (a), f is not eventually positive.

4. i) a) The characteristic polynomial

r 2 + 3r − 4
has roots r = 1, r = −4, so the recurrence has general solution

an = A + B(−4)n .
 65

Applying initial conditions, we have

A+B =7 , A − 4B = −3 ;

solving gives A = 5, B = 2 and hence

an = 5 + 2(−4)n .

b) Guess a particular solution pn = cn. Substituting an = pn into the recurrence,

cn + 3c(n − 1) − 4c(n − 2) = 10 .

Solving gives c = 2, so a particular solution is an = 2n.

ii) a) By the “dots and lines” method, the number of solutions is C(83, 5).
b) Place 78 dots into 6 categories by first putting one dot in each category, then dis-
tributing 36 pairs of dots across the categories. This is equivalent to arranging 36
objects and 5 lines in a row. The number of solutions is C(41, 5).
c) Let Sk be the set of solutions of the equation in which xk ≥ 30. To count S1 we
reserve 30 dots for section 1, then distribute 48 dots into 6 sections; the number of
solutions is C(53, 5); and likewise for all Sk . To count S1 ∩ S2 we reserve 30 dots for
each of the first two sections, then distribute 18 dots into 6 sections; the number of
solutions is C(23, 5); and likewise for all Sk ∩ Sl . Any intersection of three or more
sets Sk must have x1 + · · · + x6 ≥ 90, which is impossible. So by inclusion/exclusion,
the total number of solutions is

6C(53, 5) − C(6, 2)C(23, 5) .

iii) Let U be the set of all 52–letter words in which every letter is used twice. A word in
U which includes the subword UNSW can be regarded as a string of 49 “objects”: 22
letters occurring twice each, the letters U, N, S, W occurring once each, and the single
“object” UNSW. Counting the arrangements is a “WOOLLOOMOOLOO” problem,
and the number of possibilities is 49!/(2!)22 .However, this procedure will have counted
twice any word which contains UNSW twice. By a similar argument, the number of such
words is 46!/(2!)23 . Therefore the required number of words is

49! 46!
− .
222 223

iv) a) Since the number of 2s in the string is k and the total of the digits is n, the number
of 1s must be n − 2k and the total number of digits is n − k. To choose such a string
we have to choose which k of the n − k places will be occupied by 2s: in choosing
places, repetition is impossible and order is not important, so the number of strings
is C(n − k, k).
b) If n ≥ 2 then a string of the required type with sum n must consist of •a 1 followed
by a string of the same type with sum n − 1: there are an−1 such strings; or •a 2
followed by a string of the same type with sum n − 2: there are an−2 such strings.
Therefore an = an−1 + an−2 . If n = 1 the only possible string is 1; if n = 2 there
are two possible strings, 2 and 11. Therefore a1 = 1 and a2 = 2.
66

c) The sequence an satisfies the Fibonacci recurrence, with initial values a1 = F2 and
a2 = F3 . Clearly an = Fn+1 . On the other hand, if a string with sum n contains
k digits 2, then 0 ≤ k ≤ ⌊n/2⌋; using the result of (a), the total number of strings
with sum n is
⌊n/2⌋
X
C(n − k, k) .
k=0

But this sum is by definition an ; and we have also shown that an = Fn+1 ; and this
completes the proof.
 67

MATH1081 JUNE 2015 Solutions

1. i) a) |A × B| = |A| · |B| = 4 · 3 = 12.
b) |A ∪ B| = |{m, a, t, h, 1, 0, 8}| = 7 so |P (A ∪ B)| = 2|A∪B| = 27 = 128.
c) The only element in common between P (A) and P (B) is the empty set. So |P (A) −
P (B)| = |P (A)| − 1 = 2|A| − 1 = 24 − 1 = 15.
ii)

(A ∩ (B ∪ Ac )) ∪ (A ∪ B c )c
= (A ∩ (B ∪ Ac )) ∪ (Ac ∩ (B c )c ) De Morgan’s law
c c
= (A ∩ (B ∪ A )) ∪ (A ∩ B) double complement
c c
= ((A ∩ B) ∪ (A ∩ A )) ∪ (A ∩ B) distributive law
c
= ((A ∩ B) ∪ ∅) ∪ (A ∩ B) complement law
c
= (A ∩ B) ∪ (A ∩ B) identity law
c
= (A ∪ A ) ∩ B distributive law
=U ∩B complement law
=B identity law

iii) a)
4 k2 − 4 (k − 2)(k + 2)
1− = = .
k2 k2 k2
b)
n   n
Y 4 Y (k − 2)(k + 2)
1− 2 =
k k2
k=3 k=3
n n n
Y Y Y 1
= (k − 2) (k + 2)
k2
k=3 k=3 k=3
n−2 n+2 n
Y Y Y 1
= k k
k2
k=1 k=5 k=3
n
! n
! n
1·2 Y (n + 1)(n + 2) Y Y 1
= k k
n(n − 1) 3·4 k2
k=3 k=3 k=3
(n + 1)(n + 2)
= .
6n(n − 1)

iv) a) For any z ∈ C we have |z − 1| = |z − 1|, which means that z ∼ z. Thus ∼ is reflexive.
Suppose that z ∼ w. Then |z − 1| = |w − 1|, which implies that |w − 1| = |z − 1|,
i.e., w ∼ z. Thus ∼ is symmetric.
Suppose that z ∼ w and w ∼ u. Then |z − 1| = |w − 1| and |w − 1| = |u − 1|. We
conclude that |z − 1| = |u − 1|, i.e., z ∼ u. Thus ∼ is transitive.
b) The equivalence class of 2i is the set of z ∈ C such that z ∼ 2i, √ i.e., those z such
that |z − 1| = |2i − 1|, i.e., a circle centred at (1, 0) with radius 5.
v) a) Let A be a subset of X. Since f is injective, for each element y ∈ f (A) there is a
unique x ∈ A such that f (x) = y. Thus |f (A)| = |A|.
68

b) Applying (a) to A = X, we have |f (X)| = |X| = |Y |. But f (X) is a subset of Y , so

we must have f (X) = Y , i.e., f is surjective. Since we assumed that f is injective,
we conclude that f is bijective.

2. i) First note that as

2015 = 183 × 11 + 2
we have
2015 ≡ 2 mod 11.
Secondly
210 ≡ 1 mod 11
as can be seen by calculating:

25 = 32 ≡ 10 mod 11
so
210 ≡ 102 ≡ 1 mod 11.
Finally note that
1082 = 108 × 10 + 2
so

20151082 ≡ 21082 ≡ 2108×10+2 ≡ 2108×10 22 ≡ (210 )108 × 4 ≡ 1108 × 4 ≡ 4 mod 11.

ii) a) By the Euclidean algorithm

342 = 3 × 105 + 27
105 = 3 × 27 + 24
27 = 24 + 3
24 = 8 × 3 so the g.c.d is 3.

b) Using the identities from the Euclidean algorithm in part a) we see that

3 = 27 − 24
= 27 − 105 + 3 × 27
= 4 × 27 − 105
= 4 × (342 − 3 × 105) − 105
= 342 × 4 − 105 × 13.

Therefore
9 = 342 × (3 × 4) + 105 × (−3 × 39)
and therefore x = −39 and y = 12 work.

c) α) One solution is given by part b) namely x = −39. However there 2 more solutions,
namely
−39 + (342)/3 = 75 and − 39 + 2 × (342)/3 = 189.
β) There is no solution as the g.c.d. of 105 and 342 does not divide 8.
 69

iii) a) For there to be an Euler path there are at most two vertices of odd degree. But
there are more than 2 vertices of odd degree, so there is no Euler path.

b) Here is one way of drawing it (there are several):

Fb
Eb

Ab
I
b

b b

B C

b b

H D

iv) a) The total degree for such a graph would be 19 = 4 + 4 + 3 + 3 + 3 + 2 which is

impossible as then 19 has to be equal to 2e where e is the number of edges. (So in fact
no graph with these degrees exists, simple or otherwise).

b) Here there is a simple graph with the specified degree which can be found by trial
and error (or systematic argument). It is:
70
b
D

A b b
C

b
B

c) If such a simple graph existed, then three of the vertices connect to the other 4. So
each vertex has degree at least 3. But the graph also has a vertex of degree 1, which is
a contradiction.

v) The key to this question is the following fact about Trees:

A tree T with n vertices has n − 1 edges.
By definition of the total degree we have
X
n= d(v)
v∈V (T )

so by the Hand Shake Lemma

1 X 1 n−1
d(v) = (2(n − 1)) = 2 < 2.
n n n
v∈V (T )

vi) Applying Dijkstra’s Algorithm:

We start with a tree T with one vertex A.
Both E and F are joined to A by edges which give the shortest distance (i.e. smallest
weight path) to A.
So we obtain a new Tree T1 with vertices, A, E and F and edges {A, B} and {A, F }.
Now the vertex B is connected to E by an edge and the total weight of the path from A
to E and then E to B is 3 which is the smallest possible weight. Likewise the path from
A to F and then to D is 6 which is the smallest possible weight. So we obtain a new tree
T2 with vertices A, E, F, B, D and edges {A, B}, {A, F }, {E, B}, {F, D}. Finally adding
the edge {B, C} gives a new Tree T3 which contains all the vertices of the graph. It
looks like this:
 71

Ab

1
B b b
C

2 1 5

D 1
b b
F
E

3. i)
q∨ ∼ (p → q) ≡ q ∨ (p∧ ∼ q)
≡ (q ∨ p) ∧ (q∨ ∼ q)
≡ (q ∨ p) ∧ T
≡ q ∨ p.
ii) a) Converse:
If n ≡ 2 mod 4 then n2 is even.
The converse is a true statement. Indeed, if n ≡ 2 mod 4 then

n = 2 + 4k for some k ∈ Z.

Hence
n2 = (2 + 4k)2 = 4(1 + 2k)2 .
Thus n2 is even.
OR:
Since n ≡ 2 mod 4 we have n2 ≡ 22 mod 4 ≡ 0 mod 4. Hence n2 is a multiple of 4
and therefore is even.
b) Contrapositive:
If n 6≡ 2 mod 4 then n2 is odd.
The contrapositive is not true. Counter-example: Consider n = 4. Then n ≡ 0 mod
4. But n2 = 16 is even.
NOTE: Since the given statement is logical equivalent to the contrapositive, it is
possible to give a counter-example to the given statement to prove that the contra-
positive is wrong. Consider n2 = 16. Then n = 4 (assuming that n > 0). Hence
n 6≡ 2 mod 4.
72

iii) For n = 1:
LHS = 1 + x = RHS.
The statement is true.
Suppose the statement is true for some positive integer k, i.e.,

(1 + x)k ≥ 1 + kx.

Since x ≥ −1 so that 1 + x ≥ 0 it follows that

(1 + x)k+1 = (1 + x)(1 + x)k ≥ (1 + x)(1 + kx) = 1 + (k + 1)x + kx2 ≥ 1 + (k + 1)x.

Thus the statement is true for n = k + 1.

By induction, the statement is true for all n ≥ 1.
Premises Conclusion Reason (not required)
p
r∨ ∼ p r Disjunctive syllogism
iv) r
(∼ p∨ ∼ q) →∼ r ∼ (∼ p∨ ∼ q) Modus tollens
≡p∧q
p∧q q Simplification
Thus, the argument is valid.
v) a)
∃x∀y∃z(z > y) ∧ (z ≤ x).
b) Statement (*) is true. Indeed, for any real number x, by choosing y = x + 1 we have

z > y → z > x,

for any real number z.

4. i) a) We make 12 choices of letters for the word from 26 letters in the alphabet.
This can be done in
2612 ways.
b) Choose the location for the one “X” in C(12, 1) = 12 ways, then
choose the other 11 letters from 25 non-“X”s in 2511 ways.
Hence the probability of getting exactly one “X” is

12 × 2511
.
2612
c) Let A denote the event that the word does NOT contain an “X”
let B denote the event that the word does NOT contain a “Y” and
let C denote the event that the word does NOT contain a “Z”. Then we want

|Ac ∩ B c ∩ C c | = |U | − |A ∪ B ∪ C|
= |U | − |A| − |B| − |C| + |A ∩ B| + |A ∩ C| + |B ∩ C|
− |A ∩ B ∩ C|
12
= 26 − 3 × 2512 + 3 × 2412 − 2312 .
 73

by inclusion/exclusion.
Here for example |A| = 2512 as 12 letters are chosen from 25,
|A ∩ B| = 2412 as 12 letters are chosen from 24,
and similar for the other terms.
ii) a) The recurrence an − 3an−1 + 2an−2 = 0 has characteristic equation

r 2 − 3r + 2 = 0,

which gives
r = 1 or 2
Hence the general solution is
an = A + B2n .
b) For an − 3an−1 + 2an−2 = 2n , since we have from part (a) the solution of the
homogeneous case is hn = A + B2n and 2n is a special case of this, then we try a
particular solution of the form
pn = cn2n .
Substituting this into the equation gives

cn2n − 3c(n − 1)2n−1 + 2c(n − 2)2n−2 = 2n .

Now dividing through by 2n−2 gives

4cn − 6c(n − 1) + 2c(n − 2) = 4

which gives c = 2. Thus our particular solution is

pn = 2n2n = n2n+1 .

iii) Give each person 1 bar, then distribute the remaining 7 bars among 3 people. This is a
7 dots, 3 − 1 = 2 line distribution so the number of ways this can be done is

C(7 + 2, 2) = C(9, 2) = 36 ways.

1
iv) Partition the unit square as follows: draw a set of horizontal lines n apart, and a set of
vertical lines n1 apart.
This gives a total of n2 smaller squares of side length n1 each.