Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics and probability resit / 3 / c

The pigeonhole principle states that if more than $r$ objects are placed in $r$ boxes, with $r\ge 1$, at least one box contains two or more objects. Equivalently, a function from a finite set of more than $r$ elements to a set of $r$ elements cannot be injective: if every box held at most one object, there would be at most $r$ objects altogether.