The Pigeonhole Principle PDF

Preview

Summary

The Pigenhole Principles...

Description

The Pigeonhole Principle Discrete Structures

The Pigeonhole Principle Acknowledgement The research opportunity was a great chance for learning and professional development. Therefore, I consider myself as very fortunate individual as I was provided with an opportunity to be a part of it. I express deepest thanks to my instructor for Discrete Mathematical Structures, Faria Jameel, who in spite of being extraordinarily busy with her duties, took time out to give necessary advices and guidance which were extremely valuable for this task, both theoretically and practically. I choose this moment to acknowledge her contribution gratefully. Without her contribution, it would not have been easier for me. I perceive this opportunity as a big milestone in my career development. I will strive to use gained skills and knowledge in the best possible way, and will continue to work on their improvement, in order to attain desired career objectives.

1

The Pigeonhole Principle Contents o Summary………………………………………………………………………………………………………………3 o Pigeonhole principle..................................................................................................4 o First pigeonhole principle……………………………………………………………………………………..5 o Second Pigeonhole Principle…………………………………………………………………………….....6 o Generalized pigeonhole principle…………………………………………………………………………7 o Daily life examples……………………………………………………………………………………………….8 o Applications of pigeonhole principle……………………………………………………………………9 o Computer related application………………………….…………………………………………………10 o Conclusion………………………………………………………………………………………………………….12 o References………………………………………………………………………………………….…………….13

2

The Pigeonhole Principle

Summary The pigeon hole principle says if you have fewer pigeon holes than pigeons and you put every pigeon in a pigeon hole, then there must result at least one pigeon hole with more than one pigeon. It is surprising how useful this can be as a proof strategy. It has many generalizations. For instance: If you have N pigeons in K holes, and (N/K) is not an integer, then some hole must have strictly more than (N/K) pigeons. So 16 pigeons occupying 5 holes means some hole has at least 4 pigeons. If you have infinitely many pigeons in finitely many holes, then some hole must have infinitely many pigeons. If you have an uncountable number of pigeons in a countable number of holes, then some hole has an uncountable number of pigeons. Pigeonhole principle is applicable in many things occurring in our life, be it sock picking, or counting the number of our hair, or knowing how many people present here share the same birthday as yours. Pigeonhole principle is also applicable in field of computer sciences in hash tables. A hash table is a data structure that associates keys with values. They claim that it can store about 32 bit of data in itself, if the data exceeds, obviously the table will have to put the remaining data in the filled boxes. Here, the condition of n>m is applicable, considering n is the data and m is the memory of the hash table.

3

The Pigeonhole Principle

Pigeonhole Principle In mathematics, the pigeonhole principle states that if n items are put into m containers, with n> m, then at least one container must contain more than one item. The first formalization of the idea is believed to have been made by Peter Gustav Lejeune Dirichlet in 1834 under the name Schubfachprinzip ("drawer principle" or "shelf principle"). For this reason it is also commonly called Dirichlet's box principle, Dirichlet's drawer principle or simply "Dirichlet's principle".

An image of pigeons in holes. Here there are n = 10 pigeons in m = 9 holes. Since 10 is greater than 9, the pigeonhole principle says that at least one hole has more than one pigeon.

4

The Pigeonhole Principle

First Pigeonhole Principle If n items are put into m pigeonholes with n > m (m, n∈ N ∗), then at least one pigeonhole must contain more than one item. Proof: Assume all the pigeonholes contain at most one item, then the maximum number of the total items that the n pigeonholes can contain is n, which is less than m. By contradiction, there must be at least one pigeonhole contains more than one item.

Birthday Paradox On one hot summer day, a primary school is holding a big birthday celebrating party for the old headmaster, Professor Edison. On the party, Mark, a-grade-two pupil, asked his mother a question:”Mom, how many people are there on the party of Professor Edison?”“367.” His mother answered. “Is there anyone sharing the same birthday?” 1: If n pigeons are randomly placed in m pigeonholes with uniform probability of 1/m, then at least one pigeonhole will hold more than one pigeon with probability of 1 –m !( m −n)! m n 2. “No, I don’t think so, everyone’s birthday is different.” “You must have counted wrongly.” Mark smiled. “No it couldn’t be. I counted it twice.” Mark’s mother argued. “In mathematics, the situation that 367 students, in the house, sharing the same birthday can’t happen.” (This story is an example of the First Pigeonhole Principle)

5

The Pigeonhole Principle

Second Pigeonhole Principle If (mn−1) items ate put into n pigeonholes where m,n∈N ∗, then there will be at least one pigeonhole which must contain less than m item(s).

Proof: Assume all the pigeonholes contain greater than or equal to m item(s), then the minimum number of the total items that the n pigeonholes can contain is m×n, which is greater than (mn−1). By contradiction, there must be at least one pigeonhole contains less than m item(s).

