The-Pigeonhole-Principle.外文文献.doc

The Pigeonhole PrincipleAmy BystromIn partial fulfillment of the requirements for the Master of Arts in Teaching with a Specialization in the Teaching of Middle Level Mathematicsin the Department of Mathematics.David Fowler, AdvisorJuly 20101The Pigeonhole PrincipleIn 1834, the mathematician Peter Gustav Dirichlet (1805-1859), developed the idea of what we know today as the Pigeonhole Principle (2009). It is also commonly called Dirichlets “box principle” or Dirichlets “drawer principle” in different parts of the world. The Pigeonhole Principle is a very basic and easy concept to comprehend, yet when applied to higher-level problem solving can very difficult to detect and use (2009). This powerful Pigeonhole Principle may be presented in a few different ways: 1.) If m pigeons are put into m pigeonholes, there is an empty hole if and only if theres a hole with more than one pigeon, 2.) If n pigeons are put into m pigeonholes where nm, theres a hole with more than one pigeon, 3.) Let |A| denote the number of elements in a finite set A. For two finite sets A and B, there exists a 1-1 correspondence f: A-B if and only if |A| = |B| (Bogomolny, 2010).To get a better understanding of how the Pigeonhole Principle is actually used, below are some examples of the application of this useful idea. With each example, however, connections between the pigeons and the pigeonholes will be distinguished to help understand what action needs to be done with each problem. The first couple of examples will be basic problems followed by more challenging and higher-level problems.The first problem is stated as such: The maximum number of hairs that can grow on a human head is 500,000. Show that in a city of 7,500,000 residents, there must be at least 15 people with the same number of hairs on their heads.Now, to begin solving this problem, think of it as the 7,500,000 residents as pigeons and the 500,000 hairs as the pigeonholes. When dividing the number of residents2(pigeons) by the number of hairs (pigeonholes), the number of people with the same number of hairs on their heads, which in this case is 15, would be the result. Another way to explain the solution to this problem is by setting up 500,001 pigeonholes labeled by integers 0-500,000, and placing the residents of New York into holes labeled by the number of hairs on their heads. Since 7,500,000 14 x 500,001 + 1 one can conclude by the Pigeonhole Principle that there is a pigeonhole with at least 14 + 1 pigeons or there are at lease 15 residents of New York with the same number of hairs.Another example that uses the Pigeonhole Principle is the following: if a map of Nebraska is divided into regions and colored with two colors, there must be two points with the same color exactly one mile apart.To begin this problem, form an equilateral triangle on the map where each line segment or side is of equal distance of each other (say one mile apart). In this particular problem, visualize each of the three vertices as pigeons and the two colors as pigeonholes. This is the same as saying that there are at least two pigeons in one pigeonhole). If each of the three vertices were colored one of the two colors, one could conclude that at least two of the vertices will be of the same color exactly one mile apart.As we move into the more higher-leveled problem solving, the pigeons and pigeonholes will be a little harder to detect. These next problems may seem as if they have nothing in common with the previous two problems, but the amazing thing is that3they do! The next example states: given n integers, either one of the integers is a multiple of n, or some of the integers add up to a multiple of n.Begin this problem by labeling the n integers by a1, a2, a3,.,an. These represent individual integers. Next, define Si to be the sum of the first i integers in our list: S1= a1; S2= a1 + a2 ; S3= a1 + a2 + a3; Sn=a1 + a2 + a3 + + an.Just from the information given, if one of the values S1, S2, , Sn is a multiple of n, we can be done with the problem. However, what if none of the numbers S1, S2, , Sn is a multiple of n?If this is true, then all possible remainders when dividing these numbers by n are 1, 2, 3, , n -1. This is where the pigeons and pigeonhole comes into play. The n sums are the pigeons and the n-1 possible remainders are the pigeonholes. If this is the case, within the numbers S1, S2, , Sn, there are two numbers, one could call them Sp and Sp+b, that give the same remainders when divided by n. The problem is complete becauseSp+b- Sp is a multiple of n and because Sp+b- Sp = ap+1 + ap+2 + ap+3 + ap+b.This next problem is easier to explain by looking at visuals. Again, it is a more complex problem to solve, but within it still holds the Pigeonhole Principle. The problem states, given a real number r, prove that among the first 99 multiples of r there is at least one that differs from an integer by not more than 1/100.To began this problem take a basic number line and roll it into a circle with a circumference of one. We visualize traveling from 0 to 1 as one trip around the circle, from 1 to 2 as another, and so on for all positive integers, ie. traveling between any two integers is one lap around the circle.401Now, divide the circle into 100 arcs of equal lengths.99 0 1100 100Since any real number lies between two integers, every real must have a spot on the circle, and so must land in one of the arcs. If at least one multiple kr, where 1 k p, lie on the same arc of length 1/100. This indicates that kr pr = (k p) r is one of the given 99 multiples and that kr pr lies on one of the arcs of (99/100 0 or 0 -1/100).The next problem can be completed in a couple of different ways. Below is a visual for this particular one because it allows for students to actually see the Pigeonhole5Principle for themselves. 41 rooks are placed on a 10 x 10 chessboard. Show that youcan choose 5 that do not attack each other.To begin this problem, lets first determine the pigeons and pigeonholes. In thiscase, the rooks are the pigeons and the ten rows are the pigeonholes. Next, a 10 x 10chessboard was created to allow readers to visualize this problem. The 41 rooks werethen placed on ten rows on the board.Since there are 41 rooks in 10 rows, some row contains at least 5 rooks. Label this row A,and then disregard row A in the following steps.The remaining 9 rows have at least 41 - 10 = 31 rooks. The Pigeonhole principleimplies the existence of a row with at least 4 rooks. Label one of these rows B andremove it from the following steps.There is now at least 3 rooks in one of the remaining 8 rows, call it row C. Again,as before, discard row C, leaving at least 41-2x10 = 21 rooks.Now, there is a row among the remaining 7 rows with at least 2 rooks, and label it as rowD. Again, as before, discard row D, leaving at least 41-3x10 = 11 rooks.There is now at least 1 rook in the remaining 6 rows, and consider one of t