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

The pigeonhole principle states that if $N$ objects are placed in $k$ boxes and $N>k$, at least one box contains at least two objects.

Set $m=\lceil N/k\rceil$, using the ceiling function. If no box contains at least $m$ objects, all boxes contain at most $m-1$, so the total number of objects is at most $k(m-1)$. Taking the contrapositive, a total greater than $k(m-1)$ forces some box to contain at least $m$ objects. But $m-1<N/k$, hence $k(m-1)<N$. This proves the generalized pigeonhole principle: some box contains at least $\lceil N/k\rceil$ objects.

By the generalized pigeonhole principle, 13 cards guarantee $\lceil 13/4\rceil =4$ cards in one suit. The guarantee is sharp: 12 cards can consist of three cards from each suit, with no four cards of a common suit.