COMP2121_1B-Assignment2
File description: Assignment 2 of COMP2121 (subclass 1B) (25/26 Fall) with solutions.
Document status: FIN
Last modified: 2026-09-11 21:12 HKT
COMP2121 Discrete Mathematics
25/26 Semester 1
Assignment 2
SHING, Zhan Ho Jacob 3036228892
1. Basics on Functions
(a) [4 points] For the function β : Z β Z,
β(π) =
ξ¨
1
3
π, if π is divisible by 3,
3π, if π is not divisible by 3,
identify its (1) range, and whether it is (2) injective, (3) surjective, (4) bijective; if your answer is no, explain why.
Answers:
(1) Case 1: π is divisible by 3, i.e., βπ β Z : π = 3π. Then, β(π) =
1
3
(3π) = π, which may or may not be divisible
by 3.
Case 2: π is not divisible by 3 and π = 3π + 1 for some π β Z. Then, β(π) = 3(3π + 1) = 9π + 3, which is
divisible by 3.
Case 3: π is not divisible by 3 and π = 3π + 2 for some π β Z. Then, β(π) = 3(3π + 2) = 9π + 6, which is also
divisible by 3.
Thus, β(π) is either divisible by 3 or not divisible by 3. Therefore, the range of β is Z.
(2) We can easily ο¬nd a counterexample, e.g., β(1) = β(9) = 3. Thus, β is not injective .
(3) By sub-problem (1), we have shown that the range of β is Z, which is the same as the codomain of β. By deο¬nition,
β is surjective .
(4) Since β is not injective, by deο¬nition, β is not bijective .
Page 1 of 11
Page 1 of 11
(b) [6 points] Functions π : R β R and π : R β R are deο¬ned as follows. Determine by formulas the compositions π β¦ π and
π β¦ π.
π (π₯) = (π₯ + 2)
2
and π(π₯) =
ξ¨
2π₯ β 6, if π₯ β₯ 1,
βπ₯ β 1, if π₯ < 1.
Answers:
(1) π β¦ π:
( π β¦ π)(π₯) =
ξ¨
(2π₯ β 4)
2
, if π₯ β₯ 1,
(βπ₯ + 1)
2
, if π₯ < 1.
(2) π β¦ π:
Note that π(π₯) β₯ 1 when 2π₯ β 6 β₯ 1 β π₯ β₯
7
2
β₯ 1 and when βπ₯ β 1 β₯ 1 β π₯ β€ β2.
Also, π(π₯) < 1 when 2π₯ β 6 < 1 β 1 β€ π₯ <
7
2
and when βπ₯ β 1 < 1 β 1 > π₯ > β2.
Thus, the piecewise function π β¦ π has cases: π₯ β (ββ, β2], π₯ β (β2, 1), π₯ β [1,
7
2
), and π₯ β [
7
2
, +β).
Case 1: π₯ β (ββ, β2]. We have π(π₯) β₯ 1, so π(π(π₯)) = 2(βπ₯ β 1) β 6 = β2π₯ β 8.
Case 2: π₯ β (β2, 1), We have π(π₯) < 1, so π(π(π₯)) = β(βπ₯ β 1) β 1 = π₯.
Case 3: π₯ β [1,
7
2
). We have π(π₯) < 1, so π(π(π₯)) = β(2π₯ β 6) β 1 = β2π₯ + 5.
Case 4: π₯ β [
7
2
, +β). We have π(π₯) β₯ 1, so π(π(π₯)) = 2(2π₯ β 6) β 6 = 4π₯ β 18.
Putting all cases together, we have
(π β¦ π)(π₯) =
ο£±










