COMP9020 Assignment 1 2023 Term 2
Objectives and Outcomes
The purpose of this assignment is to build your mathematical maturity in the areas of Number Theory, Sets,
Equivalence Relations, Functions, and Graph Theory. Most questions are presented at a highly abstract level
so that the consequences are very general, and can be applied in a variety of situations: not just later on in the
course, but also beyond. The specific motivation for each problem can be summarised as follows:
Problem 1: This question works through a proof of Bézout’s Identity: the fact that the gcd of x and y can be
written as an integer linear combination of x and y. To do this we work through an approach common
throughout the course: Introducing a new definition based on known concepts; Explore that definition
with some examples; Prove results about the definition.
Problem 2: This question shows how we can use Bézout’s Identity (from Q1) to find multiplicative inverses
in modular arithmetic – that is, how to “divide” when working modulo y. In order to “divide” by x
(when working modulo y), we can instead multiply by a number w where wx =(y) 1. We saw this
with Quiz 1, T6: because 17× 11 =(186) 1, we can solve 17y =(186) 5 by multiplying both sides by 11:
55 =(186) 11(17y) =(186) y. We also saw a similar idea in the lectures about matrices.
Problem 3: We will revisit this result again when looking at algorithmic analysis. It is particularly useful for
analyzing the Faster Euclidean Algorithm covered in Week 2.
Problem 4: This question asks you to prove or disprove set equalities – specifically equalities involving
languages (so the laws of set operations do not apply). This question demonstrates another common
approach used in this course: requiring you to first decide whether the result is correct or not (assessing
understanding) and then requiring you to justify your stance (assessing ability).
Problem 5: This question demonstrates a close connection between several different topics already covered
in the course: functions, sets, and languages. This connection is more than coincidental – we will revisit
it again later in the course when we cover Boolean Algebras.
Problem 6: The use of exponential notation for describing sets of functions extends beyond comparing car-
dinalities. This question demonstrates the set-theoretical analogue of the rule abc = (ab)c. This has
applications in computer science as it demonstrates how functions of two inputs can be constructed
from functions of just a single input. This process is known as Currying.
Problem 7: This question shows another, very useful, characterization of equivalence relations, connecting
them with functions. This goes along with the characterization in terms of partitions (i.e. a connection
with sets) described in lectures. Most of the examples of equivalence relations given in lectures and
quizzes (e.g. Quiz 4, M1) fit this characterization; and we use the result again in Problem 8.
Problem 8: This question shows that, in certain circumstances, it is possible to “extend” addition and multi-
plication to equivalence classes. A variation of this result (for a different equivalence relation) establishes
the facts about how addtion and multiplication interact with =n stated in lectures. This particular re-
sult shows a connection between the matrix representation of relations and the adjacency matrix of their
graphical representation (the former corresponding to a matrix of equivalence classes). We will see the
semiring E again when we cover Boolean Logic.
Problem 9: The aim of this question is to model a concrete (“real-world”) problem abstractly using Graph
Theory. An abstract model lets us: identify the important aspects of a problem and ignore the extra-
neous; identify connections with other, seemingly unrelated problems; and make use of other, more
general, tools and results to solve the specific problem. We will revisit this problem in Assignment 2,
where we will model it with Propositional Logic.
After completing this assignment, you will:
Be able to make rigorous arguments about the foundational structures used in discrete mathematics
[All problems]
Be able to create and reason about abstract models of concrete (“real-world”) problems and objects
[Problem 9]
Understand several deeper connections between different topics of the course [Problems 1, 3, 5, 7, 8]
1
Due: Friday, 14th July, 12:00 (AEDST)
Submission is through inspera. Prose should be typed, not handwritten.
Discussion of assignment material with others is permitted, but the work submitted must be your
own in line with the University’s plagiarism policy.
Problem 1 (16 marks)
For x, y ∈ Z we define the set:
Sx,y = {mx + ny : m, n ∈ Z}.
(a) Give four elements of S6,9. 2 marks
(b) Give four elements of S10,?16. 2 marks
For the following questions, let d = gcd(x, y) and z be the smallest positive number in Sx,y, or 0 if there
are no positive numbers in Sx,y.
(c) (i) Show that Sx,y ? {n : n ∈ Z and d|n}. 4 marks
(ii) Show that d ≤ z. 2 marks
(d) (i) Show that z|x and z|y (Hint: consider (x % z) and (y % z)). 4 marks
(ii) Show that z ≤ d. 2 marks
Remark
The result that there exists m, n ∈ Z such that mx + ny = gcd(x, y) is known as Bézout’s Identity.
Problem 2 (12 marks)
For all x, y ∈ Z with y > 1:
(a) Prove that if gcd(x, y) = 1 then there is at least one w ∈ [0, y) ∩N such that wx =(y) 1.
(Hint: Use Bézout’s identity) 4 marks
(b) Prove that if gcd(x, y) = 1 and y|kx then y|k. 4 marks
(c) Prove that if gcd(x, y) = 1 then there is at most one w ∈ [0, y) ∩N such that wx =(y) 1. 4 marks
Problem 3 (4 marks)
Prove that for all m, n ∈N>0 with n ≤ m:
3
2
(
n + (m % n)
)
< m + n. 4 marks
2
Problem 4 (12 marks)
Let Σ = {0, 1}. For each of the following, prove that the result holds for all sets X, Y, Z ? Σ?, or provide a
counterexample to disprove:
(a) (X ∪Y)? = X? ∪Y? 4 marks
(b) (X ∩Y)? = X? ∩Y? 4 marks
(c) X(Y ∪ Z) = (XY) ∪ (XZ) 4 marks
Problem 5 (12 marks)
(a) List all possible functions f : {a, b, c} → {0, 1}, that is, all elements of {0, 1}{a,b,c}. 4 marks
(b) Describe a connection between your answer for (a) and Pow({a, b, c}). 4 marks
(c) Describe a connection between your answer for (a) and {w ∈ {0, 1}? : length(w) = 3}. 4 marks
Problem 6 (4 marks)
Show that for any sets A, B, C there is a bijection between A(B×C) and (AB)C. 4 marks
Problem 7 (12 marks)
Let S be a set.
(a) Show that for any set T and any function f : S → T, the relation R f ? S× S, defined as:
(s, s′) ∈ R f if and only if f (s) = f (s′)
is an equivalence relation. 6 marks
(b) Show that if R ? S× S is an equivalence relation, then there exists a set T and a function fR : S → T
such that:
(s, s′) ∈ R if and only if fR(s) = fR(s′)
6 marks
Problem 8 (16 marks)
Let B = {0, 1} and consider the function f : N→ B given by
f (n) =
{
1 if n > 0,
0 otherwise.
(a) Show that for all a, b ∈N:
(i) f (a + b) = max{ f (a), f (b)} 2 marks
(ii) f (ab) = min{ f (a), f (b)} 2 marks
3
From Problem 7, we know that R f ?N×N, the relation given by:
(m, n) ∈ R f if and only if f (m) = f (n)
is an equivalence relation. Let E ? Pow(N) be the set of equivalence classes of R f , and for n ∈ N, let
[n] ∈ E denote the equivalence class of n.
We would like to define binary operations, ? and ?, on E as follows:
[x] ? [y] := [x + y]
[x] ? [y] := [xy].
The difficulty is that the operands [x] and [y] can have multiple representations (e.g. if z ∈ [x] then
[x] = [z]), and so it is not clear that such a definition makes sense: if we take a different representation of
the operands, do we still end up with the same result? For example, suppose [1] = [2]. Then we would
want [1]? [1] = [2]? [2], but with the proposed definition above, we would have [1]? [1] = [2], and
[2]? [2] = [4], and it is by no means clear that [2] = [4].
Our next step is to show that such a definition makes sense.
(b) Define relations ?,? ? E2 ×E as follows:
((X, Y), Z) ∈ ? if and only if there is x, y ∈N such that X = [x], Y = [y] and Z = [x + y]
((X, Y), Z) ∈ ? if and only if there is x, y ∈N such that X = [x], Y = [y] and Z = [xy]
(i) Show that ? is a function. 3 marks
(ii) Show that ? is a function. 3 marks
Part (b) shows that the informal definition of ? and ? given earlier is well-defined, so from now we will
view ? and ? as binary operations on E, that is ?,? : E×E→ E.
(c) Show that for all A, B, C ∈ E:
(i) A? [1] = A 2 marks
(ii) A? B = B? A 2 marks
(iii) A? (B? C) = (A? B)? (A? C) 2 marks
Remark
Objects that have a concept of “addition” (?) and “multiplication” (?) where:
addition and multiplication are associative,
both operations have identities (see (c)(i)),
addition is commutative (see (c)(ii)), and
multiplication distributes over addition (see (c)(iii))
are known as semirings. We have already seen a number of semirings in this course:
The natural numbers with usual addition and multiplication,
Integers modulo n with addition and multiplication modulo n,
Subsets of a set X with union and intersection,
Languages with union and concatenation,
Binary relations with union and relational composition (see Assignment 1),
Matrices with matrix addition and matrix multiplication.
4
Problem 9 (12 marks)
Eight houses are lined up on a street, with four on each side of the road as shown:
Each house wants to set up its own wi-fi network, but the wireless networks of neighbouring houses – that
is, houses that are either next to each other (ignoring trees) or over the road from one another (directly
opposite) – can interfere, and must therefore be on different channels. Houses that are sufficiently far
away may use the same wi-fi channel. Your goal is to find the minimum number of different channels the
neighbourhood requires.
(a) Model this as a graph problem. Remember to:
(i) Clearly define the vertices and edges of your graph. 4 marks
(ii) State the associated graph problem that you need to solve. 2 marks
(b) Give the solution to the graph problem corresponding to this scenario; and determine the minimum
number of wi-fi channels required for the neighbourhood? 2 marks
(c) How do your answers to (a) and (b) change if a house’s wireless network can also interfere with those
of the houses to the left and right of the house over the road? 4 marks
Advice on how to do the assignment
Collaboration is encouraged, but all submitted work must be done individually without consulting some-
one else’s solutions in accordance with the University’s “Academic Dishonesty and Plagiarism” policies.
Assignments are to be submitted in inspera.
When giving answers to questions, we always would like you to prove/explain/motivate your an-
swers. You are being assessed on your understanding and ability.
Be careful with giving multiple or alternative answers. If you give multiple answers, then we will
give you marks only for your worst answer, as this indicates how well you understood the question.
Some of the questions are very easy (with the help of external resources). You may make use of
external material provided it is properly referenced1 – however, answers that depend too heavily on
external resources may not receive full marks if you have not adequately demonstrated ability/un-
derstanding.
Questions have been given an indicative difficulty level:
Pass Credit Distinction High distinction
This should be taken as a guide only. Partial marks are available in all questions, and achievable by
students of all abilities.
1Proper referencing means sufficient information for a marker to access the material. Results from the lectures or textbook can be
used without proof, but should still be referenced.