Prove the following version of the pigeonhole principle. Let $m$ and $n$ be positive integers. If $m$ objects are distributed in some way among $n$ containers, then at least one container must hold at least $1 + \left\lfloor\frac {m − 1}{n}\right\rfloor$ objects.
Another version of PP
0
$\begingroup$
combinatorics
pigeonhole-principle
-
1Setting $m=4; n=2$ we have that one of the two containers must hold $1+\frac{4-1}2=1+\frac32=2\frac12$ objects. But what is $\frac12$ an object? And why can't I just put two objects in each container? Last I checked, two pints of beer were less than two pints and half a pint of beer. – 2012-12-03
-
1Did you perhaps mean $$\left\lfloor 1+\frac{m-1}{n}\right\rfloor$$ instead? (That may also be false, but it avoids the problem that Asaf pointed out.) – 2012-12-03
-
1Cameron's version is correct, and the original post (before editing) did in fact have brackets indicating the floor function. Unfortunately someone saw fit to delete them. – 2012-12-03
-
0As for the proof, it's easy to do by contradiction. Have you tried that? – 2012-12-03
-
1I believe you can do it by using a generalized PP, If more than mn+1 objects are distributed among n boxes, then at least one box has at least m+1 objects. – 2012-12-04