Mathematical Preliminaries: The pigeon hole principle

The Pigeonhole Principle

The Pigeonhole Principle is a principle of combinatorial mathematics that states: if more than n items are put into n containers, then at least one container must contain more than one item.
It is a simple yet powerful tool used for solving problems related to counting, arrangements, and distributions.
In mathematical terms, if k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.
The principle is called the Pigeonhole Principle because it is metaphorically comparable to placing pigeons (items) into pigeonholes (containers). If there are more pigeons than pigeonholes, then at least one pigeonhole must contain more than one pigeon.

The Pigeonhole Principle is used in a wide range of mathematical fields such as algebra, geometry, number theory, and combinatorics.
The principle is often used to prove that a certain condition must hold for at least one member of a set, by ruling out all possibilities where it does not.

The Generalized Pigeonhole Principle states: if n items are put into m containers, and n > km, then at least one container must contain more than k items.
This generalised version of the principle is used when the scenario involves more complex distributions and not just the assumption of one item per container.

One common application of the Pigeonhole Principle is the “birthday problem”: in a group of more than 365 people (ignoring leap years), at least two must share the same birthday, since there are only 365 possible birthdays.
Another example: in a group of five people, there must be at least two who have been born in the same month. This is because there are only twelve months, so if we have more than twelve people, there has to be at least one month shared by two people - a direct application of the Pigeonhole Principle.