1
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ there are extended versions of the principle. I don't see where you get 9 and 10 in the birthday problem. $\endgroup$
    – user451844
    Commented Aug 31, 2017 at 20:55
  • 1
    $\begingroup$ Your professor is giving a version of the Strong form of the Pigeonhole Principle. In the Wikipedia article, let $m=r-1$ in the Strong form and you will get the statement your professor gave. $\endgroup$
    – user84413
    Commented Aug 31, 2017 at 20:59
  • 3
    $\begingroup$ In your prof's notation, the Wikipedia example uses $n=9$ and $m=1$ (not $m=10$): You have 9 holes into which you wish to put more than 9 pigeons. Therefore some hole must contain more than 1 pigeon. $\endgroup$
    – grand_chat
    Commented Aug 31, 2017 at 21:00
  • $\begingroup$ @RoddyMacPhee, sorry, I think I clicked on the link within the article and that's why the link contained the birthday problem. I fixed that. I remember reading the proper definition of it in relation to infinite sets. $\endgroup$
    – Matthew Graham
    Commented Aug 31, 2017 at 21:06
  • $\begingroup$ @user84413, Thanks for the comment! $\endgroup$
    – Matthew Graham
    Commented Aug 31, 2017 at 21:07

2 Answers 2

Reset to default
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank you! So, per the definition I was provided in class, $m$ > $mn$? How is that possible if $n$ is a positive integer? Or is it $m$ > $n$? $\endgroup$
    – Matthew Graham
    Commented Aug 31, 2017 at 22:26
  • 1
    $\begingroup$ @MatthewGraham Per the definition you were provided in class, $k$, the variable I have assigned to represent the total number of pigeons, is greater than $mn$. $m$ and $n$ have no relation. It is only in the definition given on wikipedia where $m > n$, and as I mentioned in the answer, the wikipedia definition and your professor's definition do not use $m$ to represent the same quantity. $\endgroup$
    – eyeballfrog
    Commented Aug 31, 2017 at 22:39
  • $\begingroup$ @MatthewGraham, it may help to think about it backwards. How many pigeons do you need to guarantee that at least one hole has more than 1 pigeon? More than 2 pigeons? More than 3 pigeons? $\endgroup$
    – Peter Taylor
    Commented Sep 1, 2017 at 10:12
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks! Although I'm still confused on how $m = 1$ and $n = 9$. Based on my professor's definition, We have $n = 9$, but then does $mn = 10$ or does $m = 10$? From another answer above, $m$ is just an arbitrary positive integer in my professor's definition. If it isn't too much trouble, do you think you could go through the math to show how you arrive at your conclusion that $m = 1$ and $n = 9$ please? $\endgroup$
    – Matthew Graham
    Commented Aug 31, 2017 at 22:34
  • 1
    $\begingroup$ $10$ is just "more than $mn$". and of course $mn=9$. We get $n=9$ directly from the number of pigeonholes and then since there are $10$ pigeons we only have $m=1$ left as a reasonable solution. $\endgroup$
    – Joffan
    Commented Aug 31, 2017 at 22:56
  • $\begingroup$ I get that 10 is just "more than $mn$" and I understand how $n = 9$, but why can we say $mn = 9$? I know if we assume so, we can set $mn = 9$ and $n = 9$ to each other and that leaves $m = 1$, but why can we set $mn = 9$ in the first place? $\endgroup$
    – Matthew Graham
    Commented Sep 1, 2017 at 1:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .