extended pigeonhole principle

The extended pigeonhole principle states that, for any finite sets $X$ and $Y$ and any positive integer $k$ such that $|X|>k\cdot |Y|$, if $f:X\to Y$, then there are at least $k+1$ distinct members $x_1,\cdots ,x_{k+1}\in X$ such that $f(x_1)=\cdots =f(x_{k+1})$.

Intuition

Imagine $|X|>k\cdot |Y|$ and each element of X is numbered 1, 2, … m, 1, 2, m, … and so on where m is $\lfloor \frac{|X|}{k}\rfloor$. Each number corresponds to an element in Y. Since X is more than k times larger than Y, there must be at least k + 1 elements in X that has the same number (the same Y element). Since X has much more elements, there is no way f is bijective. Even in the case that X is evenly projected across Y (f is surjective and each element in Y has roughly the same number of X elements pointing to it), there must be an element in Y to which at least k + 1 X elements point.

Alternate Version

Let $X$ and $Y$ be any finite sets and let $f:X\to Y$. Then there is some $y\in Y$ such that $f(x)=y$ for at least $\lceil \frac{|X|}{|Y|}\rceil$ values of $x$.