State and prove the Pigeonhole principle.
ANSWER – Let us start with considering a situation where we have 10 boxes and 11 objects to be placed in them. Wouldn’t you agree that regardless of the way the objects are placed in the two boxes at least one box will have more than one object in it? On the face of it, this seems obvious. This is actually an application of the pigeonhole principle, which we now state.
Theorem 1 (The Pigeonhole Principle): Let there be n boxes and (n+1) objects. Then, under any assignment of objects to the boxes, there will always be a box with more than one object in it.
This can be reworded as: if m pigeons occupy n pigeonholes, where m > n, then there is at least one pigeonhole with two or more pigeons in it.
