generalized pigeonhole principle

to be copied from original in CS2050 Scrapbox

principle

• let $n$ pigeons, $k$ holes

• there exists a hole with size $\ge\left\lceil\frac nk\right\rceil$

• proof

  • Assume to the contrary that $n$ pigeons go into holes $S_1,\ldots,S_k$ but each hole has $\le\left\lceil\frac nk\right\rceil$ pigeons within

  • then, $|S_i|<\left\lceil\frac nk\right\rceil$ so $|S_i|\le\left\lceil\frac nk\right\rceil-1$

  • $$\begin{aligned} n &= |S_1\cup\ldots\cup S_n| \\ &= |S_1|+\ldots+|S_k| \\ &\le \left(\left\lceil\frac nk\right\rceil-1\right)+\ldots+\left(\left\lceil\frac nk\right\rceil-1\right) \\ &= k\left(\left\lceil\frac nk\right\rceil-1\right) \\ &< k\left(\frac nk\right)=n \end{aligned}$$

  • Which implies $n<n$, contradiction!