Injective/Surjective/Bijective Functions, Pigeonhole Principle & Permutations
Idea in plain words
Function Classification: Injective / One-to-One (f(a) = f(b) => a = b); Surjective / Onto (∀y ∈ B, ∃x ∈ A such that f(x) = y); Bijective (both one-to-one and onto; has an inverse f⁻¹).
Exam tip
High-yield exam topic (Very High).
Explanation
Combinatorics and function theory establish the formal boundaries of computational complexity and resource allocation. The Pigeonhole principle is a non-constructive proof tool essential for establishing collision guarantees in hash tables, bounds in lossy data compression, and existence proofs in graph theory.
Key points
- Pigeonhole Principle (PHP): If k + 1 or more objects are placed into k boxes, at least one box contains two or more objects.
- Generalized Pigeonhole Principle: If N objects are placed into k boxes, at least one box contains at least ⌈N/k⌉ objects.
- Permutations P(n, r) = n! / (n - r)! (order matters); Combinations C(n, r) = n! / [r! (n - r)!] (order does not matter).
- Combinations with repetition: Number of ways to choose r elements from n categories = C(n + r - 1, r).
Example
Example
Prove that among any 5 points chosen inside an equilateral triangle of side 1, there exists a pair at distance ≤ 1/2. Divide the triangle into 4 smaller equilateral triangles of side 1/2. By PHP, 5 points in 4 triangles guarantees at least one small triangle contains ≥ 2 points.
Code examples
// Pigeonhole Principle Problem:
// In a room of 367 people, there are 366 possible birthdays (including Feb 29).
// By PHP: 367 > 366 => At least 2 people must share the exact same birthday!
// Generalized Example:
// How many cards must be selected from a standard 52-card deck to guarantee
// at least 3 cards of the same suit?
// Suits k = 4. Target ⌈N / 4⌉ = 3.
// Minimum N = 4 * (3 - 1) + 1 = 4 * 2 + 1 = 9 cards.
Exam questions
- [8 Marks] State and prove the Generalized Pigeonhole Principle. Show that if 7 colors are used to paint 50 bicycles, at least 8 bicycles must have the same color.
- [7 Marks] Let f: A -> B and g: B -> C be two functions. Prove that: (i) If f and g are injective, then g ∘ f is injective. (ii) If g ∘ f is surjective, then g is surjective.
- [7 Marks] In how many ways can 5 computer science books, 4 mathematics books, and 3 physics books be arranged on a shelf such that books of the same subject are together?