## The Pigeonhole Principle |

**The pigeonhole principle:**

If more than \(k\) objects are placed into \(k\) boxes, then at least one box contains more than one object.

**Example.**
By the pigeonhole principle, there are at least two of 27 or more people whose names start with the same letter.

**Example.**
Prove that at a party with at least two people (with no strangers), there are at least two people who know the same number of
other people.

*Solution.* Suppose there are \(n\geq 2\) people at a party with no strangers. The possible numbers of known people to each
of these \(n\) people are
\[1,2,3,\ldots,n-1.\]
By the pigeonhole principle, there are at least two people with the same number of known people.

**Example.**
Let \(d\) be a positive integer. Show that among any \(d+1\) integers, there are at least two integers with the same remainder
when they are divided by \(d\).

*Solution.* If an integer is divided by \(d\), then there are \(d\) possible remainders:
\[0,1,2,\ldots,d-1.\]
When \(d+1\) integers are divided by \(d\), there are \(d+1\) remainders. By the pigeonhole principle, there are at least
two integers with the same remainder.

**The generalized pigeonhole principle:**

If \(n\) objects are placed into \(k\leq n\) boxes, then at least one box contains at least
\(\displaystyle\left\lceil \frac{n}{k} \right\rceil \) objects.

Suppose \(n\) objects are placed into \(k\leq n\) boxes. Assume, to the contrary, that each box contains at most
\(\displaystyle\left\lceil \frac{n}{k} \right\rceil -1\) objects. Then the total number of objects is at most
\[k\left( \left\lceil \frac{n}{k} \right\rceil -1 \right) < k\left( \left(\frac{n}{k}+1 \right) -1 \right)=n\]
which contradicts that there \(n\) objects. Thus at least one box contains at least
\(\displaystyle\left\lceil \frac{n}{k} \right\rceil \) objects.

**Example.**
Show that there are at least seven people in California (population 40 million) with the same 3-letter initial and
the same birthday.

*Solution.* There are 26 ways to choose each of three letters in a 3-letter initial. By the product rule, there are
\(26^3\) 3-letter initials. There are \(366\) possible birthdays. By the product rule, there are \(26^3\cdot 366\)
3-letter initials together with a birthday. By the generalized pigeonhole principle, there are at least
\[\displaystyle\left\lceil \frac{40,000,000}{26^3\cdot 366} \right\rceil =\left\lceil 6.2 \right\rceil =7 \]
people in California with the same 3-letter initial and the same birthday.

**Example.**
What is the minimum number of students in a class where at least four students get the same grade and possible grades are
A, B, C, D, and F?

*Solution.* Suppose there are \(n\) students in a class where at least four students get the same grade out of 5 possible grades.
By the generalized pigeonhole principle,
\[\displaystyle\left\lceil \frac{n}{5} \right\rceil =4. \]
The smallest integer \(n\) satisfying the above equation is \(n=5(4-1)+1=16\). Thus the required minimum number of students is 16.

Last edited