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.

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