Confused on the Definition of The Pigeonhole Principle

Question

In my Combinatorics class yesterday, my professor defined The Pigeonhole Principle (TPP) as follows:

"If you have $n$ holes into which you wish to put more than $mn$ pigeons, then some hole must contain more than $m$ pigeons."

I don't know how to interpret this definition. I've seen TPP before in a Discrete Math class I took a while ago, but it was defined differently and I'm pretty sure I remember something about 2$\lfloor n/k \rfloor$ + 1 being relevant.

Why are $m$ and $n$ being multiplied? Why do you need more than $m$ pigeons? Why not more than $mn$ pigeons?

The Wikipedia article on TPP has a nice example: https://en.wikipedia.org/wiki/Pigeonhole_principle

In it they have $m$ = 10 pigeons and have $n$ = 9 pigeonholes. However, according to the definition provided by my professor, I am wanting to put more than 90 pigeons into the 9 pigeonholes, so that means at least one hole must contain more than 10 pigeons. I don't see 90+ pigeons in Wikipedia's example.

If somebody could explain all this for me and why $m$ and $n$ are being multiplied that would be seriously amazing. Thank you so, so much.

Answer 1

The wiki article and your professor are using different statements of the pigeonhole principle. Wiki uses

If there are $n$ holes and $m$ pigeons, if $m>n$, then at least one hole has more than one pigeon.

Your professor's statement is

If there are $n$ holes and more than $mn$ pigeons, at least one hole has more than $m$ pigeons.

Note that $m$ doesn't mean the same thing in the two statements. In the first statement $m$ is the total number of pigeons. In the second statement, $m$ is just a number, and the total number of pigeons isn't specified (just that it's larger than $mn$). This is the source of your confusion. To make this more clear, let's rephrase your professor's statement to parallel wikipedia's:

If there are $n$ holes and $k$ pigeons, if $k > mn$, then at least one hole has more than $m$ pigeons.

As a general tip, $m$, $n$, and $k$ are just labels--they don't have any special meaning. When comparing two statements that use the same labels, always check to whether those labels mean the same thing in each statement.

Answer 2

Quite often the definition of the pigeonhole principle is just something like,"If you have $h$ holes into which you wish to put $p$ pigeons and $p>h$, then some hole must contain more than $1$ pigeon"

This is equivalent to $m=1, n=h$ in your professor's more generalized definition of the pigeonhole principle:

"If you have $n$ holes into which you wish to put more than $mn$ pigeons, then some hole must contain more than $m$ pigeons."

An example with $9$ pigeonholes and $10$ pigeons would imply that we have $m=1, n=9$ in his definition.