Pigeonhole principle (statement)- If n pigeonholes are occupied by n + 1 or more pigeons, then at least one pigeonhole is occupied by more than one pigeon.
This principle can be applied to many problems where we want to show that a given situation can occur.
Examples
Example-1: Suppose a class contains 13 students, then two of the students (pigeons) were born in the same months (pigeonholes)
Example-2: Suppose a department contains 13 professors, then two of the professors (pigeons) were born in the same month (pigeonholes).
Example-2: Find the minimum number of elements that one needs to take from the set S = {1, 2, 3, . . . , 9} to be sure that two of the numbers add up to 10.
Here the pigeonholes are the five sets {1, 9}, {2, 8}, {3, 7}, {4, 6}, {5}. Thus any choice of six elements (pigeons) of S will guarantee that two of the numbers add up to ten.
Example-2: Show that if seven numbers from 1 to 12 are chosen, then two of them will add up to 13.
Sol.
First we will construct six different sets, each containing two numbers that add up to 13 as follows-
Each of the seven numbers belong to one of these six sets.
Since there are six sets, then according to the pigeonhole principle that two of the numbers chosen belong to the same set. These numbers add upto 13.
Example-3: Suppose a bag contains 10 red balls, 10 white balls and 10 blue balls. what is the minimum number of balls we have to choose randomly for the bag to ensure that we 4 balls of same color?
Solution:
By applying Pigeonhole principle-
number of colors(pigeonholes) n = 3
number of balls (pugeons) k + 1 = 4
hence the minimum number of balls required = kn + 1
by simplifying we obtain kn + 1 = 10.