Pigeonhole PrincipleFatima WardaPeriod.9 Hicksville High SchoolI wish to not participate in the Math FairAbstractThe pigeonhole principle is one of the most simple yet important tools used in mathematics. The pigeonhole principle states that given n boxes and m > n objects, at least one box must contain more than one object. In this paper you will see the main aspects of the pigeonhole principle, how it was used initially and its different applications. The pigeonhole principle is used in different forms such as the , generalized pigeonhole principle, second form of pigeonhole principle, third form and fourth form of the pigeonhole principle. .These principles are applied to real world situations such as taking medications, playing with a deck of cards and people sitting on a limited number of chairs.The Pigeonhole Principle is a principle which is applied to a broad spectrum to many situations. Pigeonhole principle, also known as the Dirichlet’s principle, originated from an idea that was expressed by Peter Gustav Lejeune Dirichlet. The objective behind his idea was that if there is a pigeon in search of a place in a grid and the grid is fully occupied with one pigeon in each grid, where should the pigeon looking for a spot go and what mathematical tool can be used to apply and solve this. The pigeonhole principle was then established to solve this concept and it states that “given n boxes and m > n objects, at least one box must contain more than one object”(Chiou). The history of the pigeonhole principle does not include much detail about the origin and development of it but what is known is that it was credited to Peter Gustav Lejeune Dirichlet in 1834. Since it was accredited to Dirichlet, the French term for this principle is “le Principe des tiroirs de Dirichlet,” which is translated to ” the principles of drawers of Dirichlet”. Dirichlet’s pigeonhole principle emphasizes that if a large number of objects is distributed in any way over not too many classes, then one of these classes contains many of these objects. The meaning of the German word Schubfach and the French word tiror relates to the English word drawer, “an open-topped box that can be slid in and out of the cabinet that contains it”. These words were then morphed into the word pigeonhole.The meaning, referring to some furniture features, has since been strongly overtaken, especially among those who do not speak English natively, but as a lingua franca in the scientific world, in favor of the more pictorial interpretation, literally involving pigeons and holes. It is interesting to note that the suggestive, though the not misleading interpretation of “pigeonhole” as “dovecote” has lately found its way back to a German “re-translation” of the “pigeonhole”-principle as the “Taubenschlag”-principle (Pigeonhole Principle). Pigeonhole principle can solve lots of seemingly unbelievable statements. Dirichlet’s principle revolves around the concept that if a pigeon is looking for a place in a grid, but each box on the grid is completely filled where does the remaining pigeon go. The diagram seen here demonstrates the Dirichlet’s principle. It shows that there is n number of pigeon holes, but more than n pigeons are present. To prove this principle, mathematical induction can be used. Base case: if n is a positive integer and n+1 objects are placed into n boxes, then at least one of the boxes will contain two or more objects(Discrete Mathematics). Proof: 1+2+……n=(n+1)/2 (i) To prove : K=11k= (1)(1+1)/2 1 =1(ii)Prove: If K=1nk=n(n+1)/2 then k=1 n+1(n+1)((n+1)+1)/2Assume- K=1nk=n(n+1)/2Consider- k=1 n+1k=K=1nk + (n+1) This proof shows that p(1) is the base case and p(n)—-> p(n+1) is the inductive step. The statement hold for n=1 and whenever the statement holds for n=k, it must also hold for n=k+1, then the statement holds for all positive integers, N.The pigeonhole principle can also be used in real life situations and scenarios. Some of which include, for example,BirthdayTwo or more people in school have the same birthday We know that there are in total 366 days in a year, including leap year and a school consists of more than 366 students. When each of the first 366 students has their birthdays on different days from January 1st to December 31th, the birthday of the 367th person must be a repeat of one of those days. Which means there are definitely two of the students who have their birthday falling on the same day. A suit of Cards Another example is that if 5 cards are picked from a standard deck of 52 cards, then at least two cards will be in the same suit.Each of the five cards have a possibility of being from one of the four suits, so we have five cards (pigeons)here but four suits(pigeonholes). By the pigeonhole principle, if four of the cards each belongs to the four suits, then the fifth card has to belong to the same suit as one of the four cards(Mind Your Decisions). The average value = 5/4 so the maximum must be at least that, and since we can’t pick a fraction of a card, there must be at least two cards of the same suit.At a business meeting, no one shakes their own hand and no one shakes another person’s hand more than once. To prove that there are 2 people who have shaken hands the same number of timeSuppose there are n people. The minimum number of handshakes is 0. The maximum number of a handshake is n-1.If someone has shaken hand with n-1 people then there is no one who has shaken hands with 0 people. So we have n number of people and at most n-1 possible number of handshakes, so by the pigeonhole principle there must be 2 people who have shaken hands the same number of timesThis example also demonstrates the pigeonhole principleConsider any five points P1……., P5 in the interior of a square S with the side length of 1. To show that two of the points are at the most distance of ?2/2 apart.Proof- Consider dividing the square into 4 subsquare. By the pigeonhole principle, 2 of the points must be in one of the sub-boxes. The distance between those two must be less than the diameter of the sub-box(Pigeonhole). A more stronger form of the pigeonhole principle is the generalized pigeonhole principle, this form is that “If k is a positive integer and N objects are placed into k boxes, then at least one of the boxes will contain ?N/K? or more objects”(Discrete Mathematics). ?x? is called the ceiling function, which represents the round up value of x (Discrete Mathematics). It states that there must be at least two objects in the same box when there are more objects than boxes. Proof for the generalized pigeonhole principle is that assume N objects are placed into k boxes. So, there is at least one box containing at least N/K objects.To prove by contradiction, “assume none of the boxes contain more than n/k-1 so the total number is at most k(N/k-1) < k ((N/k+1)-1) = N. there is a contradiction because there are a total of N objects"(Shafiei). If There are 50 baskets of apples. Each basket contains no more than 24 apples. Show that there are at least 3 baskets containing the same number of apples. To prove this generalized pigeonhole principle can be used. : The baskets are the pigeons, and we place each of them in one of 24 pigeonholes according to how many apples are in it. Thus the ratio n/k of pigeons to pigeonholes is 50/24 = 2112(Schafer) . By Generalized PHP there are at least this many baskets with the same number of apples, so there must be at least 3.Another example of the generalized pigeonhole principle is that among 200 people there at least 17 who were born in the same month. By using the pigeonhole principle, suppose that for each month there is a box containing persons with birthdays on that month. The number of boxes is 12 and the number of people is 200. By the generalized pigeonhole principle, at least one of these boxes contain at least ?200/12?=17 persons. So, there must be at least 17 people who were born in the same month. Exploring further into the pigeonhole principle, there is a second form of pigeonhole principle and a third form. The second form of the pigeonhole principle states that for "any positive integers n, and t, if tn+1 or more objects are placed in n boxes, then at least one box will have more than t objects"(Chiou). To prove this if each of the boxes contains at most t objects, them n boxes will contain at most t*n objects.this contradicts the fact that tn+1 or more objects are placed in the boxes. An example of this is, how many people at least in a group of 85 people have the same last initials. So if 85 people are the pigeons and 26 letter are the pigeon hole. Then by using the second form of the pigeonhole principle, n=85,=26 and that 85>3. 25=78.Thus k=3 and so the minimum number of people having the same last initial is k+1=4. The third form of pigeon hole is “If the average of positive numbers is , then at least one of the numbers is greater than or equal to” (Chiou). Also, at least one of the numbers is less than or equal to . To prove this Let a1,a2……,an be the numbers. Then by data Hence, if each of the n numbers a1, a2, …….an. is less than t then the sum of these numbers will be less than , contradicting .A similar argument shows that at least one of the numbers is less than or equal to. In conclusion, the pigeonhole principle is the concept that if more than n objects are placed into n boxes, then at least one box must contain more than one object. This is an important topic to know because it allows you to apply it to real world situations. This topic can be further researched by looking more into Infinite Pigeonhole principle. It relates to pigeonhole principle by that if given an infinite set of objects, if they are arranged in a finite number of places, there is at least one place with an infinite number of objects.Other topics that allow for further research on pigeonhole principle are graph theory and combinatorics.