[Math] Pigeonhole Principle – Floor versus Ceiling

discrete mathematics

I realize this question will not have an "answer," but I would really like to hear what anyone might know about this topic.

In class today my professor stated that if there are $m$ pigeons and $n$ holes, then there are at least $\left \lfloor{\frac{m-1}{n}}\right \rfloor+1$ pigeons in at least one hole. I understood the proof completely but asked why we do not use the formula $\left \lceil{\frac{m}{n}}\right \rceil$ instead. He (and my classmates) tried to find a counterexample and failed. Every time he would set up and use the formula with floor I became frustrated because the formula with ceiling gets the answer so much faster! Upon a Google search, I find both statements individually but no one ever has a discussion about their equivalence.

Does anyone know why one would be preferred over the other?

Thanks!

Best Answer

IMHO the best statement of the pigeonhole principle is... neither of these.

My reason for saying this is that both of them encourage mindless application of formulae without thinking about what they actually signify. (Though it is clear from your question that you have not fallen into this trap :)

Here is, IMO, the best formulation of the (generalised) PHP:

if $n$ pigeonholes contain, altogether, more than $kn$ pigeons, then there is a pigeonhole which contains more than $k$ pigeons.

Addendum. Your professor and classmates won't find a counterexample, because the two formulae do always give the same result. To see this, write $m=qn+r$ with $0\le r<n$. It is easy to calculate that if $r=0$ then both expressions are $q$, while if $r>0$ then both expressions are $q+1$.

Related Question