Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MAST30012 Discrete Mathematics
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.