Question

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.

Answer 1

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.