Prove Pigeon-Hole Principle: If a finite set S is partitioned into k sets, then at least one of the sets has |S|/k or more elements.
The Answer to the Question
is below this banner.
Can't find a solution anywhere?
NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?
Get the Answers Now!You will get a detailed answer to your question or assignment in the shortest time possible.
Here's the Solution to this Question
Let's assume the opposite: all sets have less than |S|/k elements.
This means that together they have less than (|S|/k)*k elements(each of k sets has no more than |S|/k). Therefore, together they have less than |S| elements.
This is the contradiction, so all sets can't have less than |S|/k elements => there is at least one set that has |S|/k or more elements.