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 ¬(a ↔ c)? Click it.
¬(a ↔ c)
1a ↔ ¬c
2¬a ∨ ¬c
3¬a ↔ ¬c
4a ∧ ¬c
2.Propositional logic & proofsHard
How many of the 16 rows of the truth table make ¬(r ∧ (s → p)) ∧ ¬(¬p ↔ (q ∧ s)) true? Call this number N.
¬(r ∧ (s → p)) ∧ ¬(¬p ↔ (q ∧ s))
N =
3.Sets, relations & functionsMedium
In a group of 50 students, 32 speak French (F), 20 speak German (G) and 18 speak Spanish (S). 16 speak French and German, 7 French and Spanish, 5 German and Spanish, and 3 speak all three. How many are in none of the three sets?
|U| = 50
|(F ∪ G ∪ S)′| =
4.Sets, relations & functionsHard
The functions f and g on {1, 2, 3, 4, 5} are given by their tables. Find (f ∘ g)(5).
A connected graph has 8 vertices and 13 edges. How many edges k must be removed to leave a spanning tree?
|V| = 8|E| = 13
k =
6.Graph theoryHard
Dijkstra’s algorithm runs from A. Click the vertex that is settled (made permanent) in round 3; A itself is round 1.
start: Around 3
1A
2B
3C
4D
5E
6F
7.Number theory & modular arithmeticMedium
Find the smallest positive integer x with x ≡ 3 (mod 9) and x ≡ 1 (mod 11).
x ≡ 3 (mod 9)x ≡ 1 (mod 11)
x =
8.Number theory & modular arithmeticHard
How many solutions N does 6x ≡ 10 (mod 14) have in {0, 1, …, 13}?
6x ≡ 10 (mod 14)
N =
3Solutions
1.Propositional logic & proofs
Answer: a ↔ ¬c
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
¬(a ↔ b) is 1 exactly when a and b differ, which is a ↔ ¬b.
¬(a ↔ c) ≡ a ↔ ¬c
Check with the truth table
a = 1, c = 1: 0 | 0 0 1 0
a = 1, c = 0: 1 | 1 1 0 1
a = 0, c = 1: 1 | 1 1 0 0
a = 0, c = 0: 0 | 0 1 1 0
Answer
a ↔ ¬c
The columns after the bar are the options in the order shown.
2.Propositional logic & proofs
Answer: N = 5
Truth tables: a formula with n different variables has 2ⁿ rows, one for every combination of truth values (1 = true, 0 = false). Work from the inside out and give every subformula its own column. ¬a flips the value; a ∧ b is 1 only when both are 1; a ∨ b is 0 only when both are 0; a → b is 0 only when a = 1 and b = 0; a ↔ b is 1 when both sides are equal.
Columns
s → p; r ∧ (s → p); ¬(r ∧ (s → p)); ¬p; q ∧ s; ¬p ↔ (q ∧ s); ¬(¬p ↔ (q ∧ s)); ¬(r ∧ (s → p)) ∧ ¬(¬p ↔ (q ∧ s))
Split on p
p = 1: 1
p = 0: 4
N = 1 + 4 = 5
Answer
N = 5
3.Sets, relations & functions
Answer: |(F ∪ G ∪ S)′| = 5
Sets and Venn diagrams: A ∪ B holds the elements in A or B (or both), A ∩ B the elements in both, A − B the elements of A that are not in B, and the complement A′ everything in U that is not in A. In a Venn diagram every set expression is a union of regions, so count it region by region. Inclusion–exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|, and |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
Centre and pairs
F ∩ G ∩ S: 3
F ∩ G only: 16 − 3 = 13
F ∩ S only: 7 − 3 = 4
G ∩ S only: 5 − 3 = 2
Single sets
F only: 32 − 13 − 4 − 3 = 12
G only: 20 − 13 − 2 − 3 = 2
S only: 18 − 4 − 2 − 3 = 9
Answer
|F ∪ G ∪ S| = 45
|(F ∪ G ∪ S)′| = 50 − 45 = 5
Answer
|(F ∪ G ∪ S)′| = 5
4.Sets, relations & functions
Answer: (f ∘ g)(5) = 4
Functions and counting: a function f: A → B gives every element of A exactly one image in B. f is injective (one-to-one) when different elements have different images, surjective (onto) when every element of B is an image, and bijective when both hold. With |A| = m and |B| = n there are nᵐ functions, n!/(n − m)! injective ones (m ≤ n), and by inclusion–exclusion Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ surjective ones. |𝒫(A)| = 2ᵐ and |A × B| = m·n.
Inner function
g(5) = 1
Outer function
f(1) = 4
(f ∘ g)(5) = 4
Answer
(f ∘ g)(5) = 4
5.Graph theory
Answer: k = 6
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
8 − 1 = 7
Edges to remove
k = 13 − 7 = 6
Answer
k = 6
6.Graph theory
Answer: B
Shortest paths and spanning trees: Dijkstra’s algorithm settles one vertex per round: the unsettled vertex with the smallest tentative distance. Its distance is then final, and every neighbour v gets d(v) = min(d(v), d(u) + w(u, v)). Kruskal’s algorithm builds a minimum spanning tree by taking the edges from light to heavy and skipping any edge that would close a cycle; Prim’s algorithm grows one tree from a start vertex by always adding the lightest edge that leaves it. A spanning tree of n vertices has n − 1 edges.
Dijkstra round by round
1. A (0): B: 15, C: 2
2. C (2): B: 3, E: 14
3. B (3): D: 7
4. D (7): F: 22
5. E (14)
6. F (22)
round 3
B
Answer
B
7.Number theory & modular arithmetic
Answer: x = 12
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 = 3 + 9k
Second congruence
3 + 9k ≡ 1 (mod 11) → 9k ≡ 9 (mod 11)
k ≡ 5·9 ≡ 1 (mod 11)
Result
x = 3 + 9·1 = 12
x = 12
check: 12 mod 9 = 3, 12 mod 11 = 1
Answer
x = 12
8.Number theory & modular arithmetic
Answer: N = 2
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).