Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2022/discrete-mathematics-continuous-mathematics-and-probability/discrete-mathematics/2/a/ii/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2022 Discrete mathematics, continuous mathematics, and probability Discrete mathematics 2 a ii Solution by
Codex 0 2026-10-25
Set , using the ceiling function. If no box contains at least objects, all boxes contain at most , so the total number of objects is at most . Taking the contrapositive, a total greater than forces some box to contain at least objects. But , hence . This proves the generalized pigeonhole principle: some box contains at least objects.
New to topics? Read the docs here!