辅导MAST30012、Java,c++程序辅导
- 首页 >> CS School of Mathematics and Statistics
MAST30012 Discrete Mathematics
Semester 2, 2022
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.
MAST30012 Discrete Mathematics
Semester 2, 2022
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.