The arrow diagram shows a function f: A → B with A = {1, 2, 3, 4} and B = {a, b}. Click the description that fits f.
f = {(1, b), (2, a), (3, a), (4, a)}
1injective, not surjective
2surjective, not injective
3bijective
4neither
5.Graph theoryMedium
How many different Hamilton circuits H does the complete graph K8 have? Circuits that differ only in the starting vertex or the direction count as the same.
K8
H =
6.Graph theoryHard
How many walks of length 3 go from B to A? A walk may repeat vertices and edges. Call the number N.
M = adjacency matrixL = 3
N =
7.Number theory & modular arithmeticMedium
Find the smallest positive integer x with x ≡ 4 (mod 7) and x ≡ 9 (mod 13).
x ≡ 4 (mod 7)x ≡ 9 (mod 13)
x =
8.Number theory & modular arithmeticHard
Solve 42x ≡ 66 (mod 74). Give the smallest positive solution x.
42x ≡ 66 (mod 74)
x =
3Solutions
1.Propositional logic & proofs
Answer: (a → c) ∧ (b → 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) → c needs c whenever either a or b holds: (a → c) ∧ (b → c).
(a ∨ b) → c ≡ (a → c) ∧ (b → c)
Check with the truth table
a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 0 | 1 0 0 0
a = 1, b = 0, c = 1: 1 | 1 1 1 1
a = 1, b = 0, c = 0: 0 | 1 1 1 0
a = 0, b = 1, c = 1: 1 | 1 1 1 1
a = 0, b = 1, c = 0: 0 | 0 1 1 0
a = 0, b = 0, c = 1: 1 | 1 1 1 1
a = 0, b = 0, c = 0: 1 | 1 1 1 1
Answer
(a → c) ∧ (b → c)
The columns after the bar are the options in the order shown.
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, q = 0, r = 0: ¬p ∧ q = 0, q = 0, ¬p = 1, p = 0
Conclusion
¬p (modus tollens twice)
Answer
¬p
3.Sets, relations & functions
Answer: reflexive
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.
reflexive
holds
symmetric
fails: (1, 4) ∈ R, (4, 1) ∉ R
antisymmetric
fails: (2, 3), (3, 2) ∈ R
transitive
fails: (2, 3), (3, 1) ∈ R, (2, 1) ∉ R
Answer
reflexive
4.Sets, relations & functions
Answer: surjective, not injective
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.
Injective?
f(2) = f(3) = a → not injective
Surjective?
every element of B is hit → surjective
Answer
surjective, not injective
Answer
surjective, not injective
5.Graph theory
Answer: H = 2520
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.
Count
H = (8 − 1)!/2 = 5040/2 = 2520
Answer
H = 2520
6.Graph theory
Answer: N = 5
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 0
B: 1 0 1 0 1 0
C: 1 1 0 0 1 0
D: 0 0 0 0 1 1
E: 0 1 1 1 0 0
F: 0 0 0 1 0 0
One more step
(M³)BA = 1·0 + 3·1 + 2·1 + 1·0 + 1·0 + 0·0 = 5
Answer
N = 5
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 + 7k
Second congruence
4 + 7k ≡ 9 (mod 13) → 7k ≡ 5 (mod 13)
k ≡ 2·5 ≡ 10 (mod 13)
Result
x = 4 + 7·10 = 74
x = 74
check: 74 mod 7 = 4, 74 mod 13 = 9
Answer
x = 74
8.Number theory & modular arithmetic
Answer: x = 28
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).