The Pigeonhole Principle

If n pigeonholes are occupied by n+1 or more pigeons, then at least one pigeonhole is occupied by greater than one pigeon. Generalized pigeonhole principle is: - If n pigeonholes are occupied by kn+1 or more pigeons, where k is a positive integer, then at least one pigeonhole is occupied by k+1 or more pigeons.

Example1: Find the minimum number of students in a class to be sure that three of them are born in the same month.

Solution: Here n = 12 months are the Pigeonholes And k + 1 = 3 K = 2

Example2: Show that at least two people must have their birthday in the same month if 13 people are assembled in a room.

Solution: We assigned each person the month of the year on which he was born. Since there are 12 months in a year.

So, according to the pigeonhole principle, there must be at least two people assigned to the same month