0
$\begingroup$

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.

  • 1
    I 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 1

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?