Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MAST30012 Discrete Mathematics Assignment 2 Due 5pm Friday September 23 Student Name Student Number Tutor’s Name Practice Class Day/Time Submit your assignment online in Gradescope. Please attach this cover sheet to your assignment or use a blank sheet of paper as the first page of your assignment with Student Name, Student Number, Tutor’s Name, Practice Class Day/Time clearly stated. • Late submission will not be accepted unless accompanied by a medical certificate (or a similar special consideration). If there are extenuating circumstances you need to contact your lecturer, preferably prior to the submission deadline. Medical certificates are usually required. • You can handwrite or typeset your assignment. If handwriting, please make sure your pho- tos/scan are clearly legible. • Full working must be shown in your solutions. • Marks will be deducted for incomplete working, insufficient justification or incorrect notation. • Unless otherwise stated, proofs of identities etc. must use combinatorial arguments. • There are 4 questions worth a total of 40 marks. Q1: (10 marks) (a) The game of Sim is played as follows. n dots are drawn on a piece of paper, and lines are drawn joining each pair of dots. Two players take turns colouring an uncoloured line (one red, the other blue). The first player to colour a triangle (the three lines joining three dots) in their own colour is the loser. If all lines are coloured with no single-colour triangle, the game is a draw. i. What is the largest number n for which Sim can end in a draw? (You may use results from lectures, but you must still clearly explain your answer.) ii. Three-player Sim works in the same way, but with three players (using colours red, blue and green). What is the largest number n for which three-player Sim can end in a draw (i.e. no one loses)? (b) Prove that the Ramsey number R(3, 6) ≤ 19. You may use results from lectures, including the other Ramsey numbers R(a, b) with a < 3 or b < 6. (Note that in fact R(3, 6) < 19 but do not attempt to prove this.) (c) Prove that the generalised Ramsey number R(2, a, b) = R(a, b). Q2: (14 marks) Recall that a binomial path is a lattice path which starts at the origin (0, 0) and takes steps from S = {(1, 0), (0, 1)} = {E,N}. A 2-coloured binomial path is one for which there are two types of E steps, red and blue, which we denote as Er and Eb (but still only one type of N step). For example, there are two binomial paths which end at (1, 1), namely EN and NE, but there are four 2-coloured paths, namely ErN, EbN, NEr and NEb. Let Ji,j be the number of 2-coloured binomial paths ending at (i, j). (a) Copy the following grid, where the bottom left corner represents the origin (0, 0). At each point (i, j), write down the number Ji,j. (b) Find a formula for the number Ji,j of 2-coloured binomial paths ending at (i, j). (c) Repeat part (a) but now for 2-coloured ballot paths, where paths may not step below the main diagonal. (d) Let T hm be the set of 2-coloured ballot paths which end at (m,m+ h). Write down a recurrence for |T hm|. Don’t forget to include initial / boundary conditions. (e) The formula you found in (b) generalises to 2-coloured ballot paths, using the counts |Bhm| for regular ballot paths, in an obvious way (if it is not obvious, check your answer to (b) again). Nevertheless there is also a way to compute |T hm| using the same kind of reflection principle that we used to count regular ballot paths. Explain this reflection principle, and use it to write down an expression for |T hm| in terms of two different Ji,j. Q3: (10 marks) Consider the recurrence relation an+3 = 3an+1 − 2an with a0 = 1, a1 = 1, a2 = 3. (a) Calculate an for n ≤ 6. (b) Prove that the generating function A(x) = ∑ n≥0 anx n = 1 + x (1− x)2(1 + 2x) . (c) Use a partial fraction expansion of A(x) to find an explicit expression for an. Q4: (6 marks) We have seen that the Fibonacci numbers Fn count many different combinatorial objects. For example, Fn+1 is the number of ways to tile an n-board with monomers and dimers. (a) Use a bijection with monomer-dimer tilings to show that the number of subsets of {1, 2, . . . , n} with no consecutive numbers (including the empty set) is Fn+2. (b) Use your answer to (a) to show that the number of subsets of {1, 2, . . . , n} with no consecutive numbers (including the empty set), where we also regard n and 1 as consecutive, is Fn−1+Fn+1.