![]() ![]() ĥ) A skyscraper has 101 floors numbered 1 to 101. Thus, you should conclude that their distance is less than or equal to (2) 1/2. By the Pigeonhole Principle there are two points into one of the sectors. SOLUTION: partition the circle with four circular sectors, each having a right angle at the center of the circle. ![]() SOLUTION: argue in a fashion similar to Problem 2, partitioning the given cube with 8 smaller cubes obtaining bydissecting it with planes parallel to the sides.Ĥ) What can you conclude if you place five points inside a circle of radius one? (Do you see why?).ģ) Prove that if nine points are placed on a cube having sides of length 2, then there must be two points that are at most 3 1/2 units apart. Since the sides of S are of length 1/2, the Pythagorean theorem tells us that the diagonal has length (2) -1/2. By the Pigeonhole Principle, there must be two points lying in one of these squares S. SOLUTION: partition the square into four parts, each of them a square this time, by drawing two lines throughout the center of the square, and parallel tothe sides. SOLUTION: done in class, by considering four triangles.Ģ) Sharpen the previous result by proving that if five points are placedon a square having sides of length one, then there must be two points that are at most (2) -1/2 units apart. But s > n+1 implies s-1> n and again by inductive hypothesisone of the first n boxes holds two or more balls.ġ) Show that if five points are placed on a square having sides oflength one, then there must be two points that are at most 1 unit apart. But s > n+1 implies s > n and so by inductivehypothesis one of the first n boxes contains more than one ball, and we aredone.įinally, let us consider the case in which the Box n+1 has just oneball:in this case, the remaining s-1 balls are placed into the first n boxes. So it remains to consider the case in which the Box n+1 contains eitherno ball or exactly one ball.In the first case the s balls are distributedamongst the first n boxes. If Box n+1contains more than one ball,we are done. For convenience label the boxes, from Box 1, to Boxn+1. Let us prove the principle holds for n+1 boxes.We have s balls (s > n+1)placed into n +1 boxes. So let us prove the "if more than n balls are placed into n boxes there existsone box that contains more than one ball"īasis Step:for n=1, we have only one box and more than one ball already placedinto that box.So, it is clear that the conclusion is true for n=1.Īssume the principle holds true for n boxes. SOLUTION: This has been provedin class by contradiction.Now we are being asked to prove it by induction. ![]() It is not possible to cover a chessboard with dominoes that each cover exactly two squares if the squares in the two diagonally opposite corners have been removed.0) Prove the Pigeonhole Principle by induction. The reverse of our assumption must be true: This is clearly impossible, so we have our desired contradiction. By the pigeon-hole principle, two of the black squares must be covered by the same domino. These 31 dominoes will be our "pigeon-holes". With 62 places to be covered, 31 dominoes will be needed. Each domino, no matter how it is placed on the board to cover exactly two squares will always cover exactly one black square and exactly one white square. These 32 black spaces will play the role of our "pigeons". Consequently, there are only 30 white squares left from the original 32 on a complete board, while the number of black squares remains unchanged at 32. Without loss of generality, let's suppose the two corners removed were both white. Note that the diagonally opposite corners of a complete chessboard are of the same color. We argue indirectly, using the pigeon-hole principle.Īssume it is possible. ![]() However, if the two diagonally opposite corners are removed, this changes. It is certainly possible to cover a chessboard with dominoes that each cover exactly two squares. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |