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
You want to prove (q ∧ p) → ¬r by contradiction. Which statement do you assume at the start? Click it.
(q ∧ p) → ¬r
1¬(q ∧ p) ∧ ¬r
2¬(q ∧ p) ∧ ¬¬r
3(q ∧ p) ∧ ¬¬r
4¬(q ∧ p) → ¬¬r
2.Propositional logic & proofsHard
The premises p → r; ¬r are given. Which conclusion follows from them? Click it.
p → r¬r
1¬p ∧ r
2¬p
3r
4p
3.Sets, relations & functionsMedium
Of 39 first-year students, 8 passed Mathematics (M), 23 passed Physics (P) and 2 passed both. How many are in at least one of the two sets?
|U| = 39|M| = 8|P| = 23|M ∩ P| = 2
|M ∪ P| =
4.Sets, relations & functionsHard
On X = {1, 2, …, 7} the relation x ~ y holds when x ≡ y (mod 4). How many elements are in the equivalence class [5]?
X = {1, …, 7}x ~ y ⟺ 4 | (x − y)
|[5]| =
5.Graph theoryMedium
Does the connected graph have an Euler circuit, an Euler path that is not a circuit, or neither? Click your answer.
|V| = 6|E| = 7
1Euler circuit
2Euler path, no circuit
3neither
6.Graph theoryHard
Dijkstra’s algorithm runs from A. Click the vertex that is settled (made permanent) in round 4; A itself is round 1.
start: Around 4
1A
2B
3C
4D
5E
6F
7G
7.Number theory & modular arithmeticMedium
Find the inverse of 41 modulo 47: the number x with 0 < x < 47 and 41·x ≡ 1 (mod 47).
a = 41n = 47
41−1 mod 47 =
8.Number theory & modular arithmeticHard
Solve 75x ≡ 72 (mod 84). Give the smallest positive solution x.
75x ≡ 72 (mod 84)
x =
3Solutions
1.Propositional logic & proofs
Answer: (q ∧ p) ∧ ¬¬r
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).
Parts of the implication
a = q ∧ p, b = ¬r
Negation of the implication
¬(a → b) ≡ a ∧ ¬b = (q ∧ p) ∧ ¬¬r
Answer
(q ∧ p) ∧ ¬¬r
If the assumption leads to a contradiction, the implication must be true.
2.Propositional logic & proofs
Answer: ¬p
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.
Rows with all premises true
p = 0, r = 0: ¬p ∧ r = 0, ¬p = 1, r = 0, p = 0
Conclusion
¬p (modus tollens)
Answer
¬p
3.Sets, relations & functions
Answer: |M ∪ P| = 29
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|.
Regions
M ∩ P: 2
M − P: 8 − 2 = 6
P − M: 23 − 2 = 21
(M ∪ P)′: 39 − (6 + 21 + 2) = 10
Answer
|M ∪ P| = 29
Answer
|M ∪ P| = 29
4.Sets, relations & functions
Answer: |[5]| = 2
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.
The class
[5] = {1, 5}
|[5]| = 2
Answer
|[5]| = 2
5.Graph theory
Answer: Euler circuit
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.
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: 7
2. B (7): C: 18, D: 13, G: 17
3. D (13): E: 27, F: 26
4. G (17)
5. C (18)
6. F (26)
7. E (27)
round 4
G
Answer
G
7.Number theory & modular arithmetic
Answer: 41−1 mod 47 = 39
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).
Extended Euclidean algorithm
Each remainder r is written as r ≡ t·41 (mod 47).
r = 47, t = 0
r = 41, q = 1, t = 1
r = 6, q = 6, t = −1
r = 5, q = 1, t = 7
r = 1, q = 5, t = −8
Inverse
1 ≡ −8·41 (mod 47)
x = 39
check: 41·39 = 1599 = 34·47 + 1
Answer
41−1 mod 47 = 39
8.Number theory & modular arithmetic
Answer: x = 20
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).