The Pigeonhole Principle PDF

The Pigeonhole Principle **Example1:** Find the minimum number of students in a class to be sure that three of them are born in the same month. **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 ea...

The Pigeonhole Principle **Example1:** Find the minimum number of students in a class to be sure that three of them are born in the same month. **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. What Is the Pigeonhole Principle? --------------------------------- Think of the pigeonhole principle as the statement about a function *f* from domain P → PH, where pigeon *n* flies into pigeonhole *f*(*n*), as is shown below: An illustration of the pigeonhole principle --- more pigeons than holes **What is the pigeonhole principle?** **Solution** **Pigeonhole principle:** **Pigeonhole principle roughly states that if there are few boxes available also, there are few objects that are greater than the total number of boxes as well as one needs to place objects in the given boxes, then at least one box must contain more than one such objects.**  **Hence, pigeonhole principle states that if more than n pigeons are placed into n pigeonholes, some pigeonholes must contain more than one pigeon.** Show that among any group of 366 people there must be at least two with the Birthday on same day. M = 365 N = 366 \[(N-1)/M\] +1 = (366-1)/ 365 + 1 = 2 Show that in any group of 27 English, words there must beat least two that begin with the same letter. N= 27 M= 26 \[(N-1)/M\] +1 = (27-1)/26 + 1 = 1+1 = 2 **Example: How many students must be in a class to guarantee that at least two students receive the same score on the final exam, if the exam is graded on a scale from 0 to 100 points.** N= X M=100 \[(N-1)/M\] +1 = \[(X-1)/100\] + 1= 2 (X-1 )/100 =2-1 (X-1)/ 100 = 1 X-1 = 101 **Example: - Show among 100 people there are at least 9 who were born in the same month.** N = 100 M= 12 \[(N-1)/M\] +1 (100-1)/12 + 1 = 99/12 + 1 = 8 +1 = 9 **Example: - What is the minimum number of students required in a discrete mathematics class to be sure that at least six will receive the same grade, if there are five possible grades, A, B, C, D and F.** N = X M= 5 \[(N-1)/M\] +1 = 6 (X-1)/ 5 = 5 X-1 = 25 X = 26