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
-
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
1 Answers
0
HINT: Suppose that each container holds at most $\left\lfloor\dfrac{m-1}n\right\rfloor$ objects. Then it’s certainly true that each container holds at most $\dfrac{m-1}n$ objects. (Why?) What does that tell you about the maximum possible total number of objects in all $n$ containers?