Apple Problem Professor Francois de Ciel, who is teaching at a primary school, wants to teach his class about simple calculation this morning. He intends to use apples as bonus when the kids are getting correct answers. When he is holding those fresh apples from basket in his hands, an idea came to his mind: Can he distribute those 19 apples to 9 children with everyone got two apples and no apple is left? With the condition that he does not eat any apple. The answer must be impossible, but what’s the reason behind it? (This story is an example of the Second Pigeonhole Principle)

6

The Pigeonhole Principle Generalized Pigeonhole Principle The pigeonhole principle can be generalized as follows: If each of N objects is to be assign one of k labels, then there are sure to be at least N/k objects with the same label. Proof: Suppose for each of the k labels we have less than N/k objects of that label. Then the number of objects is less than k. N/k=N , which is not the case. Thus at least one label is used N/k or more times. Example: Among 2000 people, at least six were born on the same day of the year. Reason: Label each person with the day on which he/she was born. There are 366 possible labels and 2000 people assigned those labels. At least 2000/366≈ 5.46 people, that is, six people have the same label. Example: Six integers are chosen at random from the set {1, 2, 3, …, 9, 10}. Prove that two of the chosen integers are sure to have an odd sum. Answer: Label each of the integers as either “even” or “odd.” As there are at most five of each label we must have two integers of opposite label. These sum to an odd value. Example: If 865 points are scattered in a one-foot by one-foot square, then at least seven points are clustered sufficiently close together as to lie in a one-inch by one-inch square.

Reason: Divide the square into 144 one-inch by one-inch squares. Notice that 865/144 ≈6.007 .

7

