3. The pigeonhole principle

The pigeonhole principle

Pigeonhole principle

If $k\in {\mathbb{N}}^{+}$ and $k+1$ or more objects are placed into $k$ boxes, then there is at least one box containing two or more objects.

If there are at least $m$ cocks and $n$ holes such that $m>n$, then there must be at least $1$ hole with more than $1$ cock.

Link to original

For example:

• Among any group of $367$ people, there must be at least two with the same birthdays.
• If an exam is marked on a scale from $0$ to $100$, then from $102$ students, there must be at least two with the same mark.
• If $A$ and $B$ are finite sets with $|A|>|B|$ and $f:A\to B$ is a function, then $f$ is not one-to-one.
• For every $n\in {\mathbb{N}}^{+}$, there is a multiple of $n$ that is not $0$, and has only $0$s and $1$s for its digits. Take any $n\in {\mathbb{N}}^{+}$, consider $n+1$ many numbers. $$1,11,111,...,\stackrel{n+1}{\overbrace{\mathrm{111..1}}}$$
  • Observe that there are $n$ possible different remainders when a natural number is divided by $n$, these are $0,1,...,n-1$.
  • Because there are $n+1$ numbers on the above list, by the pigeonhole principle, there must be two with the same remainder when divided by $n$.
  • Then “the larger of these numbers minus the smaller one”
    • is divisible by $n$ and so is a multiple of $n$
    • has only $0$s and $1$s for its digits

Generalised pigeonhole principle

Generalised pigeonhole principle

The pigeonhole principle states that if $n$ objects are placed into $k$ boxes, then there is at least one box containing at least $\lceil n/k \rceil$ objects.

Link to original

For example:

• Given $100$ people, there are at minimum $\lceil 100/12\rceil =9$ who were born in the same month.
• If the possible grades for a module are A through F, then among $26$ students, there are always at least $6$ with the same module grade, as $\lceil 26/5\rceil =6$.