COMP S264F Discrete Mathematics

Unit 5: Basics of Counting

Question 1. We use B, C, S, L to represent Brown, Cony, Sally, and Leonard, respectively. The following
decision tree shows all the possible selections in the format (President, Secretary):

B C S L

C S L B S L B C L B C S

(B, C) (B, S) (B, L) (C, B) (C, S) (C, L) (S, B) (S, C) (S, L) (L, B) (L, C) (L, S)

(a) As the president must be Brown, the secretary will be one of the remaining 3 members, i.e., there are 3
selections in which Brown is president: (B, C), (B, S), (B, L).

(b) As Leonard is excluded, the president is one of the other 3 members, and then the secretary is one of the
remaining 2 members. There are 3 × 2 = 6 selections in which Leonard is not an official.

(c) By similar argument in (a), there will be 3 selections in which Cony is the secretary. By similar argument
in (b), there are 6 selections in which Cony is not an official.
As these two selections are disjoint, by sum rule, there are 3 + 6 = 9 selections to fulfill the requirement.

(d) There will be 3 selections that Sally is the president and another 3 selections that she is the secretary.
However, we need to exclude the case that Cony is the president and Sally is the secretary, i.e., (C, S).
By sum rule, there are 3 + 3 − 1 = 5 selections to fulfill the requirement.

Question 2.

(a) There are 4 routes to go from home to Kwun Tong and 3 routes from Kwun Tong to HKMU.
By product rule, there will be 4 × 3 = 12 routes from home to HKMU via Kwun Tong.

(b) There are 4 routes from home to Kwun Tong, 3 routes from Kwun Tong to HKMU, 3 routes from HKMU
to Kwun Tong, and 4 from Kwun Tong to home.
By product rule, there will be 4 × 3 × 3 × 4 = 144 routes for the round trip.

(c) Edward can travel 4 routes from home to Kwun Tong and 3 routes from Kwun Tong to HKMU.
For the return, he can only travel 3 − 1 = 2 routes from HKMU to Kwun Tong, and 4 − 1 = 3 routes
from Kwun Tong to home.
By product rule, there will be 4 × 3 × 2 × 3 = 72 routes to fulfill the requirement.

1
Question 3. Let P and N denote the sets of students owning PS5 and NS, respectively, and let U denote the
universal set of students. We know that |U | = 70, |P | = 41, |N | = 26 and |P ∪ N | = 53. By translating the
sub-questions into Venn diagrams, we need to find the cardinality of the shaded area.

U U U U

P N P N P N P N

(a) (b) (c) (d)

(a) |P ∪ N | = |U | − |P ∪ N | = 70 − 53 = 17

(b) |P ∩ N | = |P | + |N | − |P ∪ N | = 41 + 26 − 53 = 14

(c) |P − N | = |P | − |P ∩ N | = 41 − 14 = 27

(d) |N − P | = |N | − |P ∩ N | = 26 − 14 = 12

Question 4. Let U denote the universal set of computing students. Let C, M and D denote the set of students
studying cryptography, machine learning and database, respectively. We know that |U | = 191, |C| = 65, |M | =
76, |D| = 63, |C ∩ M | = 36, |C ∩ D| = 20, |M ∩ D| = 18 and |C ∩ M ∩ D| = 10. By translating the question
into a Venn diagram, we need to find the cardinality of the shaded area.

C M

|C ∪ M ∪ D| = |U | − |C ∪ M ∪ D|
= |U | − (|C| + |M | + |D| − |C ∩ M | − |C ∩ D| − |M ∩ D| + |C ∩ M ∩ D|)
= 191 − (65 + 76 + 63 − 36 − 20 − 18 + 10)
= 191 − 140
= 51

2
Question 5. Let U be the universal set of integers between 1 and 10000 (inclusive). Let Xk be the set of
integers in U that are multiples of k. By the principle of inclusion-exclusion, we need to find

|X3 ∪ X5 ∪ X11 | = |X3 | + |X5 | + |X11 | − |X3 ∩ X5 | − |X3 ∩ X11 | − |X5 ∩ X11 | + |X3 ∩ X5 ∩ X11 | .

Let’s consider X3 which is the set of integers between 1 and 10000 (inclusive) that are multiples of 3. As a
multiple of 3 occurs in every 3 consecutive integers, we have
⌊ ⌋
10000
|X3 | = = 3333 .
3

Similarly, we can show that |X5 | = 2000 and |X11 | = 909.

X3 ∩ X5 is the set of integers in U that are multiples of both 3 and 5. As the least common multiple (LCM)
of 3 and 5 is 15, X3 ∩ X5 is equivalent to the set of integers in U that are multiples of 15, and thus
⌊ ⌋
10000
|X3 ∩ X5 | = = 666 .
15

Similarly, the LCM of 3 and 11 is 33 and thus |X3 ∩ X11 | = 303; the LCM of 5 and 11 is 55 and thus
|X5 ∩ X11 | = 181; the LCM of 3, 5 and 11 is 165 and thus |X3 ∩ X5 ∩ X11 | = 60.

Therefore, the number of integers between 1 and 10000 (inclusive) that are multiples of 3 or 5 or 11 is

|X3 ∪ X5 ∪ X11 | = 3333 + 2000 + 909 − 666 − 303 − 181 + 60 = 5152 .

Question 6.
⌈ ⌉
5
(a) By the pigeonhole principle, when taking 5 courses offered by 3 schools, there must be = 2 courses
3
offered by the same school.

