CS 2104 Problem Solving in Computer Science OOC Assignment 10 ------------------------------------------------------------------------------- 1. [20 points] Let O be the origin of the xy-plane. Suppose five more points on the xy-plane, none the same as O, are selected. Prove that there must be two points, call them P and Q, among those five points, such that the angle ANGLE(POQ) is acute. Hint: apply the Pigeonhole Principle. Let the pigeonholes be the four quadrants; for clarity, assign the positive x-axis to quadrant I, the positive y-axis to quadrant II, the negative x- axis to quadrant III, and the negative y-axis to quadrant IV. Then, by the pigeonhole principle, there must be some quadrant that contains two or more of the five points. Pick any two of those points (in the same quadrant) and call them P and Q. Then, since the boundaries of each of the quadrants form right angles, ANGLE(POQ) must be less than 90 degrees, which is the definition of an acute angle. 2. [30 points] During a tour of the Wonka Chocolate Company®, the tour group is presented with a Wonka SuperBar®, which is an rectangular slab composed of equal-sized sections, separated by break lines. It is your job to separate sections of the Wonka SuperBar® and give one of the sections to each member of the group. You may pick up any piece of the bar that consists of more than one section and separate that piece into two pieces along any vertical or horizontal break line that goes from one side of the piece to the other. Fortunately there are people in the tour group. a) What is the smallest number of breaks you can make to supply each member of the group with one section? Why? You start with a single piece of chocolate. Each break increases the number of pieces of chocolate by 1, since each break turns what was a single piece into two pieces. So, it's obvious that you must perform n - 1 breaks in order to have n pieces of chocolate. b) What is the largest number of breaks you can make to supply each member of the group with one section? Why? The discussion in part a) makes it clear that the number of breaks needed is absolutely fixed. Note: if you thought of stacking two pieces and breaking them at once, that still involves making TWO breaks as described above. 3. [xx points] A group of N people are standing in a large field, in such a way that no pair of people is the same distance apart as any other pair of people. Each of the N people is holding a numbered ball. All of the people are now told to toss the ball they are holding to the person who is closest to them. They all do so. a) Prove that if N is odd then there is one person to whom no one tosses a ball. Suppose that everyone does receive a ball. Now, it is not possible that this is achieved by people pairing up and exchanging balls, since N is odd. But, that implies there would be a cycle of people, essentially a circle of people who each toss their ball to the next person in the cycle. But that's not possible. Pick the person with the minimum distance to his/her neighbor as a starting point. Now as we proceed around the cycle, each person must be closer to the person he/she tosses to than the person after him/her in the cycle. So, we have a strictly increasing sequence of distances as we go around the cycle. Then the preceding person (along the cycle) would not have thrown his/her ball to this person, since the preceding person would have to be closer to the one before him/her. (Remember that distance measurement is symmetrical.) Therefore, there cannot be a cycle of people tossing balls to each other, and therefore someone must not receive a ball. b) Is the same event possible if N is even? Why? Absolutely. For example, suppose we have four people standing in a line as below: A B C D ----------------- 1 5 6 8 Now, A tosses to B, B tosses to C, C tosses to B, and D tosses to C. But no one will toss to A. On the other hand, it may not occur: A B C D -------------------- 1 2 6 8 4. [10 points] There are 10,000 different four-digit telephone numbers in the dorms on the VT campus, and more than half of them are located in rooms that are higher than the second story of the building in which they are located. Prove that there must be a telephone number located in a room above the second story in its building that is the sum of two other telephone numbers that are also located in rooms above the second story in their building(s). Note: the word "other" was an error in the problem statement. With that word included, it is possible to find an example showing the claim here is false. I am dropping this question due to the typo in the problem statement. 5. [10 points] A collection of 27 disks are laid on a table in a rectangular arrangement of 9 rows and three columns. Each disk is either red or blue. Prove that there is a rectangle, with sides running along rows and columns of the arrangement of disks such that the four disks at the corners of the rectangle are all the same color. There are three disks in each row, each of which is either red or blue. Now, there are exactly 8 different ways to form a row of three such disks: RRR, RRW, RWR, WRR, RWW, WRW, WWR, WWW Since there are nine rows, by the pigeonhole principle, at least two of the rows must have the same pattern of red and blue disks. Each of those rows must contain at least two red disks or at least two white disks. In the former case, we would have a rectangle with four red corners; in the latter case, we would have a rectangle with four white corners.