ο£³
β2π₯ β 8, if π₯ β€ β2,
π₯, if β 2 < π₯ < 1,
β2π₯ + 5, if 1 β€ π₯ <
7
2
,
4π₯ β 18, if π₯ β₯
7
2
.
Page 2 of 11
Page 2 of 11
2. Relations and Functions
Prove or disprove the following statements.
(a) [4 points] For arbitrary function π : Z β Z, the relation deο¬ned by
π
=
{
(π₯, π¦) β Z Γ Z | π (π₯) β π (π¦) is even
}
is reο¬exive and transitive.
Answers:
Reο¬exivity: Recall one of the properties of a function π : π΄ β π΅ deο¬ned by a relation π
0
is that βπ₯ β π΄, π¦
1
, π¦
2
β
π΅ : [(π₯ π
0
π¦
1
) β§ (π₯ π
0
π¦
2
) β (π¦
1
= π¦
2
)]. Therefore, for any pair (π₯, π¦) where π₯, π¦ β Z and π₯ = π¦, we must have
π (π₯) = π (π¦) β π (π₯) β π (π¦) = 0, which is even. Thus, π₯ π
π₯ for all π₯ β Z. By deο¬nition, π
is reο¬exive
.
Transitivity: Let π, π, π β Z be arbitrary. Note that for π₯ π
π¦ to hold, π (π₯) and π (π¦) must either be both even or both
odd. Also note that the image of π : Z β Z must be integers, which must either be even or odd. Then, when π π
π
holds, we must have that the parity of π (π) and π (π) are the same. Similarly, when π π
π holds, we must have that
the parity of π (π) and π (π) are the same. Thus, the parity of π (π) and π (π) must also be the same, which implies that
π π
π holds. By deο¬nition, π
is transitive .
Conclusion: Since π
is both reο¬exive and transitive, the statement is true .
(b) [4 points] For arbitrary function π : Z β Z, the relation deο¬ned by
π
=
{
(π₯, π¦) β Z Γ Z | π (π₯) Β· π (π¦) β
{
β1, 0, 1
}}
is symmetric and transitive.
Answers:
Observe that for π (π₯) Β· π (π¦) = 1 to hold, π (π₯) and π (π¦) must both have the magnitude of 1 and the same sign.
Similarly, for π (π₯)Β· π (π¦) = β1 to hold, π (π₯) and π (π¦) must both have the magnitude of 1 but diο¬erent signs. Finally, for
π (π₯)Β· π (π¦) = 0 to hold, at least one of π (π₯) and π (π¦) must be 0. That is, π (π₯), π (π¦) β
{
β1, 0, 1
}
β π (π₯)Β·π (π¦) β
{
β1, 1
}
,
and [( π (π₯) = 0) β¨ ( π (π¦) = 0)] β π (π₯) Β· π (π¦) = 0.
Symmetry: We need to show that π₯ π
π¦ β π¦ π
π₯ holds for all π₯, π¦ β Z. We try to prove by contradiction. Suppose
π₯ π
π¦ holds but we have π¦ ξΆπ
π₯. For the case when π (π₯) Β· π (π¦) β
{
β1, 1
}
, from π₯ π
π¦, we have π (π₯), π (π¦) β
{
β1, 1
}
.
Then, π (π¦) Β· π (π₯) β
{
β1, 1
}
, which implies that π¦ π
π₯ must hold. Then, for the case when π (π₯) Β· π (π¦) = 0, from
π₯ π
π¦, we have either or both of π (π₯) and π (π¦) equal to 0. Without loss of generality, suppose π (π₯) = 0. Then,
π (π¦) Β· π (π₯) = π (π¦) Β· 0 = 0, which implies that π¦ π
π₯ must hold. Then, we have shown that in both cases, π¦ π
π₯ must
hold. This contradicts our assumption that π¦ ξΆπ
π₯. Therefore, π
is symmetric .
Transitivity: The transitivity can be easily disproved by a counterexample. Deο¬ne π
0
: Z β Z as:
π
0
(π₯) =
ξ¨
5, if π₯ β 0,
0, if π₯ = 0.
Then, we have π
0
(β1) Β· π
0
(0) = 0 β
{
β1, 0, 1
}
and π
0
(0) Β· π
0
(1) = 0 β
{
β1, 0, 1
}
, so β1 π
0 and 0 π
1 hold. However,
π
0
(β1) Β· π
0
(1) = 5 Β· 5 = 25 β
{
β1, 0, 1
}
, so β1 ξΆπ
1. Therefore, π
is not transitive .
Conclusion: Since π
is symmetric but not transitive, the statement is false .
Page 3 of 11
Page 3 of 11
3. Image of a Set
Let π : π΄ β π΅ be a function. Consider an arbitrary set π΄
β²
β π΄. The image of set π΄
β²
is deο¬ned to be the set
π (π΄
β²
) =
{
π¦ β π΅ | βπ₯ β π΄
β²
such that π¦ = π (π₯)
}
.
(a) [4 points] Let π΄ =
{
1, 2, 3
}
, π΅ =
{
π, π, π
}
, π΄
1
=
{
1, 2
}
, and π΄
2
=
{
2, 3
}
. Prove or disprove the statement: π (π΄
1
β© π΄
2
) =
π (π΄
1
) β© π (π΄
2
) holds for any function π : π΄ β π΅.
Answers:
Consider the function π : π΄ β π΅ deο¬ned as:
π (π₯) =
ξ¨
π, π₯ β
{
1, 3
}
,
π, π₯ = 2.
Then, the image of π΄
1
β© π΄
2
=
{
2
}
is
π (π΄
1
β© π΄
2
) = π (
{
2
}
) =
{
π
}
,
and the intersection of the images of π΄
1
and π΄
2
is
π (π΄
1
) β© π (π΄
2
) = π (
{
1, 2
}
) β© π (
{
2, 3
}
) =
{
π, π
}
β©
{
π, π
}
=
{
π, π
}
.
Therefore, we have found a counterexample such that the statement does not hold. Thus, the statement is false .
(b) [6 points] Prove that for any subsets π΄
1
, π΄
2
of π΄, π (π΄
1
β© π΄
2
) = π (π΄
1
) β© π (π΄
2
) if π is injective.
Proof:
If π is injective, then for any π₯
1
, π₯
2
β π΄ where π₯
1
β π₯
2
, we must have π (π₯
1
) β π (π₯
2
). For any arbitrary set
π΄ =
{
π
1
, π
2
, . . .
}
, we have π΄
β²
= π (π΄) =
{
π (π
1
), π (π
2
), . . .
}
and
|
π΄
|
=
|
π΄
β²
|
, and for any π΄
π
β π΄, we also have
π΄
β²
π
= π (π΄
π
) β π΄
β²
and
|
π΄
π
|
=
ξ
ξ
π΄
β²
π
ξ
ξ
.
Case 1: π΄
1
β© π΄
2
= β
. Then, π (π΄
1
β© π΄
2
) = π (β
) = β
. Also, π (π΄
1
) β© π (π΄
2
) = π΄
β²
1
β© π΄
β²
2
= β
since π΄
1
β© π΄
2
= β
. Thus,
π (π΄
1
β© π΄
2
) = π (π΄
1
) β© π (π΄
2
) holds.
Case 2: π΄
1
β© π΄
2
β β
. Suppose π΄
1
and π΄
2
has some arbitrary common elements π
1
, π
2
, . . . , π
π
where π β
[1, max(
|
π΄
1
|
,
|
π΄
2
|
)]. Then, π (π΄
1
β© π΄
2
) =
{
π (π
1
), π (π
2
), . . . , π (π
π
)
}
. Also, suppose π΄
1
has some arbitrary unique
elements π
11
, π
12
, . . . , π
1π
where π β [0,
|
π΄
1
|
β π], and the same for π΄
2
with unique elements π
21
, π
22
, . . . , π
2π
where π β [0,
|
π΄
2
|
β π]. Then, π (π΄
1
) =
{
π (π
1
), π (π
2
), . . . , π (π
π
), π (π
11
), π (π
12
), . . . , π (π
1π
)
}
and π (π΄
2
) =
{
π (π
1
), π (π
2
), . . . , π (π
π
), π (π
21
), π (π
22
), . . . , π (π
2π
)
}
. Thus, π (π΄
1
) β© π (π΄
2
) =
{
π (π
1
), π (π
2
), . . . , π (π
π
)
}
= π (π΄
1
β©
π΄
2
). Therefore, π (π΄
1
β© π΄
2
) = π (π΄
1
) β© π (π΄
2
) also holds.
Conclusion: Since π (π΄
1
β© π΄
2
) = π (π΄
1
) β© π (π΄
2
) holds in both cases, the statement is true .
Q.E.D.
Page 4 of 11
Page 4 of 11
4. Asymptotics of Functions
(a) [8 points] For the following functions π , π, determine whether π = O(π), π = Ξ©(π), or π = Ξ(π). Justify your answers.
(1) π (π) = 2π
2
+ 3π + 1 and π(π) = π
2
.
Answers:
Note that βπ β₯ 0, we always trivially have π (π) β₯ π(π). That is, we can choose π = 1 and π
0
= 0, then
βπ β₯ π
0
: π (π) β₯ ππ(π) holds. This gives us π β Ξ©(π).
Also note that βπ β₯ 4, we have π (π) β€ 3π(π), Then, we can also choose π = 3 and π
0
= 4, then βπ β₯ π
0
: π (π) β€
ππ(π) holds. This gives us π β O(π).
Having shown that π β O(π) and π β Ξ©(π), by deο¬nition, we have π β Ξ(π) .
(2) π (π) = log
4
π and π(π) = log
2
(log
2
π).
Answers:
Note that we can transform π (π) as
π (π) =
log
2
π
log
2
4
=
1
2
log
2
π.
Then, we examine the growth rates of π (π) and π(π) as π β +β:
lim
πβ+β
π (π)
π(π)
= lim
πβ+β
1
2
log
2
π
log
2
(log
2
π)
=
1
2
Β· lim
πβ+β
log
2
π
log
2
(log
2
π)
=
1
2
Β· lim
πβ+β
ln π
ln 2
ln(log
2
π)
ln 2
=
1
2
Β· lim
πβ+β
ln π
ln(log
2
π)
=
1
2
Β· lim
πβ+β
ln π
ln(
ln π
ln 2
)
=
1
2
Β· lim
πβ+β
ln π
ln(ln π) β ln(ln 2)
= +β
Therefore, we have π (π) grows asymptotically faster than π(π), i.e., π β Ξ©(π). We can verify this by choosing
π = 1 and π
0
= 16. Then, βπ β₯ π
0
, we have π (π) β₯ π(π). Thus, π β Ξ©(π) .
(3) π (π) = π! and π(π) = 100
π
. [Hint: Consider Stirlingβs formula.]
Answers:
By Stirlingβs formula, we have π! β
β
2ππ
ξ
π
π
ξ
π
. Then, the limit evaluates as lim
πββ
π (π)
π(π)
β lim
πββ
β
2ππ
π+
1
2
π
βπ
100
π
.
We can identify the dominant term being π
π+
1
2
, which grows faster than all other terms. Thus, the ratio
π (π)
π(π)
β +β
as π β +β.
Therefore, we have π (π) grows asymptotically faster than π(π), i.e., π β Ξ©(π) .
Page 5 of 11
Page 5 of 11
(b) [8 points] For any function π : N β N, deο¬ne π
π
: N β N to be the function
π
π
(π) = π β¦ Β·Β·Β· β¦ π
ξΌ ξ»ξΊ ξ½
π times
(π β 1).
Let π
1
be the function deο¬ned by π
1
(π) = 2π + 1 for any π β N and π
2
be the function deο¬ned by π
2
(π) = π
2
for any π β N.
Find a function β : N β N such that all the following requirements are satisο¬ed:
β’ β β Ξ©( π
π
1
) but β β O( π
π
1
);
β’ β β O( π
π
2
) but β β Ξ©( π
π
2
).
Justify your answer.
Answers:
First, we observe the behaviour of π
π
1
:
π
π
1
(0) = 0,
π
π
1
(1) = π
1
(π β 1)
ξ
ξ
π=1
= 2π β 1
ξ
ξ
π=1
= 1,
π
π
1
(2) = π
1
(2π β 1)
ξ
ξ
π=2
= 4π β 1
ξ
ξ
π=2
= 7,
π
π
1
(3) = π
1
(4π β 1)
ξ
ξ
π=3
= 8π β 1
ξ
ξ
π=3
= 23,
π
π
1
(4) = π
1
(8π β 1)
ξ
ξ
π=4
= 16π β 1
ξ
ξ
π=4
= 63,
Β·Β·Β·
We can see the coeο¬cient of the dominant term π is 2
π
. Also, in each iteration, the coeο¬cient is multiplied by π and
some abitrary number is added. Then, we can identify the dominant term of π
π
1
(π) being 2
π
π.
Similarly, we observe the behaviour of π
π
2
:
π
π
2
(0) = 0,
π
π
2
(1) = π
2
(π β 1)
ξ
ξ
π=1
= (π β 1)
2
ξ
ξ
π=1
= 0,
π
π
2
(2) = π
2
((π β1)
2
)
ξ
ξ
π=2
= (π β 1)
4
ξ
ξ
π=2
= 1,
π
π
2
(3) = π
2
((π β1)
4
)
ξ
ξ
π=3
= (π β 1)
8
ξ
ξ
π=3
= 256,
π
π
2
(4) = π
2
((π β1)
8
)
ξ
ξ
π=4
= (π β 1)
16
ξ
ξ
π=4
= 43, 046, 721,
Β·Β·Β·
The exponent of the dominant term π is 2
π
. Then, the dominant term of π
π
2
(π) is π
2
π
.
We would like to ο¬nd a function β : N β N such that at large π, β grows asymptotically faster than π
π
1
but slower than
π
π
2
. We choose β(π) = π
π
.
Consider the ratio
β(π)
π
π
1
(π)
=
π
π
2
π
π
=
π
πβ1
2
π
as π β +β. It is clear that π
πβ1
grows much faster than 2
π
. Thus,
lim
πββ
β(π)
π
π
1
(π)
= +β, which implies that β β Ξ©( π
π
1
) but β β O( π
π
1
).
Now, consider the ratio
β(π)
π
π
2
(π)
=
π
π
π
2
π
=
1
π
2
π
βπ
as π β +β. It is trivial to show that lim
πββ
β(π)
π
π
2
(π)
= 0, which implies
that β β O( π
π
2
) but β β Ξ©( π
π
2
).
Therefore, we have found a function β(π) = π
π
that satisο¬es all the requirements.
Page 6 of 11
Page 6 of 11
5. Basic Counting
(a) [4 points] Among all positive numbers that devide 4050 exactly, how many are multiples of 45?
Answers:
Observe the prime factorisation of 4050 = 2 Β· 3
4
Β· 5
2
. Also note the fact that an integer π β€ π divides π exactly iο¬ every
prime factor of π is also a prime factor of π, i.e., the multiples of at least one prime factor of π divide π exactly.
Then, the divisors of 4050 must have the form 2
π
Β· 3
π
Β· 5
π
where π β [0, 1] β©Z, π β [0, 4] β©Z, and π β [0, 2] β©Z. We
have 2 ways to choose π, 5 ways to choose π, and 3 ways to choose π. Thus, the total number of divisors of 4050 is
2 Β· 5 Β· 3 = 30.
Now, we denote π
π
as the set of multiples of π with βπ₯ β π
π
: 1 β€ π₯ β€ 4050. Then,
|
π
45
|
=
ξ
4050
45
ξ
= 90. Note that
every multiple of 45 must have the form πΆ Β·3
2
Β· 5, where πΆ β Z
+
such that πΆ Β· 3
2
Β· 5 β€ 4050. Then, for the multiples of
45 to also be divisors of 4050, πΆ must be in the form 2
π
Β·3
π
Β·5
π
where π β [0, 1] β©Z, π β [0, 2]β©Z, and π β [0, 1] β©Z.
We have 2 ways to choose π, 3 ways to choose π, and 2 ways to choose π. Thus, the total number of multiples of 45 that
are also divisors of 4050 is 2 Β· 3 Β· 2 = 12.
Therefore, there are 12 such numbers .
(b) [4 points] There are 2 identical red balls and 3 identical black balls. You are going to put them into 5 diο¬erent boxes. If
each box can contain at most 2 balls, how many ways are there to put the balls in the boxes?
Answers:
Consider the distribution of balls, we can solve the problem by cases.
Case 1: Every box contains exactly 1 ball. This is the same as the number of 5-permutations of 2 red balls and 3 black
balls, which is
5!
2!3!
= 10.
Case 2: One box contains 2 balls, another box contains no balls, and the remaining 3 boxes contain 1 ball each. We
can choose 1 box out of 5 to contain 2 balls (label it as π΅
2
), and then choose 1 box out of 4 to contain no balls (π΅
0
). The
remaining 3 boxes will contain 1 ball each (π΅
1π
, π = 1, 2, 3). There are 5 Β· 4 = 20 ways to choose the boxes. In each of
these choices, π΅
2
can either contain 2 red balls, 2 black balls, or 1 of each colour. For the two red balls case, π΅
1π
must
contain 1 black ball each, which is 1 way. For the two black balls case, we have 3 ways to choose one of π΅
1π
to contain
the remaining black ball, and the other two boxes will contain 1 red ball each. For the 1 red and 1 black balls case, we
have 3 ways to choose one of π΅
1π
to contain the remaining red ball, and the other two boxes will contain 1 black ball
each. Thus, there are 1 +3 +3 = 7 ways to distribute the balls in each choice of boxes. Therefore, there are 20 Β·7 = 140
ways in this case.
Case 3: Two boxes contain 2 balls each, and one box contains 1 ball, and the remaining 2 boxes contain no balls. We
ο¬rst choose 1 box to hold 1 ball (π΅
1
), there are 5 ways. π΅
1
can either hold a black ball or a red ball (2 ways). If π΅
1
holds
a black ball, then we either choose 1 box out of 4 to hold 2 red balls (4 ways) and 1 box out of 3 to hold 2 black balls (3
ways), or we choose 2 boxes out of 4, each holding the same colour (6 ways) This gives us 4 Β· 3 + 6 = 18 ways. If π΅
1
holds a red ball, then we must choose 1 box out of 4 to hold 2 black balls (4 ways) and 1 box out of 3 to hold 1 red and
1 black balls (3 ways). This gives us 4 Β· 3 = 12 ways. Therefore, there are 5 Β· (18 + 12) = 150 ways in this case.
Putting all cases together, we have 10 + 140 + 150 = 300 ways in total
.
(c) [4 points] In a game, the player needs to move from the point (0, 0) to the point (π, π) where π β₯ π > 0 are integers. At
each point (π₯, π¦), the player can either move right to (π₯ + 1, π¦) or move up to (π₯, π¦ + 1). It is forbidden to move up for two
successive times. How many diο¬erent ways are there for the player to reach (π, π)?
Answers:
Note that since the player can move only one unit to the right or upwards, regardless of the path the player chooses,
exactly (π + π) steps are required to reach (π, π) from (0, 0), with π steps to reach the line π₯ = π and π steps to reach
the line π¦ = π.
The path is a (π + π)-sequence of the set {π, π
}, where π denotes moving upwards and π
denotes moving to the right.
In addition, we must have no pairs of πβs that are adjacent to each other. The sequence must have π π
βs and π πβs.
Consider a sequence of π π
βs and (π + 1) gaps between each pair of π
βs, including the head and the tail. We need to
choose π gaps to put the π πβs, that is
ξ
π+1
π
ξ
ways. Thus, there are
ξ
π+1
π
ξ
ways in total .
Page 7 of 11
Page 7 of 11
6. Counting Sets and Relations
(a) [4 points] In a group of 15 computer scientists, each scientist has collaborated with at least 8 other members of the group.
Prove that there exist 3 members, such that each one of them has collaborated with the other two members.
Proof:
Let π΄ be the set of the 15 computer scientists, π₯ π
π¦ : βπ₯ has collaborated with π¦β. Note that π
is symmetric. Also
deο¬ne the set πΆ
π₯
=
{
π¦ β π΄ β
{
π₯
}
| π₯ π
π¦
}
as the set of collaborators of π₯. Then, we have βπ₯ β π΄ :
|
πΆ
π₯
|
β₯ 8.
Assume, for contradiction, that no 3 members have mutually collaborated.
For any arbitrary π₯ β π΄, and for some arbitrary π¦ β πΆ
π₯
, since π₯ and π¦ have collaborated, we also have π₯ β πΆ
π¦
. Since no
3 members have mutually collaborated, we have ξΆβ π§ : (π§ β πΆ
π₯
β§ π§ β πΆ
π¦
), where π₯, π¦, π§ are distinct.
Note that
|
πΆ
π₯
β
{
π¦
}|
β₯ 7 and
ξ
ξ
πΆ
π¦
β
{
π₯
}
ξ
ξ
β₯ 7. Since πΆ
π₯
β
{
π¦
}
and πΆ
π¦
β
{
π₯
}
are disjoint, we have
|
πΆ
π₯
β
{
π¦
}|
+
ξ
ξ
πΆ
π¦
β
{
π₯
}
ξ
ξ
β₯
14. However, since π΄ β
{
π₯, π¦
}
has only 13 members, and (πΆ
π₯
β
{
π¦
}
) βͺ (πΆ
π¦
β
{
π₯
}
) β π΄ β
{
π₯, π¦
}
, we must have
ξ
ξ
(πΆ
π₯
β
{
π¦
}
) βͺ (πΆ
π¦
β
{
π₯
}
)
ξ
ξ
β€ 13. This contradicts the fact that
|
πΆ
π₯
β
{
π¦
}|
+
ξ
ξ
πΆ
π¦
β
{
π₯
}
ξ
ξ
β₯ 14.
Therefore, our assumption is false, and there exist 3 members who have mutually collaborated .
Q.E.D.
(b) [6 points] Let π΄, π΅, πΆ be sets with
|
π΄
|
=
|
π΅
|
=
|
πΆ
|
= π and
|
π΄ βͺ π΅ βͺπΆ
|
= π. Find the minimal value of
|
π΄ β© π΅ β©πΆ
|
.
Answers:
Recall that
|
π΄ βͺ π΅ βͺπΆ
|
=
|
π΄
|
+
|
π΅
|
+
|
πΆ
|
β
|
π΄ β© π΅
|
β
|
π΄ β© πΆ
|
β
|
π΅ β© πΆ
|
+
|
π΄ β© π΅ β©πΆ
|
, substitue the given values, we
have
π = 3π β
|
π΄ β© π΅
|
β
|
π΄ β© πΆ
|
β
|
π΅ β© πΆ
|
+
|
π΄ β© π΅ β©πΆ
|
|
π΄ β© π΅ β©πΆ
|
= π β 3π +
|
π΄ β© π΅
|
+
|
π΄ β© πΆ
|
+
|
π΅ β© πΆ
|
(1)
Since
|
π΄ βͺ π΅
|
=
|
π΄
|
+
|
π΅
|
β
|
π΄ β© π΅
|
, and
|
π΄ βͺ π΅
|
β€
|
π΄ βͺ π΅ βͺπΆ
|
= π, we have
|
π΄
|
+
|
π΅
|
β
|
π΄ β© π΅
|
β€ π
2π β
|
π΄ β© π΅
|
β€ π
|
π΄ β© π΅
|
β₯ 2π β π
Similarly, we ο¬nd the lower bounds for
|
π΄ β© πΆ
|
and
|
π΅ β© πΆ
|
to also be 2π β π.
Then, equation (1) becomes
|
π΄ βͺ π΅ βͺπΆ
|
β₯ π β 3π + 3(2π β π)
= 3π β 2π
Moreover, since
|
π΄ β© π΅ β©πΆ
|
β₯ 0, we have that min
|
π΄ βͺ π΅ βͺπΆ
|
= max(0, 3π β 2π)
.
Page 8 of 11
Page 8 of 11
(c) [6 points] Let π΄ be a set with
|
π΄
|
= 5. Count the number of distinct (i) symmetric relations and (ii) asymmetric relations that
can be constructed on π΄. An asymmetric relation π
is a relation such that, for every pair of distinct π₯ and π¦, π₯ π
π¦ β Β¬(π¦ π
π₯).
Answers:
Express a relation on π΄ as a 5-by-5 matrix, where each entry π
π π
=
ξ¨
1, if π₯
π
π
π₯
π
,
0, if π₯
π
ξΆπ
π₯
π
, and π₯ β π΄.
(i) Symmetric Relations:
If π
is symmetric, then its matrix representation must also be a symmetric matrix. Since the main diagonal of
a symmetric matrix is arbitrary, for each entry, we can freely choose between 1 and 0. Then, we have 2
5
= 32
choices. For the oο¬-diagonals, we must have π
π π
= π
ππ
, where π β π. Then, for π
π π
where π β [2, 5] and
π β [1, π β 1], i.e., the lower triangular part of the matrix excluding the main diagonal, we can freely choose
between 1 and 0, and the corresponding π
ππ
is constrained. We have 2
4
Β· 2
3
Β· 2
2
Β· 2
1
= 1024 choices.
Therefore, in total, there are 32 Β· 1024 = 32, 768
distinct symmetric relations.
(ii) Asymmetric Relations:
Note that the requirement of asymmetry implies that whenever π
π π
= 1, its corresponding π
ππ
must be 0, and vice
versa, but if π
π π
= π
ππ
= 0, the requirement is still satisο¬ed. Also, the main diagonal must be all 0βs as asymmetry
requires irreο¬exivity. Then, for each of the oο¬-diagonal pairs (π
π π
, π
ππ
) where π β [2, 5] and π β [1, π β 1], there
are 3 possibilities: (1, 0), (0, 1), and (0, 0). Note that there are 4 + 3 + 2 + 1 = 10 such pairs. Thus, we have
3
10
= 59, 049 choices.
Therefore, in total, there are 59, 049 distinct asymmetric relations.
7. Pigeonhole Principle
(a) [4 points] Show that if you have a set π΄ of 5 points (π₯
π
, π¦
π
) β Z
2
, there must exist distinct π, π such that, for (π₯
π
, π¦
π
), (π₯
π
, π¦
π
) β
π΄, the midpoint
ξ
π₯
π
+ π₯
π
2
,
π¦
π
+ π¦
π
2
ξ
also lies in Z
2
.
Proof:
For the midpoint of (π₯
π
, π¦
π
), (π₯
π
, π¦
π
) β π΄ to lie in Z
2
, we require both the of their π₯- and π¦-coordinates to have the same
parity, such that the sums of their π₯- and π¦-coordinates are even, hence divisible by 2. There can be 4 possible parity
cases, namely
{
(even, even), (even, odd), (odd, even), (odd, odd)
}
. We have 5 points distributed among the 4 cases, by
the Pigeonhole Principle, at least two of them are in the same parity case. Therefore, there are at least 2 distinct points
in π΄ whose sums of π₯- and π¦-coordinates are of the same parity, and their midpoint lies in Z
2
.
We have shown that such distinct π, π exist
.
Q.E.D.
(b) [4 points] For any π β N, prove that for any collection of π + 1 distinct numbers drawn from
{
1, 2, . . . , 2π
}
, there must be
at least one pair of numbers such that one of them is a multiple of the other.
Proof:
Note that every positive integer π₯ can be written in the form of π₯ = 2
π
Β· π, where π is odd and π β₯ 0. Then, each
π₯ β
{
1, 2, . . . , 2π
}
corresponds to a unique odd factor π β
{
1, 3, 5, . . . , 2π β 1
}
. There are π such odd factors in total.
Since we are drawing π + 1 distinct numbers, by the Pigeonhole Principle, at least two of them must correspond to the
same odd factor. Let π = 2
π
Β· π and π = 2
π‘
Β· π be the two numbers, where π , π‘ β₯ 0. Without loss of generality, assume
π < π‘, then we have
π
π
=
2
π‘
Β· π
2
π
Β· π
= 2
π‘ βπ
,
which is an integer. Thus, π is a multiple of π.
We have shown that such a pair of numbers exist .
Q.E.D.
Page 9 of 11
Page 9 of 11
8. Conditional Probability
You are training a classiο¬er for spam detection using machine learning. Each data point (π₯, π¦) in the dataset represents an email,
which can be categorized as either spam or non-spam, with the content of the email denoted as π₯ and a label π¦ β spam, non-spam.
(a) [4 points] Given that 10% of the data in the dataset is labelled as spam and 90% is labelled as non-spam, and that the modelβs
output satisο¬es the following conditions:
π(output = spam | label = spam) = 0.8, π(output = non-spam | label = non-spam) = 0.9,
determine the probability that the modelβs output matches the true label when the input is randomly selected from the dataset.
Answers:
Let πΏ be the event that the mail is labelled as spam, πΏ be the event that the mail is labelled as non-spam, π be the event
that the model outputs spam for the mail, and π be the event that the model outputs non-spam for the mail.
From the given information, we have
π(πΏ) = 0.1, π(πΏ) = 0.9,
π(π | πΏ) = 0.8, π(π | πΏ) = 0.9.
We need to ο¬nd π(πΏ β© π) + π(πΏ β©π).
By conditional probabilities, we have π(π | πΏ) =
π (πΏβ©π)
π (πΏ )
β π(πΏ β© π) = π(π | πΏ) Β· π(πΏ) = 0.8 Β· 0.1 = 0.08.
Similarly, we have π(π β© πΏ) = π(π | πΏ) Β· π(πΏ) = 0.9 Β· 0.9 = 0.81.
Therefore, the required probability is π(output matches label) = 0.08 +0.81 = 0.89 .
(b) [4 points] Continuing from part (a), calculate the probability that the true label is spam given that the model predicts spam.
Answers:
We need to ο¬nd π(πΏ | π) =
π (πΏβ©π)
π (π)
.
By the law of total probability, we have π(π) = π(π | πΏ)π(πΏ) + π(π | πΏ)π(πΏ) = 0.8 Β· 0.1 +
ξ¨
1 β π(π | πΏ)
ξ©
Β· 0.9 =
0.08 + (1 β 0.9) Β· 0.9 = 0.08 +0.1 Β· 0.9 = 0.08 + 0.09 = 0.17.
Therefore, π(πΏ | π) = 0.08/0.17 =
8
17
.
(c) [4 points] Suppose the labels are manually provided by users, introducing noise in the dataset. This means some emails
have incorrect labels (i.e., the label has been ο¬ipped from spam to non-spam or vice versa). With the same conditions as in
part (a), and given that 5% of the emails have incorrect labels, determine the probability that the model categorizes a random
email from the dataset correctly, regardless of whether the label is accurate.
Answers:
Let πΆ be the event that the label is correct, and πΆ be the event that the label is ο¬ipped. We have π(πΆ) = 0.95 and
π(πΆ) = 0.05.
When the label is correct (πΆ), from part (a), we know the probability that the modelβs output matches the label is 0.89.
Since the label is correct, this is also the probability that the model categorizes the email correctly.
When the label is ο¬ipped (πΆ), the modelβs output matches the (incorrect) label with the same probability 0.89. Therefore,
the model categorizes the email correctly (i.e., matches the true label) with probability 1 β 0.89 = 0.11.
By the law of total probability, the probability that the model categorizes a random email correctly is
π(correct) = π(correct | πΆ)π(πΆ) + π(correct | πΆ)π(πΆ)
= 0.89 Β·0.95 +0.11 Β· 0.05
= 0.8455 + 0.0055
= 0.851 .
Page 10 of 11
Page 10 of 11
(d) [4 points] There are π passengers queuing to board a bus one by one. Each passenger has an assigned seat. However, the
ο¬rst passenger does not follow the seating arrangement and chooses a seat at random. Subsequently, each passenger takes
their assigned seat if it is available; otherwise, they select a seat uniformly at random from the remaining unoccupied seats.
Determine the probability that the last passenger sits in the assigned seat.
Answers:
Note that when there is only 1 passenger, they will always sit in their assigned seat. Therefore, the probability is 1.
For π β₯ 2, denote πΈ
π
π
as the event that the π-th passenger sits in the seat numbered π. We are required to ο¬nd π(πΈ
π
π
).
Note that there are three cases:
β’ Case 1 β π¬
1
1
: The ο¬rst passenger chooses seat 1. In this case, all subsequent passengers will ο¬nd their assigned
seats unoccupied and sit in them. Thus, π(πΈ
π
π
| πΈ
1
1
) = 1.
β’ Case 2 β π¬
π
1
: The ο¬rst passenger chooses seat π. In this case, the last passenger will ο¬nd their assigned seat
occupied and must choose to sit somewhere else. Thus, π(πΈ
π
π
| πΈ
π
1
) = 0.
β’ Case 3 β π¬
π
1
, where π β
{
2, 3, 4, . . . , π β 1
}
: π(πΈ
π₯
1
) =
πβ2
π
. Now, assume the 1st passenger chooses some seat,
say seat π₯
0
. Then, passengers 2, 3, . . . , π₯
0
β 1 will ο¬nd their assigned seats unoccupied and sit in them. When
passenger π₯
0
boards the bus, the problem reduces to as if the π₯
0
-th passenger were the ο¬rst to board the bus with
π β π₯
0
+ 1 seats remaining. The passenger, can either sit in seat 1, allowing all subsequent passengers to sit in
their assigned seats, or sit in seat π, so that the last passenger cannot sit in their assigned seat, or sit in some other
seat, until the problem reduces to only two passengers remaining. That is, the (π β 1)-th passenger either sits in
seat 1 or seat π. Therefore, we have π(πΈ
π
π
| πΈ
π₯
1
) = π(πΈ
πβπ₯+1
πβπ₯+1
) =
1
2
.
Therefore, by the law of total probability, we have
π(πΈ
π
π
) = π(πΈ
π
π
| πΈ
1
1
)π(πΈ
1
1
) + π(πΈ
π
π
| πΈ
π
1
)π(πΈ
π
1
) + π(πΈ
π
π
| πΈ
π₯
1
)π(πΈ
π₯
1
)
= 1 Β·
1
π
+ 0 Β·
1
π
+
1
2
Β·
π β 2
π
=
1
π
+
π β 2
2π
=
π
2π
=
1
2
.
Thus, we have π(πΈ
π
π
) =
ξ¨
1
2
if π β₯ 2
1 if π = 1
.
(e) [4 points] A family has two children. It is known that at least one of them is a girl born on a Monday. What is the probability
that both children are girls?
Answers:
Let πΊ =
{
π, πΉ
}
be the set of genders, and π· =
{
Mon, Tue, Wed, Thu, Fri, Sat, Sun
}
be the set of days in a week. Then,
the sample space π is given by π = (πΊ Γ π·) Γ (πΊ Γ π·) and
|
π
|
= 2 Β· 7 Β· 2 Β· 7 = 196.
Denote π΄ as the event that at least one girl was born on a Monday, and π΅ as the event that both children are girls. We
are required to ο¬nd π(π΅ | π΄).
To ο¬nd
|
π΄
|
, we consider the complement π΄, which is that there is no girl, or if there is a girl, she was not born on a
Monday. For two children, there are 13 Β· 13 = 169 such outcomes in total. Thus,
|
π΄
|
=
|
π
|
β
ξ
ξ
ξ
π΄
ξ
ξ
ξ
= 196 β 169 = 27.
To ο¬nd
|
π΄ β© π΅
|
, ο¬rst consider π΅, whose cardinality is
|
π΅
|
= 7 Β· 7 = 49. Then, count the number of outcomes in π΅ that
none of the girls was born on a Monday. There are 6 Β·6 = 36 such outcomes. Thus,
|
π΄ β© π΅
|
=
|
π΅
|
β36 = 49 β36 = 13.
Therefore, by conditional probability, we have
π(π΅ | π΄) =
π(π΄ β© π΅)
π(π΄)
=
13
27
.
Page 11 of 11
Page 11 of 11
This is the solutions that was submitted for COMP2121 (subclass 1B) Assignment 2 by the author.
The assignment was scored 100/100. The solutions included in this document was proposed by the author and may not be the optimal solution. As a result of copyright issues, the official solutions cannot be provided in this document. You are advised to consult other when in doubt.
Please note that there are often more than one way to solve the problems and the solutions provided here are not guaranteed to be the most optimal approach. They are provided for reference only.
This document will receive no further updates.
See also
-
COMP2121_1B-Assignment1
Assignment 1 of COMP2121 (subclass 1B) (25/26 Fall) with solutions.
-
COMP2121_1B-Assignment3
Assignment 3 of COMP2121 (subclass 1B) (25/26 Fall) with solutions.
-
CCCH9044-Individual-Essay
The 3000-word individual essay for the course CCCH9044.
-
CCGL9042-Question-Bank
The question bank for CCGL9042 in-class quizzes.
-
CCHU9094-Essay
Read the student submission of the essay to CCHU9094. This work has been graded A.
-
CCST9064-Video-Essay
The final video essay submitted for CCST9064 group project. Python code for Manim included.