School of Mathematics and Statistics
MAST30012 Discrete Mathematics 2021
Assignment 2 – Solutions
Q1: (a) This is true. Place the numbers into n pigeonholes as (2k−1, 2k), k = 1, . . . , n.
Thus each pair of numbers have greatest common divisor 1. Since we select
n+1 numbers, by the PHP at least one pigeonhole contains two numbers which
then have greatest common divisor 1.
(b) This is not true. Counterexamples include choosing 1, 3, 4 from {1, 2, 3, 4}
or choosing 1, 4, 5, 6 from {1, 2, 3, 4, 5, 6} (of course one counterexample is
enough).
(c) This is true. Every number ai ∈ {1, 2, 3, . . . , 2n} can be expressed uniquely as
ai = 2
kbi, for some integer k and odd integer bi. There are n odd integers in
{1, 2, 3, . . . , 2n} which form our pigeonholes. Since we select n + 1 numbers,
by the PHP at least one pigeonhole contains two numbers, say, a1 = 2
jbi and
a2 = 2
kbi. If j > k, then a1/a2 = 2
j−k > 1 and so a2 divides a1. Similarly, if
k > j, then a2/a1 = 2
k−j > 1 and so a1 divides a2. In any case there must be
a pair of integers such that one divides the other.
Q2: (a) Consider two cases:
Case 1. All points have the same label (either A or B). In this case there are
no neighbouring points labelled either AB or BA. Zero is an even number so
the parity is even.
Case 2. Some points are labelled A some B. At least one pair of neighbouring
points are labelled BA. Take such a pair and remove the arc connecting them.
This reduces the number of neighbouring points labelled either AB or BA
by one. The labelling of the remaining points is a Sperner labelling on an
interval. Hence by Sperner’s lemma for an interval there is an odd number
of neighbouring points labelled either AB or BA. Hence the original labelled
circle had an even number of neighbouring points labelled either AB or BA.
In either case the number of neighbouring points labelled either AB or BA is
even.
Alternative proof. Consider adding a single new point labelled A or B.
Repeat arguments from lectures to show change in the number of neighbouring
points labelled either AB or BA is even. Any configuration can be obtained by
adding labelled points one at a time. We start with a single point labelled A
or B, which can be viewed as an AA or BB interval. In either case there are
no neighbouring points labelled either AB or BA and adding new points does
not change the parity. Hence the total number of neighbouring points labelled
either AB or BA is even.
(b) Make use of the floor plan lemma: In a floor plan with all rooms having 0, 1
or 2 doors, the parity of the number of rooms with 1 door equals the parity of
the number of outside doors.
Here the segments AB (or BA) are considered as doors.
The triangle labelled ABC has one door. Any other triangle has either 0 or 2
doors (show this by drawing the labelled triangles).
Hence the floor plan lemma applies to this case and the sought after result
follows.
Q3: (a) Take the derivative on both sides of the given generating function:
n(1 + x)n−1 =
d
dx
(1 + x)n =
d
dx
n∑
k=0
(
n
k
)
xk =
n∑
k=1
k
(
n
k
)
xk−1.
Setting x = 1, we obtain
n∑
k=1
k
(
n
k
)
= n2n−1.
(b) Integrate on both sides from 0 to 1:∫ 1
0
(1 + x)ndx =
[
1
n + 1
(1 + x)n+1
]1
0
=
2n+1 − 1
n + 1
.
∫ 1
0
n∑
k=0
(
n
k
)
xkdx =
[
n∑
k=0
1
k + 1
(
n
k
)
xk+1
]1
0
=
n∑
k=0
1
k + 1
(
n
k
)
.
Hence
n∑
k=0
1
k + 1
(
n
k
)
=
2n+1 − 1
n + 1
.
(c) Integrate on both sides from −1 to 0:∫ 0
−1
(1 + x)ndx =
[
1
n + 1
(1 + x)n+1
]0
−1
=
1
n + 1
.
∫ 0
−1
n∑
k=0
(
n
k
)
xkdx =
[
n∑
k=0
1
k + 1
(
n
k
)
xk+1
]0
−1
= −
n∑
k=0
(−1)k+1
k + 1
(
n
k
)
.
Hence
1−
n∑
k=1
(−1)k+1
k + 1
(
n
k
)
= −
n∑
k=0
(−1)k+1
k + 1
(
n
k
)
=
1
n + 1
.
That is,
n∑
k=1
(−1)k+1
k + 1
(
n
k
)
=
n
n + 1
.
Q4: (a) Partition on the number of dimers in a paving. If there are k dimers there are
n−2k monomers and a total of n−k pavers. The positions of the k dimers can
then be chosen in
(
n−k
k
)
ways. The result follows from the addition principle
by summing over the values of k from 0 to bn/2c.
(b) Take a board of size 2n. There are F2n+1 pavings in total. Consider the
configuration at the centre of the board at positions (n, n+ 1). These cells are
either covered by a dimer or they are not. In the first case there are boards
of length n − 1 to the left and right of the dimer each of which can be paved
independently in Fn ways for a total number of pavings F
2
n . In the second case
the pavings can be obtained from concatenating any two boards of length n
each of which can be paved in Fn+1 ways for a total number of pavings F
2
n+1.
Q5: (a) The five successive sequences which result by the application of the substitution
rule are:
A 7→ B 7→ AAB 7→ BBAAB 7→ AABAABBBAAB.
(b) From the substitution rule we see that every A in the previous sequence gives
rise to a B in the next sequence and every B in the previous sequence gives rise
to a two A’s and a B in the next sequence. Hence
An = 2Bn−1, Bn = An−1 + Bn−1.
Therefore
Sn = An + Bn
= 2Bn−1 + An−1 + Bn−1
= Sn + 2Bn−1
= Sn + 2(An−2 + Bn−2)
= Sn−1 + 2Sn−2
The boundary condition is S0 = 1 and S1 = 1, since initially we have the string
A which after one application of the substitution rule becomes B.
(c) We have
∞∑
n=2
Snx
n =
∞∑
n=2
Sn−1x
n + 2
∞∑
n=2
Sn−2x
n ⇒
∞∑
n=0
Snx
n − S1x− S0 = x
(
∞∑
n=0
Snx
n − S0
)
+ 2×2
∞∑
n=0
Snx
n ⇒
S(x)− x− 1 = x(S(x)− 1) + 2x2S(x) ⇒
S(x)(1− x− 2×2) = 1
(d) We have 1− x− 2×2 = (1 + x)(1− 2x). So
1
1− x− 2×2
=
A
1 + x
+
B
1− 2x
⇒
1 = A(1− 2x) + B(1 + x) ⇒
A + B = 1, B − 2A = 0 ⇒
A =
1
3
, B =
2
3
Using the geometric series, we then have
S(x) =
∞∑
n=0
Snx
n =
2
3
∞∑
n=0
2nxn +
1
3
∞∑
n=0
(−1)nxn
so that
Sn =
2n+1 + (−1)n
3
.