A connected graph has 13 vertices and 14 edges. How many edges k must be removed to leave a spanning tree?
|V| = 13|E| = 14
k =
6.Graph theoryHard
Dijkstra’s algorithm runs from A. Click the vertex that is settled (made permanent) in round 5; A itself is round 1.
start: Around 5
1A
2B
3C
4D
5E
6F
7.Number theory & modular arithmeticMedium
Find the inverse of 23 modulo 91: the number x with 0 < x < 91 and 23·x ≡ 1 (mod 91).
a = 23n = 91
23−1 mod 91 =
8.Number theory & modular arithmeticHard
Solve 24x ≡ 22 (mod 26). Give the smallest positive solution x.
24x ≡ 22 (mod 26)
x =
3Solutions
1.Propositional logic & proofs
Answer: ¬c → ¬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
An implication is equivalent to its contrapositive ¬b → ¬a, not to its converse b → a or its inverse ¬a → ¬b.
a → c ≡ ¬c → ¬a
Check with the truth table
a = 1, c = 1: 1 | 0 1 1 1
a = 1, c = 0: 0 | 0 1 1 0
a = 0, c = 1: 1 | 0 0 0 1
a = 0, c = 0: 1 | 1 1 1 1
Answer
¬c → ¬a
The columns after the bar are the options in the order shown.
2.Propositional logic & proofs
Answer: ∀x ∃y ¬R(x, y)
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.
Move the negation inwards
¬∃x ∀y R(x, y) ≡ ∀x ∃y ¬R(x, y)
Answer
∀x ∃y ¬R(x, y)
The other options either keep a quantifier unchanged, change the order of the quantifiers, or negate the inner formula wrongly.
3.Sets, relations & functions
Answer: |(L ∪ T)′| = 13
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
L ∩ T: 11
L − T: 33 − 11 = 22
T − L: 19 − 11 = 8
(L ∪ T)′: 54 − (22 + 8 + 11) = 13
Answer
|(L ∪ T)′| = 13
Answer
|(L ∪ T)′| = 13
4.Sets, relations & functions
Answer: (f ∘ g)(2) = 1
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(2) = 4
Outer function
f(4) = 1
(f ∘ g)(2) = 1
Answer
(f ∘ g)(2) = 1
5.Graph theory
Answer: k = 2
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
13 − 1 = 12
Edges to remove
k = 14 − 12 = 2
Answer
k = 2
6.Graph theory
Answer: E
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: 1, C: 7
2. B (1): D: 10, E: 15
3. C (7): E: 11
4. D (10): F: 15
5. E (11)
6. F (15)
round 5
E
Answer
E
7.Number theory & modular arithmetic
Answer: 23−1 mod 91 = 4
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·23 (mod 91).
r = 91, t = 0
r = 23, q = 3, t = 1
r = 22, q = 1, t = −3
r = 1, q = 22, t = 4
Inverse
1 ≡ 4·23 (mod 91)
x = 4
check: 23·4 = 92 = 1·91 + 1
Answer
23−1 mod 91 = 4
8.Number theory & modular arithmetic
Answer: x = 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).