The Pigeonhole Principle

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

If $N$ objects are placed into $k$ boxes, then there is at least one box containing at least $\lceil N/k\rceil$ obejcts

Ramsey Theory

Example

Assume that in a group of six people, each pair of individuals consists of two friends of two enemies. Then there are either three mutual friends or three mutual enemies in the group

Proof: Let $A$ be one of the six people. Of the five other people in the group, there are either three or more who are friends of $A$, or three or more who are enemies of $A$. This follows the generalized pigeonhole principle, because when five objects are divided into two sets, one of the sets has a least $\lceil 5/2\rceil =3$ elements.

Generalization

The Ramsey number $R(m,n)$, where $m,n\ge 2$, denote the minimum number of people at a party such that there are either $m$ mutual friend of $n$ mutual enemies, assuming that every pair of people at the party are friends or enemies.