# Pigeonhole: Practical Applications in Computer Science

Most of the problems I've seen involving the pigeonhole principle have so far seemed fairly artificial. As I'm studying CompSci I'm interested what kind of practical, real world problems in CompSci are solved using this principle?

-

The pigeonhole principle can be used in a more subtle way to derive the $\Omega(n \log n)$ lower bound on comparison sorts by showing that if the algorithm makes fewer comparisons than this, there must be some pair of inputs that the algorithm wouldn't be able to distinguish, since there are more possible inputs than configurations of the algorithm. Similar arguments can be used to show other lower bounds in other problems.