The Pigeonhole Principle Forms

PIGEONHOLE PRINCIPLE. Student redefine this as common sense behind this basic idea of this mathematical principle; if there are n objects to be positioned in m receptacles (with m < n), at least two of the items must go into the same box. Whereas the idea is commonsensical, in the hands of a capable mathematician it can be made to do extraordinary things. There is one of the most famous applications of Pigeonhole Principle which there’s at least two people in New York City with the same number of hairs on their head.

The principle itself is attributed to Dirichlet in 1834, although he in fact used the term Schubfachprinzip. The same maxim is often named in honour of Dirichlet who used it in solving Pell’s equation. The pigeon seems to be a fresh addition, as Jeff Miller’s web site on the first use of some math words gives,

“Pigeon-hole principle occurs in English in Paul Erdös and R. Rado, A partition calculus in set theory, Bull. Am. Math. Soc. 62 (Sept. 1956)”.

In a recent debate on a history group Julio Cabillon added that there are a variety of names in different countries for the idea. His list incorporated,

Le principe des tiroirs de Dirichlet, French for the principle of the drawers of Dirichlet

Principio da casa dos pombos in Portuguese for the house of pigeons principle

Das gavetas de Dirichlet for the drawers of Dirichlet.

Dirichlet’s principle

The Box principle

Zasada szufladkowa Dirichleta which mean the principle of the drawers of Dirichlet in Polish

Schubfach Prinzip which mean drawer principle in German

INTRODUCTION

Let’s make this thing easier by visualize some common daily awkward moment which related to Pigeonhole Principle. Sometimes, I wake up and get ready for classes early in the morning. But then, the room still dark and my room-mate still in sleep. Let see, I have socks of three different colours in my drawer and to be found in messy order. So, how can I pick a matching pair of same coloured socks in most convenient way without disturbing my partners (which mean turning on the light)? A simple math will overcome this problem. I just have to get only 4 socks from the drawer! Of course it’s the Pigeonhole Principle applied in the real life.

Get Help With Your Essay

If you need assistance with writing your essay, our professional essay writing service is here to help!
Find out more about our Essay Writing Service

So, what is Pigeonhole Principle then? Let put an example to demonstrate this principle. For instance, there are 3 pigeonholes around. There are 4 pigeon and each of them holds one mail. The pigeons are delivering the mails and have to place all of its mails into available pigeonholes. With only 3 pigeonholes around, there clear to be 1 pigeonhole with at least 2 mails!

Thus, the general rule states when there are k pigeonholes and there are k+1 mail, then they will be 1 pigeonhole with at least 2 mails. A more complex version of the principle will be the following:

If mn + 1 pigeons are positioned in n pigeonholes, then there will be at least one pigeonhole with m + 1 or more pigeons in it. However, this Pigeonhole Principle tells us nothing about how to locate the pigeonhole that contains two or more pigeons. It only asserts the existence of a pigeonhole containing two or more pigeons.

The Pigeonhole Principle sounds trifling but its uses are deceiving astonishing! Thus, in our project, we intend to learn and discover more about the Pigeonhole Principle and illustrate its numerous interesting applications in our daily life.

RESULTS OF RESEARCH AND REAL WORLD EXAMPLES

CASE 1 : LOSSLESS DATA COMPRESSION

Lossless data compression algorithms cannot guarantee compression for all input data sets. Frankly says, for any (lossless) data compression algorithm, there will be an input data set that didn’t get reduced in size when processed by the algorithm. This is effortlessly proven with elementary arithmetic using a counting argument, as follows:

Assume each particular file is represented as a string of bits (in count of arbitrary length)

We inference that there is a compression algorithm that transforms everything of the file into a different file which the size is reduced than the original file, and that in any case one file will be compressed into something that is shorter than itself.

Let M be the least number such that there is a file F with length M bits that compresses to something shorter. Let N be the length (in bits) of the compressed version of F.

F = File with length M

M = Least number that compressed into something shorter

N = length (in bits) in compressed version of F

Since N < M, each file of length N keeps its size throughout the compression. There are 2N such files. Together with F, this makes 2N + 1 files which all compress into one of the 2N files of length N.

2N < 2N + 1

But 2N is smaller than 2N + 1, consequently from the pigeonhole principle there must be some file of length N which is at the same time, the output of the compression function on two different inputs. That file cannot be decompressed dependably (which of the two originals suppose to be yield?), which contradicts the assumption that the algorithm was lossless.

