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.

Answer 2

Yes you are right. You will have to put m+1 pigeons in one pigeonhole.

One easy way of solving basic pigeonhole principle questions is to divide the number of pigeons by number of pigeonholes and adding the reminder to the quotient. Use it only for very basic questions.