(b) Suppose, for the sake of contradiction, that there is a school that the student does not take any course
from it. The student can take at most 2 courses from each of the remaining 2 schools, which sums up to
at most 4 courses, contradicting that the student will take 5 courses.

Question 7.

(a) By
⌈ the
⌉ pigeonhole principle, if N cards are selected
⌈ from
⌉ 4 suits, there must be a suit containing at least
N N
cards. The smallest integer N that makes = 3 is N = 2 × 4 + 1 = 9, so 9 cards suffice.
4 4
(b) In the worst case, we can select all the clubs, diamonds, and spades, 13 × 3 = 39 cards in total, before
we select a single heart. Therefore, we need to select 39 + 3 = 42 cards to get three hearts.

3
Question 8. Let ai denote the position of the ith available item. We will show that ai − aj = 9 for some i
and j. Consider two sets of numbers

A = {a1 , a2 , . . . , a50 } and B = {a1 + 9, a2 + 9, . . . , a50 + 9} where 1 ≤ ai ≤ 89 .

There are 100 numbers in total and their possible values are from 1 to 89⌈+ 9 =⌉ 98.
100
By the pigeonhole principle, there exists an integer 1 ≤ x ≤ 98 such that = 2 numbers equal to x.
98
All ai ’s are distinct and thus (ai + 9)’s are also distinct, so there exist i, j such that ai = aj + 9 = x, which
implies ai − aj = 9, as desired.

Question 9. Partition the triangle, by connecting the midpoints of its sides, into 4 equilateral triangles with
sides of length 0.5 cm, as shown in the figure. The maximum distance between any two points in any of the
small triangles is 0.5 cm, i.e. any two points in a small triangle must have a distance at most 0.5 cm.

By
⌈ the
⌉ pigeonhole principle, if N points are in⌈ the⌉ big triangle, at least one small triangle contains at least
N N
points. The smallest integer N to make = 2 is N = 1 × 4 + 1 = 5, so at least 5 points should be
4 4
placed in the big triangle such that there exist two points whose distance is at most 0.5 cm.

Question 10. Let x be the number of available IPv4 addresses, and let xA , xB and xC denote the number of
Class A, B, C addresses available, respectively. By sum rule, x = xA + xB + xC .

• To find xA , note that there are 27 − 1 = 127 Class A netids, excluding the netid 1111111. For each
netid, there are 224 − 2 = 16, 777, 214 hostids, excluding the hostids consisting of all 0s and all 1s. Thus,
xA = 127 × 16, 777, 214 = 2, 130, 706, 178.

• To find xB , note that there are 214 = 16, 384 Class B netids. For each Class B netid, there are 216 − 2 =
65, 534 hostids, excluding the hostids consisting of all 0s and all 1s. Thus, xB = 1, 073, 709, 056.

• To find xC , note that there are 221 = 2, 097, 152 Class C netids. For each Class C netid, there are
28 − 2 = 254 hostids, excluding the hostids consisting of all 0s and all 1s. Thus, xC = 532, 676, 608.

We conclude that the total number of IPv4 addresses available is x = xA + xB + xC = 2, 130, 706, 178 +
1, 073, 709, 056 + 532, 676, 608 = 3, 737, 091, 842.

4
Question 11. There are a total of 26 + 26 + 10 + 6 = 68 allowable characters for the password selections.
Let P be the total number of possible passwords of the system. Let Pk be the number of possible passwords
of length k.
By sum rule, P = P8 + P9 + P10 + P11 + P12 .

(a) Since we do not have extra restriction on the choice of character, Pk = 68k . Then, P = P8 + P9 + P10 +
P11 + P12 = 688 + 689 + 6810 + 6811 + 6812 = 9, 920, 671, 339, 261, 325, 541, 376 ≈ 9.9 × 1021 .

(b) To find Pk , it is easier to find the number of strings of all allowable characters, and subtract from this the
number of strings with no special characters. Hence, Pk = 68k −62k . Thus, P = P8 +P9 +P10 +P11 +P12 =
6, 641, 514, 961, 387, 068, 437, 760.
9, 920, 671, 339, 261, 325, 541, 376
(c) For the system in (a), the longest time needed = ≈ 314, 373 years.
109
6, 641, 514, 961, 387, 068, 437, 760
For the system in (b), the longest time needed = ≈ 210, 461 years.
109

Question 12.

(a) By the product rule, there are 8 × 2 × 10 = 160 area codes with format NYX. Similarly, by the product
rule, there are 8 × 8 × 10 = 640 office codes with format NNX and 104 = 1000 station codes with format
XXXX.
Consequently, applying the product rule again, under the old plan, there are 160 × 640 × 10, 000 =
1, 024, 000, 000 different numbers available.

(b) Similar to (a), there are 8 × 10 × 10 = 800 area codes, 8 × 10 × 10 = 800 office codes and 104 = 1000
station codes under the new plan.
Consequently, applying the product rule again, under the new plan, there are 800 × 800 × 10, 000 =
6, 400, 000, 000 different numbers available.

(c) The number of different phone numbers in the form NXX-XXXX is 800 × 1000 ⌈ = 8, 000, 000⌉ .
25, 000, 000
Hence, by the pigeonhole principle, among the 25 million phones, at least = 4 of them
8, 000, 000
must have identical phone numbers.
Hence, 4 area codes are required to provide 4 × 8, 000, 000 = 32, 000, 000 different telephone numbers,
which ensures that all 10-digit numbers of the 25 million phones are different.