Hence, we can finalize that our original hypothesis (that the compression function makes no file longer) is necessarily fallacious.

For any lossless compression algorithm that turns some files shorter, must automatically make some files longer, but it is not necessary that those files become very much longer. Most practical compression algorithms provide an “escape” facility that can turn off the normal coding for files that would become longer by being encoded. Then the only increase in size is a few bits to let know the decoder that the normal coding has been turned off for the whole input. In example, for every 65,535 bytes of input, DEFLATE compressed files never need expansion by more than 5 bytes.

In reality, for any lossless compression that reduces the size of some file, the expected length of a compressed file (averaged over all possible files of length N) must necessarily be greater than N if we consider files of length N, if all files were equally apparent. So if we don’t have any idea about the properties of the data we are considering for a compressing, we probably not compress the file at all. A lossless compression algorithm is only come in handy when we are prefer to compress a particular types of files than others; after that the algorithm could be intended to compress those types of data in a much better way.

Whenever opting for an algorithm always means implicitly to select a subset of all files that will become usefully shorter. This is the theoretical reason why we suppose to consider different kind of compression algorithms for different kinds of files: there are almost impossible for an algorithm that perfect for all kinds of data. Algorithms are generally quite exclusively tuned to a particular type of file such like this example; lossless audio compression programs do not work well on text files, and vice versa.

Above all, files of random data cannot be consistently compressed by any likely lossless data compression algorithm: undeniably, this result is used to define the concept of randomness in algorithmic complexity theory.

CASE 2 : DARTBOARD

Another kind of problem requiring the pigeonhole principle to solve is those which involve the dartboard. In such questions, the general shape and size of Dartboard which are known, a given number of darts are thrown onto it. Then we determine the distance between two convinced darts is. The hardest part is to define and identify its pigeons and pigeonholes.

EXAMPLE 1

On a circular dartboard of radius 10 units, seven darts are thrown. Can we prove that there will always be two darts which are at most 10 units apart?

To demonstrate that the final proclamation will always true, we first have to divide the circle into six equivalent sectors as shown;

Therefore, we allowing each of the sectors to be a pigeonhole and each dart to be a pigeon, we have seven pigeons to be passed into six pigeonholes. By pigeonhole principle, there will be at least one sector containing a minimum number of two darts. The statement is proven to be true in any case since the greatest distance involving two points lying in a sector would be 10 units.

In actual fact, it is also possible to prove the scenario with only six darts. In such a case, the circle this time is redefined into five divided sectors and all else follows. But then, put attention that this is not always true to any further extent if we use five darts or less.

EXAMPLE 2

On a dartboard which is formed as a regular hexagon of side length 1 unit, nineteen darts are then thrown. How would we prove that there will be two darts within units each other?

All over again, we have to identify our pigeonholes by dividing the hexagon into six equilateral triangles as illustrated below.

While the 19 darts as pigeons and with the six triangles as the pigeonholes, we uncover that there must be in any case one triangle with a minimum of 4 darts in it.

Now, considering another scenario, we will have to endeavour an equilateral triangle of side 1 unit within 4 points inside.

If locate all the points as far apart from each other as possible, we will come to conclusion of conveying each of the first three points to be at the vertices of the triangle. The fourth or the last point will then be exactly at the centre of the triangle. Since we realize that the distance from the centre of the triangle to each vertex is of the altitude for this triangle, that is, units, we can find that it is unquestionable potential to find two darts which are units apart within the equilateral triangle.

CONCLUSIONS

In conclusion, although the Pigeonhole Principle seems to be simple, but, this topic is very useful in helping someone to devise and smooth the progress of calculation and proving steps for various important mathematical problems. This principle is very useful in our life although it seem so simple. This Principle also can be applied in our daily life, whether we realizes it or not. It is fun when the problem can be solved in a way that we know, by using this principle.

RECOMMENDATIONS

We would like to provide you some recommendation on making the Pigeonhole Principle far more interesting like:

• Using variety of leaning materials and variety of examples to help student to get more understand the Pigeonhole Principle.
• Create a well imagination of what are the real things about the Pigeonhole Principle.
• Search more information from the internet about the Pigeonhole Principle.
• Make a lot of exercise that is related about the Principle.
• Make a group discussion and discussed about the topic.