本文是数学专业的留学生作业范例，题目是“The Pigeonhole Principle Forms(鸽子洞原理的形成)”，鸽子洞原理。学生将其重新定义为数学原理的基本概念背后的常识;如果有n个物体要放置在m个容器中(m < n)，那么至少有两个物品必须放入同一个盒子中。虽然这个想法是常识性的，但在一个有能力的数学家手中，它可以被用来做非凡的事情。鸽子洞原理最著名的应用之一就是纽约市至少有两个人头上有相同数量的头发。
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.
让我们通过形象化一些日常生活中与鸽子洞原理相关的尴尬时刻来简化这个问题。有时，我早上很早就起床准备上课。但是，房间里还是黑的，我的室友还在睡觉。让我想想，我抽屉里有三种不同颜色的袜子，找起来杂乱无章。那么，我怎样才能在不打扰同伴(也就是开灯)的情况下，最方便地挑选一双颜色相同的袜子呢?简单的数学就能解决这个问题。我只需要从抽屉里拿出4只袜子!当然，这是现实生活中应用的鸽子洞原理。
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.
如果n个鸽子洞中放置了mn + 1只鸽子，那么至少会有一个鸽子洞中有m + 1只或更多只鸽子。然而，这个鸽子洞原理并没有告诉我们如何定位包含两只或更多鸽子的鸽子洞。它只是断言存在一个包含两只或更多鸽子的鸽子洞。
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 RESULTS OF RESEARCH AND REAL WORLD EXAMPLES
CASE 1 : LOSSLESS DATA COMPRESSION情况1:数据无损压缩
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.
实际上，对于任何减少文件大小的无损压缩，如果我们考虑长度为N的文件，如果所有文件都同样明显，那么压缩文件的预期长度(所有长度为N的可能文件的平均长度)必然大于N。因此，如果我们不知道要压缩的数据的属性，我们可能根本就不会压缩文件。无损压缩算法只有在我们更喜欢压缩特定类型的文件而不是其他类型的文件时才会派上用场;在此之后，该算法可以以更好的方式压缩这些类型的数据。
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情况2:镖靶
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.
综上所述，虽然鸽子洞原理看起来很简单，但是，这个主题对于帮助人们设计和平滑各种重要数学问题的计算和证明步骤是非常有用的。这个原则在我们的生活中很有用，虽然它看起来很简单。这一原则也可以应用在我们的日常生活中，无论我们是否意识到它。当问题可以用我们知道的方式解决时，通过使用这一原则是很有趣的。
数学作业相关专业范文素材资料，尽在本网，可以随时查阅参考。本站也提供多国留学生课程作业写作指导服务，如有需要可咨询本平台。