CS计算机代考程序代写 discrete mathematics The University of Melbourne — School of Mathematics and Statistics

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.