We use the Pigeon Hole Principle

Pigeon Hole Principle

(problem 1) A drawer contains red, green and purple socks. How many socks must be selected to ensure that there are two of the same color?
(problem 2) Humans are known to have at most 200,00 hairs on their heads. How large must the population of a city be in order to ensure that at least 2 people have the same number of hairs on their heads?
If is the number of hairs on a persons head, then
(problem 3) A group of people convenes and they begin shaking hands. Each pair of people can shake hands 0 or 1 times. Use the Pigeonhole Principle to explain why there must be at least 2 people who shake the same number of hands.

Suppose not. That is, suppose that each of the pigeonholes contains fewer than pigeons. Then the number of pigeons in each pigeonhole is no more than and the total number of pigeons is no more than . But this contradicts the assumption that there are pigeons. Hence, there must be at least one pigeonhole containing (or more) pigeons.
(problem 4) The edges of a graph are colored using 5 different colors. How many edges must the graph have to ensure that there are at least 4 edges of the same color?