A Deep Dive into the “Pigeon Hole Principle”
● Definition and Idea: Pigeon hole principle states that if x objects or items are placed in y containers with the number of x greater than y, then at least one of the containers must contain more than one x. Basically in simple terms, this principle states that when more amount of object are placed in fewer number of containers, at least one of those containers will contain more than one items. This theory is valid as long as the number of items is greater than the number of containers. If the number of items is equal or below the number of containers, this theory becomes invalid.
● Example: Lets say that we have 10 cars but only 9 garages and we must store all 10 cars. Then, at least one of those garage will have more than one car. This is simply the Pigeon hole principle.
● Generalized form of Principle given by, If n number of items are placed in k number of containers, at least one of those containers should contain [n/k] items.
● Example: If there are 100 students, how many students possibly share the same birth month?
-Number of students(n)=100
-Number of months(k)=12
according to the pigeon hole principle=[n/k]=[100/12]=8.33
Since half a person does not exist, and 8 x 12 = 96, we will add one and make it 9. So, 9 students possibly share a birth month.
● Pigeon Hole Principle Theorem: This theorem states that if “A” is the average number of pigeons per hole and A is not an integer, then:
-At least one hole must contain pigeons greater than or equal to the average number of pigeons per hole. This is called the ceiling function.
-The remaining pigeonholes must contain pigeons less than or equal to the average number of pigeons per hole. This is called the flooring function.
To understand this theorem clearly, lets take 10 pigeons and 3 holes. So then, the average number of pigeons per hole is 3.3
Practically, there can not exist 0.3 of a pigeon. and there are 10 pigeons so half of a pigeon is not possible. So, if we round the 0.5 as 1, then at least one of those holes must contain pigeons greater than 3.3. This is known as the ceiling function as the number of pigeon in one of the hole is greater than the average number of pigeons per hole. Then, the rest of the hole contain 3 pigeon per hole since the calculation is 3+3+4. Which satisfies the condition of the rounding down condition of the flooring function which states that the remaining pigeon holes must be less than or equal to the average which in this case is less (3 < 3.33).
Get Pawan’s stories in your inbox
Join Medium for free to get updates from this writer.
The mathematical notation for this is Kn+1 where n is the number of pigeon holes, k= number of items that can be taken without guarenteeing the result.
● Example: A bag contains 10 red marbles, 10 white marbles, and 10 blue marbles. What is the minimum number of marbles that must be chosen randomly to ensure that we get 4 marbles of the same color?
-Number of marbles required = 4
To avoid getting 4 marbles of the same color, we can choose at most 3 marbles of each color.
3 red + 3 white + 3 blue = 9 marbles
After choosing 9 marbles, we still do not have 4 marbles of the same color.
Therefore, the next marble chosen must make one of the colors reach 4.
3 + 3 + 3 + 1 = 10
Therefore, the minimum number of marbles required is:
10 marbles
● Pigeonhole Principle Strong Form Theorem: The Strong Form of the Pigeonhole Principle states that if q₁, q₂, …, qₙ are positive integers and
q₁ + q₂ + … + qₙ — n + 1 objects are placed into n boxes, then at least one box must contain the required number of objects. In simple words, if we want to avoid having q₁ objects in the first box, q₂ objects in the second box, and so on, the maximum number of objects we can put in each box is q₁ — 1, q₂ — 1, …, qₙ — 1 respectively. Therefore, the maximum number of objects we can place without reaching any required number is q₁ + q₂ + … + qₙ — n. If we add one more object, making the total q₁ + q₂ + … + qₙ — n + 1, then at least one box must contain at least its required number of objects.
● Example: A box contains 6 red, 8 green, 10 blue, 12 yellow and 15 white balls. What is the minimum no. of balls we have to choose randomly from the box to ensure that we get 9 balls of same color?
-Here, we cannot blindly apply the Strong Form of the Pigeonhole Principle.
First, if we apply the formula directly, we get 47 because 6 + 8 + 10 + 12 + 15–5 + 1 = 47.
However, this answer is not correct because the red and green balls have fewer than 9 balls, so it is not possible to get 9 balls of the same color from them. Therefore, we only need the blue, yellow, and white balls. Since we are picking the balls randomly, we could pick all 6 red balls and all 8 green balls before getting 9 balls of the same color.
Now, applying the Pigeonhole Principle to the blue, yellow, and white balls, we get 9 + 9 + 9–3 + 1 = 25.
Therefore, we add the 6 red and 8 green balls that could be picked first: 6 + 8 + 25 = 39. Hence, to guarantee getting 9 balls of the same color, we have to pick 39 balls from the box.
● Applications: The Pigeonhole Principle can be used in many different areas to solve problems where objects are being placed into different groups or containers. Some common applications are:
-Computer Science: In computer science, the Pigeonhole Principle is used in hashing. When many data items are placed into a smaller number of buckets, two or more items must sometimes end up in the same bucket. This is called a collision.
-Coding Theory: In coding theory, the Pigeonhole Principle helps us understand errors in messages. If there are more messages than the number of available codewords, some different messages will have to use the same codeword. This can cause problems when sending or receiving the messages.
-Number Theory: In number theory, the Pigeonhole Principle can be used to prove that certain things must exist. For example, among any n + 1 integers, there must be at least two integers whose difference is divisible by n.
-Graph Theory: In graph theory, the Pigeonhole Principle can be used to prove that certain relationships must exist between objects. For example, in a group of people, there must be some people who either have a common friendship or a common non-friendship.
