School of Mathematics and Statistics MAST30012 Discrete Mathematics, Assignment 2, Semester 2, 2020 Student Name Student Number Tutor’s Name Practice Class Day/Time Submission deadline is 23:59pm Monday 21 September. Check Canvas for details of the late submission policy. Submit your assignment online using Canvas as a single pdf including this cover page (more details to follow). • Full working must be shown in your solutions. • Marks will be deducted for incomplete working, insufficient justification or incorrect notation. Q1: Give a bijective proof of the following identity! k≥0 " n 2k # = 2n−1 using the following steps: (a) Use subsets of the set [n] to define a set ΩL representing the left-hand side. (b) Define a set ΩR representing the right-hand side as a certain set of tuples with entries from the set {0, 1}. (c) Define a bijective function Γ : ΩR → ΩL. (Note the direction of the function must be right-to- left). (d) Show that your function in (c) is well defined. (There is no need to prove it is a bijection). Your definitions in (a) and (b) must use the specification form of a set definition (see week 1 lecture notes). Q2: Select n2 + 1 distinct points in (or on the boundary of) the unit square. Prove that at least two points are no more than a distance √ 2/n apart. End of Assignment.
欢迎咨询51作业君