The Pigeonhole Principle Daily Life Examples This theorem is exemplified in real-life by truisms like "there must be at least two right gloves in a group of three gloves". It is an example of a counting argument, and despite seeming intuitive it can be used to demonstrate possibly unexpected results; for example, that two people in London have the same number of hair on their heads. Followings are the detailed examples for pigeonhole principles. Sock-picking Assume you have a mixture of black socks and blue socks, what is the minimum number of socks needed before a pair of the same color can be guaranteed? Using the pigeonhole principle, to have at least one pair of the same color (m = 2 holes, one per color) using one pigeonhole per color, you need only three socks (n = 3 items). Hand-shaking If there are n people who can shake hands with one another (where n > 1), the pigeonhole principle shows that there is always a pair of people who will shake hands with the same number of people. As the 'holes', or m, correspond to number of hands shaken, and each person can shake hands with anybody from 0 to n − 1 other people, this creates n − 1 possible holes. This is because either the '0' or the 'n − 1' hole must be empty (if one person shakes hands with everybody, it's not possible to have another person who shakes hands with nobody; likewise, if one person shakes hands with no one there cannot be a person who shakes hands with everybody). This leaves n people to be placed in at most n − 1 non-empty holes, guaranteeing duplication. Hair-counting We can demonstrate there must be at least two people in London with the same number of hairs on their heads as follows. Since a typical human head has an average of around 150,000 hairs; it is reasonable to assume (as an upper bound) that no one has more than 1,000,000 hairs on their head (m = 1 million holes). There are more than 1,000,000 people in London ( n is bigger than 1 million items). Assigning a pigeonhole to each number of hairs on a person's head, and assign people to pigeonholes according to the number of hairs on their head, there must be at least two people assigned to the same pigeonhole by the 1,000,001st assignment (because they have the same number of hairs on their heads) (or, n > m). For the average case (m = 150,000) with the constraint: fewest overlaps, there will be at most one person assigned to every pigeonhole and the 150,001st person assigned to the same pigeonhole as someone else. In the absence of this constraint, there may be empty pigeonholes because the "collision" happens before we get to the 150,001st person. The principle just proves the existence of an overlap; it says nothing of the number of overlaps (which falls under the subject of Probability Distribution).

8

The Pigeonhole Principle Applications of Pigeonhole Principle Decision Making Strategy for Optimum Outcome Using Pigeonhole Principle In daily life, the Pigeonhole Principle is a useful method to help people solve some realistic problems, such as following cases: Case 1: Jason is blind and he lives alone. In total, there are 5 different pairs of socks with 5 colors respectively in his closet. It would be easy for him to distinguish them if the socks, present in front of him, are in pairs. In order to save time, what’s the maximum number of socks taken by him will ensure there is a pair of socks? Solution: As a blind man, it is always hard for Jason to find out the suitable pair of socks with same color from the closet. If there are 5 different pairs of socks in his closet in total and he can feel and determine whether two socks in his hand are a pair or not. By the Pigeonhole Principle, treating the socks as the pigeons, only if 6 socks being taken out would ensure there is at least a pair. Case 2: In an experiment, the scientists want to find two people with the ABO blood group. In order to save time, the blood samples will be collected and processed simultaneously. What’s the smallest number of samples that should be collected? Solution: It is known that there are 4 types of blood in ABO blood grouping system, namely A, B, AB, and O. If we treat them as 4 pigeonholes, and consider the patients as pigeons (to be put into the holes). To ensure there are at least two pigeons in a hole, the scientists should pick up at least 5 samples.

9

The Pigeonhole Principle Computer Related Application of Pigeonhole Principle Pigeonhole principle in hash tables: A hash table is a data structure that associates keys with values. The primary operation it supports efficiently is a lookup: given a key (e.g. a person's name), find the corresponding value (e.g. that person's telephone number). It works by transforming the key using a hash function into a hash, a number that is used to index into an array to locate the desired location ("bucket") where the values should be. Key-value pairs are quite common in real world data, and hash tables are both reasonably efficient in storage and quite fast at lookups, offering O(1) performance in most cases. That's why hash tables are the go-to data structure for many programmers. It may not be the optimal choice, but unlike so many things in computer science, it's rarely a bad choice. But hash tables do have one crucial weakness: they are only as good as the hash function driving them. As we add each new item to the hash table, we compute a hash value from the key for that item, and drop the item in the bucket represented by that hash value. So how many buckets do we need? Let's consider the extremes: 

If we had one giant bucket, everything would get piled in together. We'd have to look at each and every item in our one bucket to find the one we want, which reduces us to worst-case performance: an O(n) linear search.



If we had exactly the same number of buckets as items, each item is placed in its own unique, individual bucket. We know each bucket will contain one, and only one, item. That's a perfect hash function, delivering best-case performance: an O(1) lookup. Reality, of course, lies somewhere in between these two extremes. The choice of hash function is critical, so you don't end up with a bucket shortage. As you place more and more items in each bucket (i.e., "collisions") you edge closer to the slow O(n) end of the performance spectrum. There's something magical about these hash functions that drive the hash table. The idea of the hash as a unique digital fingerprint for every chunk of data in the entire world is a fascinating one. It's a fingerprint that cleverly fits into a mere 32 bits of storage, yet is somehow able to uniquely identify any set of data ever created.

10

The Pigeonhole Principle Of course, this is a lie, for several reasons. Let's start with the most obvious one. Consider all possible values of a 32-bit hash function: 232 ~= 4.3 billion The current population of the earth is about 6.6 billion people. If we were to apply a perfect 32bit hash function to the DNA of every man, woman, and child on the planet, we could not guarantee uniqueness-- we simply don't have enough possible hash values to represent them all! This is known as the pigeonhole principle. It's not complicated. If you try to put 6 pigeons in 5 holes, one will inevitably be left out in the cold.

11

The Pigeonhole Principle Conclusion Over hundreds of thousands of years, the Pigeonhole Principle has been applied into our real life applications. It states that, whenever given boxes and objects, at least one box must contain more than one object. This statement has important applications in number theory and was first stated by Dirichlet in 1834. Based on many real life cases, it has been noticed since ancient Greeks and Egyptians. By proving and developing the Pigeonhole principle, mathematicians derived more powerful and helpful theories from it, like A.V.P, Ramsey theory, and principle of inclusion and exclusion so that we can solve problems which seem quiet complex. In addition, all these principles and theories are discovered from the phenomena in daily life, abstracted away from the particular examples, becoming valid anywhere. Pigeonhole principle is applicable in many things occurring in our life, be it sock picking, or counting the number of our hair, or knowing how many people present here share the same birthday as yours. Pigeonhole principle is so useful in the field of computers even. It is used in Hash tables; a hash table is a data structure that associates keys with values. They claim that it can store about 32 bit of data in itself, if the data exceeds, obviously the table will have to put the remaining data in the filled boxes. Here, the condition of n>m is applicable, considering n is the data and m is the memory of the hash table. We only touched the shallow surface of the principle in the view of mathematics and applied applications. There are still many things, even seem to be simply but with hidden truths and mysteries, remaining to bed is covered and uncovered.

12

The Pigeonhole Principle References http://en.wikipedia.org/wiki/Pigeonhole_principle http://io9.com/why-the-pigeonhole-principle-is-one-of-maths-most-power-1601025172 http://www.academia.edu/3249779/Pigeonhole_Principle_Real_Life_Applications_and_Mathe matical_Investigation http://www.jamestanton.com/wp-content/uploads/2013/01/Microsoft-Word-UNIT20_Pigeonhole-Principle.pdf http://blog.codinghorror.com/hashtables-pigeonholes-and-birthdays/

13...