Q 4: State and prove Pigeonhole principle with an example.
Pigeonhole सिद्धान्त को लिखें एवं उदाहरण के साथ सिद्ध करें।

Solution: If the number of pigeon is more than the number of pigeonholes, then some pigeonhole must be occupied by two or more than two pigeons. This statement is called the Pigeon hole principle, it is also called Dirchlet Drawer Principle. This statement is also written as

"If n pigeonholes are occupied by n + 1 or more pigeons, then at least one pigeonhole is occupied bby more than one pigeon"

Example 1 Among 13 people there are two who have their birthdays in the same month.

Example 2 A basket of fruit is being arranged out of apples, bananas, and oranges.

What is the smallest number of pieces of fruit that should be put in the basket in order to guarantee that either there are at least 8 apples or at least 6 bananas or at least 9 oranges?

Answer: 8 + 6 + 9-3 + 1 = 21.