The Pigeonhole Principle: Basics and Applications

This lecture introduces the Pigeonhole Principle, stating that if k + 1 objects are placed into k boxes, then at least one box contains two or more objects. It explores the principle's applications in proving functions are not one-to-one and extends to the Generalized Pigeonhole Principle. Examples illustrate how the principle guarantees specific outcomes, such as finding people born in the same month or selecting cards of the same suit from a deck.