What is the pigeonhole principle?

The pigeonhole principle is a simple problem-solving technique used in discrete mathematics. It states the following:

Given$\space n \space$objects and$\space m \space$boxes, if $\space n>m \space$, there will be at least one box containing$\space \lceil n/m \rceil \space$objects.

In simple words, if$\space n+1$ pigeons are placed in $n$ pigeonholes, there will be more than one pigeon in at least one pigeonhole. This principle may seem naive, but if the boxes and objects are selected correctly, it is helpful in problem-solving.

For example, there are six cabins and seven employees; hence one cabin will belong to two employees.

Examples

Suppose there are three bird species, and each specie is in a pair—male and female. All these birds are kept in a box. If birds are taken out without looking at them, how many minimum birds must be drawn out to find a pair of a single species?

In the problem above, if we take four birds out of the box, it is guaranteed that one pair of the birds is found. In this case, the species are the boxes, and each bird drawn is an object to be sorted in the boxes.

Let's take another example.

Suppose we have to make a timetable for a university. There are 10 time slots and 210 different classes to be scheduled. We have to find the number of rooms needed. In this case, the number of boxes $m$ are 10, and the objects $n$ are 213. Let's apply the pigeonhole principle:

22 rooms are required to construct a timetable of this sort.