Compsci 225
Exam: Revision Guide (Solutions)
Wednesday, October 28th, 5:00-7:30pm UoA 2021
For almost everyone enrolled in Compsci 225, Exams has announced that our exam will take place
on October 28th at 17:00 New Zealand time. You should verify this for yourself on Student Services
Online in case your exam timetable is different (due to e.g. a clash), but for almost everyone If you
have an issue with this exam time, please contact Exams as soon as possible to try to get things
fixed! In particular, please note that Amal and I cannot reschedule or otherwise do anything about
the timing of your exams: these things are entirely under the control of the University’s central
Exams office, who typically ask for considerable lead time to process exceptions.
The exam is open book / open notes / open to Internet search, and will consist of 5-7 free-response
problems, covering weeks 1-12 of the course, with about a 30/70 split between weeks 1-6 and weeks
7-12. To help you revise, I’ve written this revision guide: it contains a set of practice problems we’ve
written to model the kinds of tasks you’re likely to face!
Specifically, you’ll find nine problems in this guide. These problems are not as polished as your
exam tasks would be: i.e. some problems here will be much longer than reasonable exam problems
would be, some might be a bit too short, etc. Note that your exam may mix and match concepts
on some problems: like you saw in the test, you could have a problem that has some induction and
some RSA mixed together, or some graph theory combined with error-correcting codes, so that we
can cover most of the course without asking a ton of questions.
Solutions to these exercises can be found on the same Canvas page where you found this document.
If you’re stuck, post to Piazza, or stop by the drop-in sessions and office hours!
1
https://www.auckland.ac.nz/en/students/academic-information/exams-and-final-results/before-exams/exam-timetable.html
https://www.auckland.ac.nz/en/students/my-tools/sso.html
https://www.auckland.ac.nz/en/students/my-tools/sso.html
1. (Graphs.)
(a) Suppose that G is a connected simple planar graph containing V vertices, E edges and
F faces. Suppose further that each of V,E and F are prime numbers.
Prove that exactly one of V,E or F must be equal to 2.
(b) Suppose that G = (V,E) is a graph on n vertices, where each vertex has degree at least
n/2. Prove that G must be connected.
(c) Let G be the set of all planar simple graphs. Given a planar graph G, let #V (G) denote
the number of vertices in G, and similarly let #E(G),#F (G) denote the number of edges
and faces in G. Define the function f : G → Z as follows:
f(G) = χ(G) ·
(
3− #V (G) + #E(G)− #F (G)
)
+
∑
v∈V (G)
deg(v)
% 2
What is the range of f : i.e. what integers are possible outputs of f?
Solution:
(a) The key observation to make here is that 2 is the only even prime number; all other primes
are odd. Therefore, because the Euler characteristic tells us that V − E + F = 2, we
cannot have all three of V,E and F be odd (as the sum/difference of three odd numbers
is odd, not even!)
Indeed: the only way for V −E + F to be even is if either exactly one of V,E, F is 2, or
if all three are 2.
In the case where all three are 2, this would mean in particular that we have a two-vertex
two-edge graph. But G is simple, and so can contain at most one edge if it has just two
vertices! This leaves us with just the case where exactly one of V,E, F is two, as claimed.
(b) Take any graph G in which the degree of every vertex is at least n/2, and pick any two
vertices x, y ∈ V .
x has degree at least n/2, so it’s connected to n/2 other vertices. In particular, because
there are n− 1 vertices other than x, it’s connected to over half of the vertices in G.
So, because y has degree at least n/2, it’s also connected to over half of the vertices in
G. In particular, this means that x and y have a neighbor in common, and so there’s a
path of length 2 from x to y!
(c) First, we note that by the degree-sum formula, the sum of all degrees in G is 2#E(G),
and thus that the degree sum modulo 2 is always 0; as such, we can ignore the last term.
Next, we note that V − E + F for any planar graph is 1+ the number of connected
components of G: i.e. if G is connected, V − E + F = 2, if G has two connected
components, V −E+F = 3, and so on/so forth. As a result, we can see that 3−V +E−F
is either 1, 0, or negative for all planar graphs.
Finally, we can note that if G is planar, χ(G) is at most 4, by the four-colour theorem.
As a result, the range of f is clearly at most Z∩(−∞, 4]; we cannot output a value greater
than 4, as the maxima of the individual functions that make up f cannot combine to
yield a value greater than 4.
To conclude, we simply note that this range is actually attainable. K4,K3 and K2 are all
connected planar graphs with chromatic numbers 2-4, and so generate the values 2, 3, 4
when plugged into f .
Now, to conclude, consider G =
n times︷ ︸︸ ︷
K1 ∪K1 ∪ . . . ∪K1, i.e. n isolated vertices in a graph.
This has V − E + F = n + 1, as we have n vertices and the one outside face; it also
has χ(G) = 1, as we can give all vertices the same colour. Therefore, we have f(G) =
3− (n+ 1) = 2− n, and thus can get any integer ≤ 1 as an output of f as well.
2
2. (Automata.)
(a) Suppose that we are working over the alphabet Σ = {a, b}. Draw an automata that
recognizes the language of all strings that contain exactly two a’s and two b’s (in any
order.)
(b) Let p be a prime, and let L be the set of all strings over the alphabet {a} whose lengths
are multiples of p. Prove or disprove the following claim: “If M is a DFA over the
alphabet {a} whose language of accepted strings is L, then the number of states in M is
a multiple of p.”
(c) In class, we proved that you cannot create a DFA over the alphabet {a} that accepts
precisely the language L of strings with prime lengths. Prove that you cannot create a
DFA over the language L = {a} that accepts precisely the set of strings with nonprime
lengths.
Solution:
(a) Here is one (of many) possible DFA! In this diagram, the blue states are the accepting
states, and the red dashed lines are labeled with any letters not used on other edges
leaving the state they originate from.
garbage
initial
b
a
b
a
b
a
b
b
a
a
b
b
a
b
a
b
a
a
To expand a bit on how you’d get this: If you want to accept any string with 2 a’s and
2 b’s, you want to accept precisely the strings aabb, abab, abba, baab, baba, bbaa, and no
others (as those are the only strings with 2 a’s and 2 b’s.)
So: how would you recognize just one of these strings, like say aabb? Well: one way to
do it is via the left path on the diagram above. That is:
� Draw four vertices in a row.
� Make it so that you go from the initial vertex to the first one if your DFA sees an
”a”.
� Similarly, go from the first to the second if your DFA sees another ”a”.
� Go from the second to the third if your DFA sees a ”b”.
� Go from the third to the fourth if your DFA sees a ”b”.
� If your DFA sees anything after that fourth state, it should go to the ”garbage” state
at bottom, from which it cannot leave: this is because we want to not accept any
strings with more than two a’s or b’s.
� As well, if your DFA sees anything other than the a → a → b → b path, it should
leave this path as well, as we’re trying to detect only aabb.
You can do the same thing for all of the other strings! Combining these paths together
gives you the DFA above, and finishes the problem.
(b) This is false! Consider the following 3-state automaton:
3
init, 0
a
even, +
a
a
odd
This automaton accepts all strings of length 0 because the initial state is an accepting
state, as well as any string whose length is a positive multiple of 2, because of the length-
2 loop that cycles between the even and odd states. 3 is not a multiple of 2, so we’ve
disproven our claim by finding a counterexample.
(c) You could create an argument here that parallels the “no DFA exists that accepts only
prime-length strings” from the typeset notes, or you could consider the following quick
proof by contradiction: assume that such a DFA could exist, and call it M .
Now, consider M , defined by taking M and reversing which states are accepting and
which are not. If M accepts a string, it’s a string that M rejects; conversely, if M rejects
a string, it’s a string that M accepts.
This means that M accepts precisely the language of all prime-length strings. We know
this is impossible from lecture, and thus have arrived at a contradiction, as desired.
4
3. (Error-correcting codes.)
(a) Find a ternary length 4 code C with distance 3, containing at least 4 elements.
(b) A Latin square (introduced briefly at the end of Lecture 15) is a n × n grid in which
every square contains a number from 1, 2, . . . n, with no repeats in any row or column.
Two 4× 4 Latin squares are drawn below.
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
1 2 3 4
4 3 2 1
2 1 4 3
3 4 1 2
i. Describe how to make a n× n Latin square, for every n.
ii. Given a Latin square, you can make a table of its cells by listing the row, column,
and symbol for each:
1 2
2 1
−→
r c s
1 1 1
1 2 2
2 1 2
2 2 1
By thinking of the rows of this table as a code, prove that An(3, 2) ≥ n2.
Solution:
(a) Here’s an example with nine words, which is the biggest code possible (as we’ll see in
the last exercise proof!) {0000, 0111, 0222, 1012, 1120, 1201, 2021, 2102, 2210} .
You only need four codewords here, so any four of the above (or any other set of four
words that you’ve found!) can work.
(b) For (i), there are many ways to go. The simplest is probably to list the numbers 1, 2, . . . n
at the top row, and then shift this row one over repeatedly n times:
1 2 3 . . . n-2 n-1 n
2 3 4 . . . n-1 n 1
3 4 5 . . . n 1 2
…
…
…
…
…
…
…
n 1 2 . . . n-3 n-2 n-1
For (ii), just observe that our “no repeats” property means that if we have any two
distinct triples (r1, c1, s1), (r2, c2, s2) in our code, we know that if r1 = r2, we must have
c1 6= c2 (each cell shows up once) and s1 6= s2 (no repeated symbols in any row). Similarly,
if we have c1 = c2, we must have s1 6= s2 by the same logic. As such, it is impossible for
(r1, c1, s1) and (r2, c2, s2) to agree in more than one place, and thus the distance of the
code generated by these tables is at least 2.
This, along with (i), proves that An(3, 2) ≥ n2: we’ve made a table with n2 rows, and
those rows are a length-3 n-ary code with distance 2.
5
4. (Number theory and RSA.)
(a) In class, we said when we choose the public exponent e, we tended to reuse the same
values: i.e. e = 3 or e = 65537 are common choices.
Suppose that you instead picked e by taking a uniformly-chosen random value from 1 to
ϕ(n), where n = pq is your public base. Show that at least 50 % of the time, the value
of e you choose is one for which the RSA algorithm cannot be ran.
(b) In the RSA algorithm, our first step involves choosing a pair of large prime numbers p, q.
Suppose you picked p = q: i.e. you reused the same large prime for q, and believed1 that
this would make ϕ(n) = ϕ(p2) = (p− 1)2.
Will the RSA process still work: i.e. will you always be able to find a value of d, and will
(M e)
d
= M mod n always hold? Or will it fail (and if so, why?)
Solution:
(a) This one is pretty quick. Observe that in RSA, p and q are a pair of distinct prime
numbers. In particular, this means that at least one of p, q must be odd, as there is only
one even prime (namely, 2.) Therefore, ϕ(n) = (p− 1)(q − 1) is always even.
If we choose a value of e uniformly from 1 to ϕ(n), we have a 50 % chance of choosing an
even value of e. If we do so, then e−1 mod ϕ(n) will not exist: for any integers d, k, we
have that ed+ kϕ(n) is an even number, and thus we cannot find a value of d such that
ed ≡ 1 mod ϕ(n). But this means that we cannot find the private exponent d = e−1
mod ϕ(n) needed for RSA!
(b) This will often not work. The process of finding d will still function just fine: as long as
e is not a factor of p− 1, then d = e−1 mod ϕ(n) will exist.
However, the decryption step can go wrong. Note that if ϕ(n) = (p − 1)2 and n = p2,
then because ed ≡ 1 mod ϕ(n), we can write ed = 1 + k(p− 1)2. This means that
(M e)
d
= M ed = M1+k(p−1)
2
= Mkp
2−2kp+k+1 = Mk(p
2−1)−2kp+2k+1 =
(
Mp
2−1
)k
M2k(p−1)M.
This, sadly, is not equal to M for most values of M , p. You can try to simplify it
down further, but Fermat’s little theorem won’t be of too much use (it only tells you
that Mp−1 = 1 mod p; i.e. you don’t get information about M mod p2 − 1), and if
you experimentally try out a few values you’ll see that this frequently doesn’t work. To
illustrate this by randomly picking values: let’s choose p = 4, e = 2,M = 3. This means
that p2 = 16, (p− 1)2 = 9, d = 5 and thus that M ed mod p2 = 310 mod 16 = 9. This is
not 3, so this doesn’t work here!
There are occasions where this will accidentally work out, but in general this process isn’t
going to lead you to M , and thus this is not a good implementation of RSA.
1Note that this calculation isn’t right: if you look up the definition of ϕ, you can see that ϕ(p2) = p(p − 1), as
ϕ(n) should be “the number of positive integers relatively prime to and less than n.” You don’t need to know how to
calculate ϕ(n) for any values other than n = pq in this class, as we haven’t gone through this definition: this footnote
is just a FYI for future studies!
6
https://en.wikipedia.org/wiki/Euler’s_totient_function
5. (Logic and proofs.)
(a) Let f : R → R be a function. Express the negation of the following statements without
using any words of negation or the symbol ¬. ( 6= is fine, though!)
� A: ∀x ∈ R,∃y ∈ R such that f(x) = y.
� B: ∃y ∈ R, ∀x ∈ R such that f(x) = y.
Prove that B implies A. Does A imply B?
(b) Create a truth table for the compound proposition (p→ q) ∧ (r ↔ (¬r)). Is this propo-
sition logically equivalent to (p ∧ q) ∧ r?
Solution:
(a) We first write down the negations of these statements here:
� A translates as follows: “Not(For any real number x, there is a real number y such
that f(x) = y.)” This simplifies to “There is some real number x such that for all
real numbers y, f(x) 6= y,” because negating a quantifier “flips” it (i.e. the ∃,∀’s
flip)
� B similarly translates to “For any real number y, there is a real number x such that
f(x) 6= y.”
We now return to the original statements, and prove that B implies A. This is not too
hard to see: B says that there is one value of y, such that for all x ∈ R, f(x) = y. If this
is true, let’s write down that one value of y, and call it “Special-Y” so we don’t forget
what it is.
Now, let’s look at A, which says that for any x in R, we want a value of y such that
f(x) = y. This is now true! Take any x ∈ R. We know that f(x) = our “Special-Y”
value from earlier, so if we let y be that “Special-Y” value, we’ve proven that A holds!
The other direction, however, fails. Consider the function f : R→ R given by f(x) = x2.
For any x ∈ R, there is a y ∈ R, namely y = x2, such that f(x) = y; however, there is
no single y ∈ R that you can pick out ahead of time such that for every x, f(x) = y;
this is because f(x) takes on multiple values, as f(0) = 0, f(1) = 12, and y cannot have
multiple values!
(b) As described in class, we create a truth table:
p q r p→ q ¬r r ↔ (¬r) (p→ q) ∧ (r ↔ (¬r))
F F F T T F F
F F T T F F F
F T F T T F F
F T T T F F F
T F F F T F F
T F T F F F F
T T F T T F F
T T T T F F F
Notice that this proposition always outputs false, no matter what inputs it is given!
Therefore, it cannot be equivalent to any proposition that can output true values, like
(p ∧ q) ∧ r (which is true when p, q, r are all true.)
7
6. (Induction and recurrence relations.)
(a) Two difference equations (i.e. recurrence relations) are given below. Find the general
solutions to each.
i. xn + 2xn+1 − 3xn+2 = 4
ii. 3yn − yn+1 = n · 9n
(b) Define the values an recursively by setting a0 = 0, a1 = 1 and an = an−1 − an−2 for all
n ≥ 2.
Use induction to prove that if n is a multiple of 3, then an is even.
(c) Find every logical flaw in the following proof. Explain why the flaws you’ve found are
indeed logical flaws.
Claim: Take any positive integer n. Then, if x, y are a pair of positive integers such
that max(x, y) = n, then x = y.
Proof. We proceed by induction on n.
Our base case is when n = 1. In this case, the only two positive integers x, y such
that max(x, y) = 1 are precisely x = 1, y = 1, in which case our claim that x = y
holds.
We proceed to the inductive step. Here, we assume that our claim holds for all values
up to some n, and seek to prove that it holds for n+ 1 as well.
To be specific: our claim for n + 1 is that if we take any two positive integer x, y
such that max(x, y) = n+ 1, then x = y must hold. To see why this is true, look at
x − 1, y − 1. Because we’ve decreased both x, y by 1, their maximum has decreased
by 1 as well; therefore maxx− 1, y − 1 = n.
But we know by our inductive hypothesis that if the maximum of two numbers is
n, then they must be equal! In other words, the inductive assumption tells us that
x− 1 = y − 1, and thus that x = y as desired.
Solution:
(a) We use the methods from class (see Amal’s lectures for week 9 and Monday, week 10, the
practice problems posted in week 9, and also this link for many more worked examples!
Specifically: let’s start with (i) Here, we have xn + 2xn+1 − 3xn+2 = 4. To begin, we
solve the “homogeneous” form of this equation, i.e. the one in which we have all of our
sequence terms on the left, the other bits on the right, and replace those other bits with
0: i.e. xn + 2xn+1 − 3xn+2 = 0. We do this by “guessing” that our equation will have
a solution of the form xn = Kx
n for some constants K,x. If we make such a guess and
plug it in, our equation is
0 = Kxn + 2Kxn+1 + 3Kxn+2
⇒0 = 3×2 − 2x− 1
if we divide by Kxn and then multiply by −1. This equation has roots given by the
quadratic equation
2±
√
4 + 12
6
= 1,−
1
3
. As such, K1(1)
n + K2
(
−1
3
)n
is our solution
to the homogeneous part of our equation (if we get multiple possible values of x through
this process, the overall solution is the sum of those individual solutions.)
Now, we solve the “particular” part of our solution. When we do this, we look at the
right-hand-side and guess a form for the solution that matches it. Amal gave a table
for these correspondences in class; you can also find it here. In this case, our RHS is
8
http://web.cs.wpi.edu/~cs504/s00m/notes/recurrence/solve/solve.html
http://web.cs.wpi.edu/~cs504/s00m/notes/recurrence/solve/step2/step2.html
a constant, so we would guess a constant solution: i.e. xn = D for some constant D.
Plugging this in yields D + 2D − 3D = 4, i.e. 0 = 4; a problem! In general, you cannot
try a particular solution that is also one of the homogeneous solutions (as we saw above,
K2 is a homogeneous solution) because plugging that in yields 0.
Instead, if you’re in this situation, try multiplying your guess by n. In our case, this
means that we’re guessing xn = Dn, and thus have Dn+ 2D(n+ 1)− 3D(n+ 2) = 4, i.e.
2D − 6D = 4, i.e. D = −1, and thus have −n as a particular solution.
To finish, just add your homogeneous and particular solutions together. This gives you
K1(1)
n +K2
(
−
1
3
)n
− n as your general solution, for any constants K1,K2.
For (ii), we proceed in the same way. The homogeneous form of 3yn − yn+1 = n · 9n is
3yn − yn+1 = 0. If we guess that the solution here is Kyn, we get 3(Kyn)−Kyn+1 = 0,
which is just 3 − y = 0 if we divide by Kyn. This gives us K3n as our homogeneous
solution.
Now, we look at the particular part of our solution. Here, our right-hand-side is n9n, and
thus a solution that would “match” this in form is one of the form 9n(An + B). If we
plug this in to our equation, we get
n9n = 3 · 9n(An+B)− 9n+1(A(n+ 1) +B)
⇒ n9n = n9n(3A− 9A) + 9n(3B − 9A− 9B)
⇒ −6A = 1,−6B − 9A = 0
from which we can conclude that A = −1
6
, B = 1
4
, and thus that our particular solution
is 9n
(
1
4
− n
6
)
.
In total, then, our overall general solution is K3n + 9n
(
1
4
−
n
6
)
, for any constant K.
(b) We proceed by induction, where our claim P (n) is the statement “a3n is even.”
For our base cases, we check the first few entries of our sequence:
� 0 is a multiple of 3; in this case, a0 = 0 is indeed even.
� 1, 2, are not multiples of 3, so we don’t necessarily care about what happens here.
Still, out of curiosity, we can check and see that a1 = 1 and a2 = a1− a0 = 1− 0 = 1
are both odd.
� At 3, we have that a3 = a2 − a1 = 1− 1 = 0, and so is indeed even.
� At 4,5, we have that a4 = a3 − a2 = 0− 1 = −1, a5 = a4 − a3 = (−1)− 0 = −1 are
both odd.
� At 6, we have that a6 = a5−a4 = (−1)− (−1) = 0 is again even (and indeed is again
0!)
� At 7, 8, we have that a7 = a6 − a5 = 0− (−1) = 1 and a8 = a7 − a6 = 1− 0 = 1; so
they’re again odd.
It looks like our sequence has a nice pattern: indeed, if we were asked to find by induction
what all of the terms in this sequence are, it looks like the pattern
0, 1, 1, 0,−1,−1, 0, 1, 1, 0,−1,−1, 0, 1, 1, 0,−1,−1, 0, 1, 1 . . .
seems to always hold!
If you wanted, you could complete this problem by proving that this holds, again via
induction. For now, though, we’ll stick with our original claim. We’ve proven P (n)’s
base cases; we now proceed via induction, and seek to prove that if P (n) holds, then
P (n+ 1) also holds.
9
So: if P (n) holds, then a3n is even. We know that by definition a3n = a3n−1 − a3n−2; as
a result, we must have that either a3n−1, a3n−2 are both even or both odd.
If they’re both even, then a3n+1 = a3n − a3n−1 is even-even = even, which implies that
a3n+2 = a3n+1 − a3n is also even-even = even, which implies that a3n+3 = a3n+2 − a3n+1
is also even-even = even. In other words, P (n+ 1) holds!
If they’re both odd, however, then a3n+1 = a3n−a3n−1 is even-odd = odd, which implies
that a3n+2 = a3n+1− a3n is odd-even =odd, which implies that a3n+3 = a3n+2− a3n+1 is
odd-odd=even. In other words, P (n + 1) holds in this case as well, so we’ve proven our
claim!
(c) The logical flaw in our proof comes in the inductive step! Specifically, look at the line
where we said
“To see why this is true, look at x− 1, y − 1. Because we’ve decreased both x, y by 1,
their maximum has decreased by 1 as well; therefore maxx− 1, y − 1 = n.
But we know by our inductive hypothesis that if the maximum of two numbers is n, then
they must be equal!”
In this line, we’ve assumed that we can apply our inductive assumption to the pair
x − 1, y − 1. This is not correct! Our inductive assumption only applied to all pairs of
positive integers x, y. However, the values x−1, y−1, may not be positive. If they aren’t,
then this application of the inductive hypothesis will fail!
To give an example, if x = 1, y = 2 then max(1, 2) = 2 and yet 1 6= 2. This can happen
without “breaking” induction because (x − 1, y − 1) = (0, 1) is not a pair of positive
integers, and so when we reduced our larger case we did not do so in a way that will
eventually reach one of our base cases (and thus our proof fails.)
10
7. (Relations.)
(a) For any two natural numbers n, k ∈ N, let C(n, k) denote the number of ways to choose
k unordered objects from a set of n distinct objects without repeats, and let P (n, k)
denote the number of ways to choose k ordered objects from a set of n distinct objects
without repeats.
Define a relation ∼ on N×N as follows: we say that n ∼ k holds if and only if C(n, k) =
P (n, k).
Prove that ∼ is not an equivalence relation.
(b) Let Σ be an alphabet and w1, w2 be a pair of words in Σ
∗, the set of all words over the
alphabet Σ. We say that w1 is a substring of w2 if we can create w1 by taking w2 and
deleting some symbols from either the start or end (or both!) of w2. For example, the
following four strings are each substrings of abbaa:
� ba � abba � λ � abbaa
Prove that “is a substring of” is a poset relation on Σ∗.
Solution:
(a) First, notice that as shown in class, for any n ≥ k
� C(n, k) =
(
n
k
)
= n!
k!(n−k)! , while
� P (n, k) = n!
(n−k)! ,
and for k > n both C(n, k) and P (n, k) = 0.
Therefore, C(n, k) = P (n, k) holds if and only if we’re in the following situations:
� Either k > n, in which case both C(n, k) and P (n, k) are both 0 and thus equal.
� Otherwise, if k ≤ n, then C(n, k) = P (n, k) holds if and only if n!
k!(n−k)! =
n!
(n−k)! .
Dividing by n! and multiplying through by k! · (n− k)! yields 1 = k!, which holds if
and only if k is 0 or 1.
Therefore, our relation holds for precisely the following pairs, and no others:
� n ∼ k for every k > n.
� n ∼ 1 for every n.
� n ∼ 0 for every n.
Notice that this means that ∼ cannot be reflexive! For instance, 2 6∼ 2, and in general
n 6∼ n for any n ≥ 2. (The fast version of this proof is to just start your proof here: i.e.
just notice that C(2, 2) =
(
2
2
)
= 1 and P (2, 2) = 2!
0!
= 2 are different, and therefore 2 6∼ 2
and we’re not reflexive.)
∼ is also not symmetric, if you wanted to break things that way: 2 ∼ 3, for instance,
because C(2, 3) and P (2, 3) are both 0, while 3 6∼ 2 because
(
3
2
)
= 3!
1!2!
= 3 and 3!
1!
= 6.
Finally, ∼ is also not transitive, if that’s the way you wanted to break this relation! (You
only need to show that just one of these properties fails to make ∼ not an equivalence
relation: i.e. any one of these three would be sufficient for a proof.) You can see that
2 ∼ 0 and 0 ∼ 2, as noted before, but 2 6∼ 2.
(b) To show that something is a poset, we simply check the three defining properties of a
poset:
� Reflexivity: We seek to show that for any word w ∈ Σ∗ that w is a substring of
itself. This is trivially true, as any word contains itself as a substring!
11
� Antisymmetry: We seek to show that if w1, w2 are a pair of words such that
w1 6= w2 and w1 is a substring of w2, then w2 is not a substring of w1.
To see why, notice that if w1 6= w2 and w1 is a substring of w2, then (1) we can create
w1 by deleting characters from the front and end of w2, and (2) when doing so we
delete at least one character (as otherwise they’d be equal.)
But this means that w1 contains strictly less characters than w2! As a result, we
cannot have w2 as a substring of w1, as it is impossible to remove characters from
w1 and wind up with a strictly longer string.
� Transitivity: We seek to show that if w1, w2, w3 are three strings such that w1 is a
substring of w2 and w2 is a substring of w3, then w1 is a substring of w3.
To see why, simply take w3 and delete characters from its start and end until it is
w2; we can do this by definition. Then keep going; i.e. delete characters from the
front and end of this w2 until we have w1, which we can again do by definition.
The result of this process is that we’ve deleted characters from the front and end of
w3 to get a w1; i.e. that w1 is a substring of w3, as desired.
12
8. (Functions.)
(a) Let c be a value in {0, 1, 2, 3}.
Suppose that f : {0, 1, 2, 3} → {0, 1, 2, 3} is defined by the rule f(x) = y if cx ≡ y mod 4.
Find all values of c such that f has an inverse.
(b) Let X,Y, Z be sets and f : X → Y , g : Y → Z be a pair of functions. Suppose that g ◦ f
is surjective. Prove that g is surjective.
Solution:
(a) As seen in class, a function f : A → B has an inverse if and only if f is both injective
and surjective. Our function f : {0, 1, 2, 3} → {0, 1, 2, 3} is defined by the rule f(x) = y
if cx ≡ y mod 4; so, if we want to find the values of c that make f have an inverse, we just
need values of c that make f both injective and surjective! We do this by just looking at
all of the possible values of c.
� If c = 0, then f(0) = 0, f(1) = 0, f(2) = 0, and f(3) = 0. Why? Well, for any
x ∈ {0, 1, 2, 3}, cx is zero, and so 0 ≡ y mod 4 means that y is a multiple of 4.
The only multiple of 4 in {0, 1, 2, 3} is 0; so we have that for any x, cx ≡ y mod 4 if
and only if y = 0.
But this means that f(x) = 0 for every x ∈ {0, 1, 2, 3}. In particular this means that
our function is not surjective (there is no value of x that maps to y=1.) Therefore f
does not have an inverse if c = 0.
� If c = 1, then for any x ∈ {0, 1, 2, 3} we have that f(x) = x because 1 · x ≡ x mod 4.
As a result, f(x) is injective (for any y ∈ {0, 1, 2, 3}, there is at most one x ∈
{0, 1, 2, 3} such that f(x) = y) and surjective (for any y ∈ {0, 1, 2, 3}, there is at least
one x ∈ {0, 1, 2, 3}, namely x = y, such that f(x) = y), so we have an inverse.
� If c = 2, then f(0) = 0 because 2 · 0 = 0 mod 4, f(1) = 2 because 2 · 1 = 2 mod 4,
f(2) = 0 because 2 · 2 = 0 mod 4, and f(3) = 2 because 2 · 3 = 2 mod 4. In
particular this function is not injective (because it maps x = 0 and x = 2 to the
same y-value 0), and thus does not have an inverse.
� If c = 3, then the same reasoning as above tells us that f(0) = 0, f(1) = 3, f(2) = 2
and f(3) = 1. So f is injective and surjective (for any y ∈ {0, 1, 2, 3} there is exactly
one x ∈ {0, 1, 2, 3} such that f(x) = y, according to our results), and thus has an
inverse.
(b) As we often do, we start by expanding our definitions:
� We’re assuming that the function g ◦ f : X → Z is surjective. That is: we know that
for any z ∈ Z, there is at least one x ∈ X such that g(f(x)) = z.
� We want to show that the function g must be surjective. That is: we want to show
that for any z ∈ Z, there is at least one y ∈ Y such that g(y) = z.
So: if we want to prove that something holds for any z ∈ Z, we should start our proof
by writing “Take any z ∈ Z.”
The next step of our proof is the tricky part: we need to find a y ∈ Y such that g(y) = z.
How can we do this?
Well: if we look at our assumption, we know that for any z ∈ Z, we can find a x ∈ X
such that g(f(x)) = z. In other words, if we let y = f(x), we have found a y such that
g(y) = g(f(x)) = z! This completes our proof, as desired.
13
9. (Enumeration.)
(a) Let A = {n ∈ N | n ≡ 0 mod 5, n ≤ 1000}, B = {n ∈ N | n ≡ 0 mod 11, n ≤ 1000}, and
C = {n ∈ N | n ≡ 0 mod 2, n ≤ 1000}. Use the inclusion-exclusion principle to count
the number of elements in A ∪B ∪ C
(b) Suppose that A = {1, 2, . . . , 40}, and S is any subset of A containing at least 21 elements.
Prove that there are two elements a, b ∈ S such that a divides b.
Solution:
(a) For shorthand, let Ak denote the collection of all numbers that are a multiple of k from
the set {0, 1, . . . 1000}. By the inclusion-exclusion principle, we know that
|A2 ∪A5 ∪A11| = |A2|+ |A5|+ |A11| − (|A2 ∩A5|+ |A2 ∩A11|+ |A5 ∩A11|) + |A2 ∩A5 ∩A11|.
Also, note that for any k, l, we have Ak ∩ Al is the set of all numbers that are multiples
of both k or l! By definition, a number is a multiple of both k and l if and only if
it’s a multiple of the least common multiple of k, l. = ALCM(k,l); so we have Ak ∩ Al =
ALCM(k,l)! In particular, this tells us that A2∩A5 = A10, A2∩A11 = A22, A5∩A11 = A55
and A2 ∩A5 ∩A11 = A110.
Finally, we know that Ak = 1 +
⌊
1000
k
⌋
; this is because our natural numbers start at 0
(which is where the 1+ comes from) and between 1 to n, we have
⌊
n
k
⌋
multiples of k. (For
instance, there are 4 multiples of 3 in the set {0, 1, 2, . . . 10}, namely 0,3,6,9; our formula
counts this correctly, as 1 +
⌊
10
3
⌋
= 4.)
So, we have
|A2 ∪A5 ∪A11| = |A2|+ |A5|+ |A11| − (|A2 ∩A5|+ |A2 ∩A11|+ |A5 ∩A11|) + |A2 ∩A5 ∩A11|
= |A2|+ |A5|+ |A11| − |A10| − |A22| − |A55|+ |A110|
=
(
1 +
⌊
1000
2
⌋)
+
(
1 +
⌊
1000
5
⌋)
+
(
1 +
⌊
1000
11
⌋)
−
(
1 +
⌊
1000
10
⌋)
−
(
1 +
⌊
1000
22
⌋)
−
(
1 +
⌊
1000
55
⌋)
+
(
1 +
⌊
1000
110
⌋)
= 501 + 201 + 91− 101− 46− 19 + 10 = 637 .
(b) This is a pigeonhole proof! (The tipoff here is that we have a problem where we’re
picking or selecting some big collection of elements, and then we’re hoping to conclude
that amongst our choices there is some sort of “collision:” in this case, that we’re forced
to pick two elements such that one divides the other. In particular, situations where
you’re forced to take more than half of the possible choices, or more than a quarter, or
something else like that, are very often pigeonhole-ish problems.)
To do this, we need to decide what our “pigeons” are and what our “holes” are:
� The pigeons are relatively straightforward to find: because we’re picking 21 elements
from A, we can think of the 21 things we’re picking as our pigeons! (In general, look
at what you’re picking: this are the “pigeons” of any pigeonhole proof.)
� The “holes” are typically harder to find. The always correspond to some partition
(i.e. way to group together in disjoint piles) the elements of the set we’re picking our
pigeons from, so that if we pick two pigeons from any one hole the conclusion of the
proof follows.
In this case, our holes should be some way to break apart A = {1, 2, . . . 40} into
disjoint sets, so that if we take any two elements a, b from one of these sets we get
that a|b or vice-versa!
Finally, if we want pigeonhole to work, the number of holes should be less than the
number of pigeons (so that we’re forced to pick two pigeons from one hole.)
14
So: we want to break up A into 20 sets, so that for any a, b from one of those sets, either
a|b or vice-versa. How can we do this? Well: consider the sets U2k+1 = {a ∈ A | ∃n ∈
N, a = (2k+ 1) · 2n}, formed by taking an odd number 2k+ 1 along with all multiples of
that number by a power of two.
For example U1 = {1, 2, 4, 8, 16, 32}, U3 = {3, 6, 12, 24}, and U5 = {5, 10, 20, 40}.
If we take any two numbers (2k + 1)2n, (2k + 1)2m, from one of these sets, clearly one
divides the other; so they are suitable “holes” for our proof.
There are also clearly 20 such sets, as there is one set for every odd number in {1, 2, . . . 40}.
So, by the pigeonhole property, we’re done!
(Note: coming up with these sets U2k+1 is a pretty clever trick / not one I’d expect
people to do on the fly! I mention it because (1) it’s neat and (2) seeing it helps you
appreciate more straightforward pigeonhole exercises, in much the same way that lifting
heavy weights makes you better at lifting smaller weights.)
15