Solution to Prove Pigeon-Hole Principle: If a finite set S is partitioned into k sets, then at … - Sikademy
Author Image

Archangel Macsika

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.


Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3982-qpid-2681