Mathematical Preliminaries: The pigeon hole principle
Mathematical Preliminaries: The pigeon hole principle
The Pigeonhole Principle
Basic Concept

The Pigeonhole Principle is a principle of combinatorial mathematics that states: if more than
n
items are put inton
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 andk + 1
or more objects are placed intok
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.
Applications

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.
Generalized Pigeonhole Principle

The Generalized Pigeonhole Principle states: if
n
items are put intom
containers, andn > km
, then at least one container must contain more thank
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.
Examples

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.