The University of Sydney
School of Mathematics and Statistics
Assignment 1
MATH1004: Discrete Mathematics Semester 2, 2022
Lecturer: Oded Yacobi
This individual assignment is due by 11:59pm Thursday 25 August 2022, via
Canvas. Late assignments will receive a penalty of 5% per day until the closing date.
A single PDF copy of your answers must be uploaded in the Learning Management
System (Canvas) at https://canvas.sydney.edu.au/courses/44703. Please sub-
mit only one PDF document (scan or convert other formats). It should include your
SID, your tutorial time, day, room and Tutor’s name. Please note: Canvas does NOT
send an email digital receipt. We strongly recommend downloading your submis-
sion to check it. What you see is exactly how the marker will see your assignment.
Submissions can be overwritten until the due date. To ensure compliance with our
anonymous marking obligations, please do not under any circumstances include your
name in any area of your assignment; only your SID should be present. The School
of Mathematics and Statistics encourages some collaboration between students when
working on problems, but students must write up and submit their own version of the
solutions. If you have technical difficulties with your submission, see the University
of Sydney Canvas Guide, available from the Help section of Canvas.
This assignment is worth 5% of your final assessment for this course. Your answers should be
well written, neat, thoughtful, mathematically concise, and a pleasure to read. Please cite any
resources used and show all working. Present your arguments clearly using words of explanation
and diagrams where relevant. After all, mathematics is about communicating your ideas. This
is a worthwhile skill which takes time and effort to master. The marker will give you feedback
and allocate an overall mark to your assignment using the criteria on this assignment’s canvas
page.
Copyright ? 2022 The University of Sydney 1
1. Suppose you begin on a first rung of a ladder. A ladder path is a sequence of steps on
the ladder where each step is either up one rung or down one rung, you always remain
on the ladder, and you end back on the first rung. Assume the ladder is tall enough so
that you can never step off the top. For example, there is only one ladder path with two
steps, given by taking one step up and then one step down.
(a) Make a list of all the ladder paths with n steps, where n ∈ {3, 4, 5, 6}.
(b) Let n ≥ 1. Write down a correspondence that relates the ladder paths with 2n
steps to Catalan paths from (0, 0) to (n, n). More precisely, let Ln be the set of
ladder paths with 2n steps, and let Cn be the set of Catalan paths from (0, 0) to
(n, n). Construct a bijection f : Ln → Cn. (You don’t have to prove that it is a
bijection.)
2. (a) Find explicit bijections, and use the horizontal line tests to prove that they are
indeed bijections.
(i) f : (a, b) → (c, d), where a, b, c, d are real numbers such that a < b and
c < d.
(ii) g : (0, 1)→ (1,∞).
(b) For a set X, let
(
X
k
)
denote the set of subsets of X of cardinality k. Given n ≥ 1
we define three sets of cardinality n: Xn = {1, . . . , n}, X ′n = {1′, . . . , n′} and
X ′′n = {1′′, . . . , n′′}. For n > 3 construct a bijection