[Math] Pigeonhole Principle : $mn+1$ pigeons into $n$ holes.

Question

If you have to put $n+1$ pigeons into $n$ holes, according to Pigeonhole principle, you will have to put two pigeons into the same hole. But what if you have to put $mn+1$ pigeons into $n$ holes?

(Does this mean that $m+1$ pigeons will have to be placed into the same hole?)

Answer 1

Yes, you have to put at least $m+1$ pigeons into one hole.

Proof is by contradiction:

Suppose not, so every hole contains at most $m$ pigeons. In that case there are at most $mn < mn+1$ pigeons across the $n$ holes, contradiction.

But we can find a distribution such that no hole contains $m+2$ pigeons:

Put $m+1$ pigeons in the first hole, then $m$ pigeons in the subsequent $(n-1)$-holes. Then there are $m+1+(n-1)m = nm+1$ pigeons in total (as required), but no hole contains $m+2$ pigeons.