Draw a Venn diagram and decide region by region what belongs to the set expression.
For counting problems, fill in the regions from the centre outwards: all sets, then pairs, then single sets, then the outside.
Use inclusion–exclusion as a check: |A ∪ B| = |A| + |B| − |A ∩ B|.
For a relation, test each property on every pair and give one counterexample when it fails.
For a function, count the arrows arriving at each element of B: at most one means injective, at least one surjective.
Graph theory
Handshake lemma
Σ deg(v) = 2|E|
Complete graphs
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Regular graph
|E| = n·k/2
Tree and forest
|E| = n − 1, |E| = n − c
Leaves of a tree
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler
circuit: all degrees even; path: exactly 2 odd degrees
Hamilton circuits in Kn
(n − 1)!/2
Dijkstra update
d(v) = min(d(v), d(u) + w(u, v))
Walks of length L
(Mᴸ)ij
Method
Write down the degree of every vertex; the degrees add up to twice the number of edges.
For Euler questions, check that the graph is connected and count the vertices with odd degree.
For trees, use n − 1 edges and the handshake lemma.
For Dijkstra, keep a table of tentative distances and settle the smallest unsettled vertex each round.
For a minimum spanning tree, sort the edges by weight and skip every edge that closes a cycle (Kruskal), or grow one tree from a start vertex (Prim).
Number theory & modular arithmetic
Division with remainder
a = q·n + r, 0 ≤ r < n
Euclid
gcd(a, b) = gcd(b, a mod b)
Least common multiple
lcm(a, b) = a·b/gcd(a, b)
Inverse
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Linear congruence
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Euler’s totient
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
Method
Reduce every number modulo n first; remainders lie between 0 and n − 1.
For a gcd, divide repeatedly with Euclid’s algorithm; the last nonzero remainder is the gcd.
For an inverse, run the extended algorithm and keep the coefficient of a; add n if it is negative.
Solve a·x ≡ b by multiplying with a⁻¹; combine two congruences by writing x = r₁ + m₁k.
For powers, write the exponent in binary and square repeatedly; in RSA, d = e⁻¹ mod φ(n) with φ(n) = (p − 1)(q − 1).
2Practice problems
1.Propositional logic & proofsMedium
Which formula is logically equivalent to ¬(b ∧ a)? Click it.
¬(b ∧ a)
1¬b ∧ a
2¬b ∧ ¬a
3¬b ∨ ¬a
4¬b ∨ a
2.Propositional logic & proofsHard
The argument with premises r ∨ q; r and conclusion ¬q is invalid. Click the row of the truth table that is a counterexample.
r ∨ qr∴ ¬q
1q = 1, r = 1
2q = 1, r = 0
3q = 0, r = 1
4q = 0, r = 0
3.Sets, relations & functionsMedium
R = {(1, 2), (2, 2), (3, 4), (4, 1)} is a relation on {1, 2, 3, 4}. What is the smallest number k of ordered pairs that must be added to R to make it transitive (the size of the transitive closure minus |R|)?
R = {(1, 2), (2, 2), (3, 4), (4, 1)}
k =
4.Sets, relations & functionsHard
An equivalence relation R on {1, …, 9} has the classes {2, 4}, {7, 8}, {3, 6}, {1, 5, 9}. How many ordered pairs does R contain? Call the number |R|.
{2, 4}{7, 8}{3, 6}{1, 5, 9}
|R| =
5.Graph theoryMedium
A connected graph has 12 vertices and 18 edges. How many edges k must be removed to leave a spanning tree?
|V| = 12|E| = 18
k =
6.Graph theoryHard
How many walks of length 2 go from A to B? A walk may repeat vertices and edges. Call the number N.
M = adjacency matrixL = 2
N =
7.Number theory & modular arithmeticMedium
Find the smallest positive integer x with x ≡ 4 (mod 10) and x ≡ 9 (mod 13).
x ≡ 4 (mod 10)x ≡ 9 (mod 13)
x =
8.Number theory & modular arithmeticHard
37 is prime. Use Fermat’s little theorem to find 1755876 mod 37.
p = 37k = 55876
1755876 mod 37 =
3Solutions
1.Propositional logic & proofs
Answer: ¬b ∨ ¬a
Logical equivalence: two formulas are equivalent (≡) when they have the same value in every row of the truth table. A tautology is 1 in every row, a contradiction is 0 in every row, and a contingency is neither. Useful laws: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b and ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (contrapositive); ¬(a → b) ≡ a ∧ ¬b; and the distributive laws, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
The law
De Morgan: ¬(a ∧ b) ≡ ¬a ∨ ¬b. The ∧ turns into ∨ and both parts are negated.
¬(b ∧ a) ≡ ¬b ∨ ¬a
Check with the truth table
a = 1, b = 1: 0 | 0 0 0 1
a = 1, b = 0: 1 | 1 0 1 1
a = 0, b = 1: 1 | 0 0 1 0
a = 0, b = 0: 1 | 0 1 1 1
Answer
¬b ∨ ¬a
The columns after the bar are the options in the order shown.
2.Propositional logic & proofs
Answer: q = 1, r = 1
Quantifiers and arguments: ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x). Move a negation inwards, swap every quantifier it passes, and negate the inner formula with the propositional laws, such as ¬(a → b) ≡ a ∧ ¬b. An argument is valid when the conclusion is 1 in every row in which all premises are 1. A single row with true premises and a false conclusion is a counterexample and shows the argument is invalid.
Premises and conclusion row by row
q = 1, r = 1: 1 1 | 0
q = 1, r = 0: 1 0 | 0
q = 0, r = 1: 1 1 | 1
q = 0, r = 0: 0 0 | 1
Counterexample
q = 1, r = 1
Answer
q = 1, r = 1
An argument with this form looks like a valid rule, but one row is enough to show that it is not.
3.Sets, relations & functions
Answer: k = 3
Relations: a relation R on a set X is a set of ordered pairs (x, y). R is reflexive when (x, x) ∈ R for every x in X; symmetric when (x, y) ∈ R always comes with (y, x) ∈ R; antisymmetric when (x, y) and (y, x) are both in R only if x = y; and transitive when (x, y) and (y, z) in R force (x, z) ∈ R. An equivalence relation is reflexive, symmetric and transitive, and splits X into disjoint classes.
Pairs to add
{(3, 1), (3, 2), (4, 2)}
Count
k = 3
Answer
k = 3
4.Sets, relations & functions
Answer: |R| = 21
Relations: a relation R on a set X is a set of ordered pairs (x, y). R is reflexive when (x, x) ∈ R for every x in X; symmetric when (x, y) ∈ R always comes with (y, x) ∈ R; antisymmetric when (x, y) and (y, x) are both in R only if x = y; and transitive when (x, y) and (y, z) in R force (x, z) ∈ R. An equivalence relation is reflexive, symmetric and transitive, and splits X into disjoint classes.
Pairs per class
|R| = 2² + 2² + 2² + 3² = 21
Answer
|R| = 21
5.Graph theory
Answer: k = 7
Euler, Hamilton and trees: a connected graph has an Euler circuit (every edge once, back to the start) when every vertex has even degree, and an Euler path that is not a circuit when exactly two vertices have odd degree; the path then runs from one odd vertex to the other. A Hamilton circuit visits every vertex once; Kn has (n − 1)!/2 of them. A tree on n vertices has n − 1 edges, and a connected graph with m edges keeps a spanning tree after removing m − n + 1 edges.
Edges of a spanning tree
12 − 1 = 11
Edges to remove
k = 18 − 11 = 7
Answer
k = 7
6.Graph theory
Answer: N = 1
Degrees: the degree of a vertex is the number of edges that meet it. Every edge has two ends, so the degrees add up to twice the number of edges: Σ deg(v) = 2|E| (the handshake lemma). The number of vertices with odd degree is therefore even. Kn has n(n − 1)/2 edges, a k-regular graph on n vertices has nk/2, and a tree on n vertices has n − 1 edges.
Adjacency matrix
A: 0 1 1 0 0
B: 1 0 1 1 1
C: 1 1 0 0 0
D: 0 1 0 0 1
E: 0 1 0 1 0
Common neighbours
(M²)AB = 0·1 + 1·0 + 1·1 + 0·1 + 0·1 = 1
Answer
N = 1
7.Number theory & modular arithmetic
Answer: x = 74
Inverses and congruences: a has an inverse modulo n exactly when gcd(a, n) = 1. The extended Euclidean algorithm writes 1 = s·n + t·a, and then a⁻¹ ≡ t (mod n). A congruence a·x ≡ b (mod n) with gcd(a, n) = 1 has the solution x ≡ a⁻¹·b. Two congruences x ≡ r₁ (mod m₁) and x ≡ r₂ (mod m₂) with coprime moduli have one solution modulo m₁·m₂ (Chinese remainder theorem). Euler’s φ(n) counts the numbers from 1 to n that are coprime to n: φ(n) = n·∏(1 − 1/p).
First congruence
x = 4 + 10k
Second congruence
4 + 10k ≡ 9 (mod 13) → 10k ≡ 5 (mod 13)
k ≡ 4·5 ≡ 7 (mod 13)
Result
x = 4 + 10·7 = 74
x = 74
check: 74 mod 10 = 4, 74 mod 13 = 9
Answer
x = 74
8.Number theory & modular arithmetic
Answer: 1755876 mod 37 = 12
Modular powers and RSA: compute aᵏ mod n by repeated squaring: write k in binary, square, reduce after every step and multiply the powers whose bit is 1. Fermat: aᵖ⁻¹ ≡ 1 (mod p) for a prime p not dividing a, so the exponent can be reduced modulo p − 1. RSA: choose primes p and q, n = p·q and φ(n) = (p − 1)(q − 1); the public exponent e is coprime to φ(n), and the private exponent is d = e⁻¹ mod φ(n). Encrypt with c = mᵉ mod n and decrypt with m = cᵈ mod n.