The University of Melbourne — School of Mathematics and Statistics
MAST30012 Discrete Mathematics — Semester 2, 2021
Practice Class 5: Parity and Lattice Paths – Answers
Q1: (a) Draw a picture and consider #(subintervals with di↵erent labelling at each endpoint).
(b) Deleting the rightmost string of 0’s reduces by one the number of (1, 0)–subintervals.
Q2: (a) Suppose the top left corner is white. Then the bottom right corner is also white.
After their removal there are thus 32 black and 30 white squares left.
(b) A 2⇥ 1 rectangular tile must always cover 1 white and 1 black square.
(c) Now consider what happens in a tiling with 2⇥ 1 rectangles.
Q3: (a) Consider a row (column) with k black squares the change in the number of black
squares as colours are reversed.
(b) Now use parity to complete the argument.
Q4: Colour the 5⇥ 5 square board as for a chess board and consider the number of white and
black squares
Q5: (a) Dm,n = Dm�1,n +Dm,n�1 +Dm�1,n�1, D0,0 = 1, Dm,n = 0 m,n < 0. (b) The grid count for Dm,n. By symmetry Dm,n = Dn,m (c) Repeat with ‘boundary conditions’ B0,0 = 1, B0,n = 1, Bm,n = 0 if m > n
(d) Bm,n = Dm,n �Dn+1,m�1.
(e) Proof required.
Q6: (a) The paths in B3
1
(3), B1
2
(3) and B2
2
(3) are
(b) Bhn(c) = B
h+1
n�1(c) + B
h�1
n (c), B
�1
n (c) = 0, B
c+1
n (c) = 0, B
0
0
(c) = 1.
Conjecture |B0n(3)| = F2n�1, n � 1.
(c) vm = T
m
v0 = T · Tm�1v0 = Tvm�1.
v1 =
✓
0 1
1 1
◆✓
1
2
◆
=
✓
2
3
◆
, v2 =
✓
0 1
1 1
◆✓
2
3
◆
=
✓
3
5
◆
, v3 =
✓
0 1
1 1
◆✓
3
5
◆
=
✓
5
8
◆
,
v4 =
✓
0 1
1 1
◆✓
5
8
◆
=
✓
8
13
◆
, v5 =
✓
0 1
1 1
◆✓
8
13
◆
=
✓
13
21
◆
, v6 =
✓
0 1
1 1
◆✓
13
21
◆
=
✓
21
34
◆
Conjecture :
vm =
✓
xm
ym
◆
then xm = ym�1 and xm =
8
>><
>>:
���B0m+3
2
(3)
��� if m is odd
���B3m
2
(3)
��� if m is even
(d) The eigenvalues �1 and �2 of the matrix T are �1 =
1
2
(1 +
p
5), �2 =
1
2
(1�
p
5).
With this we can then show that the entries of Tm are Fibonacci numbers.