The Pigeonhole Principle

{\bf Special Interview Lecture for Undergraduate Audience}

The pigeonhole principle says: If n+1 pigeons are sorted into n boxes, then there will be at least one box with two or more pigeons in it. This statement is easy to understand and easy to prove, yet if applied correctly, it allows us to find elegant solutions to some very tricky problems. The difficulty usually lies in finding just the right pigeons, and deciding how to sort them into boxes. In my talk, I will introduce the principle, and then we shall go pigeon hunting together.