4

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!

David
  • 82,662
fullyhip
  • 436

2 Answers2

4

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$.

David
  • 82,662
  • 1
    I completely agree with your mindless application of formula opinion. However the ceiling function does not even require thinking about a formula! If I have m pigeons and n holes, I want the "worst case scenario" so I evenly divide. This means there will be $\frac{m}{n}$ pigeons per hole. If this is an integer, awesome we are done. If this is not an integer, round up because then there is guaranteed to be that many pigeons in at least one hole. DONE! – fullyhip Nov 20 '15 at 03:27
  • Yes ... he and they agreed, but for EVERY EXAMPLE he still calculated using the floor when I had the answer in about two seconds! – fullyhip Nov 20 '15 at 03:32
  • I still think my formulation addresses the problem more directly: if you put more than $30$ objects into $10$ boxes, there must be a box containing more than $3$ objects. Obvious, no? – David Nov 20 '15 at 03:32
  • Also, in some of the more intricate examples of PHP, it may not be very clear what the "worst case scenario" is. – David Nov 20 '15 at 03:32
  • Yeah I know "worst case" is ambiguous - I mean evenly distribute to spread out and see which has the most. – fullyhip Nov 20 '15 at 03:34
1

This is a good proof that $\left \lfloor{\frac{m-1}{n}}\right \rfloor+1=\left \lceil{\frac{m}{n}}\right \rceil$. Let $k=\left\lfloor{\frac{m-1}{n}}\right \rfloor$ You put $k$ pigeons in each hole, then put one more in some of the holes. If $n|m$, the floor on the left is one less than the ceiling on the right because the argument of the ceiling is an integer. If $n \not |m$, the floor on the left is one less than the ceiling on the right because $\frac mn$ is a fraction.

Ross Millikan
  • 374,822