Twenty-third Annual UNC Math Contest Final Round January 31, 2015 SOLUTIONS 1. The sum of three consecutive integers is 54. What is the smallest of the three integers? ANSWER: 17 SOLUTION: The sum of three consecutive integers is three times the average, or middle, integer, so the middle integer is 54/3 = 18 and the smallest is 17. Another approach is to write the three integers as n, n+1, and n+2 and compute 54=n+(n+1)+(n+2)=3n+3 so 51=3n and 17=n. 2. Find the area of the shaded region. The outer circle has radius 3. The shaded region is outlined by half circles whose radii are 1 and 2 and whose centers lie on the dashed diameter of the big circle. ANSWER: 3π SOLUTION: The area of the shaded region is the area of a circle of diameter radius 2 minus the area of a circle of radius 1 = 4π − π = 3π. One elegant way to see this is to reflect the top half of the diagram left to right. 3. If P is a polynomial that satisfies P( x2 + 1) = 5x4 + 7x2 + 19, then what is P( x )? ANSWER: P( x ) = 5x2 − 3x + 17 SOLUTION: P is clearly quadratic. Let P( x ) = Ax2 + Bx + C. Then P( x2 + 1) = A( x2 + 1)2 + B( x2 + 1) + C = Ax4 + 2Ax2 + A + Bx2 + B + C = Ax4 + (2A + B) x2 + ( A + B + C ). Therefore, A = 5, 2A + B = 7, and A + B + C = 19. Solve for A, B, and C. 4. Tarantulas A, B, and C start together at the same time and race straight along a 100 foot path, each running at a constant speed the whole distance. When A reaches the end, B still has 10 feet more to run. When B reaches the end, C has 20 feet more to run. How many more feet does Tarantula C have to run when Tarantula A reaches the end? ANSWER: 28 SOLUTION: In the time A travels 100 feet, B travels 90 feet. Thus B travels at a speed 9/10 the speed of A. Similarly, C travels at a speed 8/10 the speed of B and (8/10)(9/10)=72/100 the speed of A. When A has gone 100 feet, C has gone 72 feet and has 100-72=28 feet to go. 5. A termite nest has the shape of an irregular polyhedron. The bottom face is a quadrilateral. The top face is another polygon. The sides comprise 9 triangles, 6 quadrilaterals, and 1 pentagon. The nest has 10 vertices on its sides and bottom, not counting the several around the top face. How many edges does the top face have? You may use Euler’s polyhedral identity, which says that on a convex polyhedron the number of faces plus the number of vertices is two more than the number of edges. (A vertex is a corner point and an edge is a line segment along which two faces meet.) ANSWER: 8 SOLUTION: F = 1 bottom + 1 top + 9 triangles + 6 quadrilaterals +1 pentagon= 18 faces. Let n be the number of edges around the open top. Then there are also n vertices on the rim and the total number of vertices is V = 10 + n. Count 9 × 3 edges on triangles, 7 × 4 edges on quadrilaterals (including the bottom), and so on. Observe that this will count each edge two times. So 2E = 9 × 3 + 7 × 4 + 1 × 5 + n = 27 + 28 + 5 + n = 60 + n. Using the Euler identity, we obtain 18 + 10 + n = (1/2)(60 + n) + 2 or n = 8. 6. How many ordered pairs (n, m) of positive integers satisfying m < n ≤ 50 have the property that their product mn is less than 2015? ANSWER: 1197 SOLUTION: Note that 50 × 40 = 2000 so for n = 50, m = 1, 2, 3, . . . , 40. There are 40 such pairs. For n = 49 clearly m can be 40. Try 49 × 41 = 2009. For n = 49, m = 1, 2, 3, . . . , 41. For n = 48 clearly m can be 41. Try 48 × 42 = 2016. No! For n = 48, m = 1, 2, 3, . . . , 41. For n = 47 m = 1, 2, 3, . . . , 42. For n = 46 m = 1, 2, 3, . . . , 43. For n = 45 m = 1, 2, 3, . . . , 44. From now on, all m ≤ n will work. Adding up, we get 1 + 2 + . . . + 44 plus 43 + 42 + 41 + 41 + 40. The first sum is 44 × 45/2 = 22 × 45 = 990 and the second is 200 + 3 + 2 + 1 + 1 = 207. The total is 1197. Alternative way of looking at this one: There are 50×2 49 = 1225 ordered pairs (n, m) that satisfy m < n ≤ 50. Because most of them will satisfy the inequality mn < 2015, it is easier to concentrate on counting the exceptions (shown in the shaded region ) that satisfy mn > 2015 but n ≤ 50, hence m > 40. 48 The bounding curve nm = 2015 is a hyperbola, mirrorsymmetric across the line m = p n. By mirror sym√ metry, the tangent line through ( 2015), 2015) has slope −1. The shaded region is convex, so it lies above this tangent line, √ inside the triangular region defined by m + n > 2 45 = 89.7 . . .. Since we seek only integer solutions, this narrows the field of candidates to m + n ≥ 90. There are 30 lattice points in the triangular 46 Out[299]= 44 42 42 44 46 48 50 region that lie on or above this border-line. It seems probable that most of these candidates will lie in the shaded region, but now we must check carefully if any of the points on or above the border-line are false solutions (not actually on the shaded region). Points (m, n) on this line can be written in parametric form as n = 45 + t, m = 45 − t. Since (45 + t)(45 − t) = 2025 − t2 it is easy to create this table of values for (n, m, n ∗ m) for the small values of t of interest: n= 45 46 47 48 49 50 m= 45 44 43 42 41 40 n ∗ m = 2025 2024 2021 2016 2009 2000 Note that the last two points (49, 41) and (50, 20) lie outside the shaded region. Thus there are 30 − 2 = 28 candidates that remain. One can check easily (numerically) that the lattice points immediately above these two discarded false solutions are true solutions; that is, all candidates have been classified, and all lattice point solutions in the shaded region are now accounted for. Take 1225-28= 1197. 7. (a) Give an example of a polyhedron whose faces can be colored in such a way that each face is either blue or gold, no two gold faces meet along an edge, and the total area of all the blue faces is half the total area of all the gold faces. A blue face may meet another blue face along an edge, and any colors may meet at vertices. Describe your polyhedron and also describe how to assign colors to the faces. (b) Show that if the faces of a polyhedron are colored in such a way that each face is either blue or gold and no two gold faces meet along an edge, and if the polyhedron contains a sphere inside it that is tangent to each face, then the total area of all the blue faces is at least as large as the total area of all the gold faces. ANSWER: (a) One possible example is a square box with large top and bottom and small height, with the top and bottom colored gold and the four sides blue. If the top and bottom are squares of side s, then the total area colored gold is 2 × s2 . If the height of the box is h, then the total area colored blue is 4 × h × s. It is easy to select s and h to make 4 × h × s equal to half of 2 × s2 . Set 4 × h × s = s2 or 4 × h = s. Choose, say, h = 1 and s = 4. (b) Triangulate each face by connecting the point of tangency on the face to each vertex of the face. Look at a gold face and one of the triangles into which it has been cut. The gold triangle meets a blue triangle along the edge where the two faces meet. Consider the two triangles and the radii that go from the tangent points on the two faces (=the apexes of the triangles) to the center of the sphere. By symmetry, the two triangles are congruent. This means that for each triangle colored gold, there is a congruent triangle colored blue. Therefore, the total area colored blue is at least as large as the total area colored gold. G More detail: We are told that each face has a point of tangency to the sphere. Each face is perpendicular to the radius that connects the center of the sphere to the point of tangency. Consider a pair of faces that meet along an edge, as in the diagram. P G Using the radii, which are perpendicular to the respecF tive faces, we can find some congruent triangles. Call the far end of the edge in the diagram P and the center C of the sphere C. Call the point of tangency of one face F and the point of tangency of the other face G. The segments FC and GC are radii and so have the same length. The segments FP and GP lie in the faces so they are perpendicular to the radii to those two faces. This makes triangles CFP and CGP both right with right angles at F and G. They have the common hypotenuse PC and F they each have legs the length of the radius of the sphere. This makes them congruent (by the Hypotenuse-Leg rule for right triangles) and tells us that FP and GP have the same length. P There is another pair of congruent right triangles: Just replace P with the other end of the edge, Q: Triangles C CFQ and CGQ are also congruent. This will give us the result about color. Consider a face colored gold- the pentagon in the example, say. Triangulate it by connecting the point of tangency to each vertex. Consider one of the gold triangles: we know it meets a blue face and that the blue face contains a triangle that is congruent to the gold one. Therefore, the amount of surface area that is blue is at least as large as the amount that is colored gold. G F Q 8. A garden urn contains 18 colored beetles: 6 red beetles, numbered from 1 to 6, and 12 yellow beetles, numbered from 1 to 12. In random order, beetles wander out of the urn, one at a time, without any going back in. What is the probability that the sequence of numbers on the first four beetles to wander out is steadily increasing, that is, that the number on each beetle to wander out is larger than the number on the beetle before and that no number is repeated? Give your answer as a fraction in lowest terms. You may leave the numerator and denominator in a factored form. ANSWER: 157/(18 × 17 × 16) or 157/4896 SOLUTION: There are 18 numbered beetles that can wander out of the urn and therefore 18 × 17 × 16 × 15 ways for a sequence of four beetles to emerge. There are two copies of each number ≤ 6 and a single copy of each of the numbers ≥ 7. Categorize the possibilities in which the numbers increase into disjoint cases. Case 1: All 4 beetles have numbers ≤ 6. There are C (6, 4) combinations of 4 distinct numbers ≤ 6. Once we have selected the 4 numbers, there is only one way to list them in increasing order. Each number ≤ 6 occurs on 2 different beetles in the urn. There are 24 C (6, 4) ways to create strictly increasing sequences of 4 distinct numbers ≤ 6. Case 2. The first 3 beetles have numbers ≤ 6 and the last one out has a number ≥ 7. There are C (6, 3) combinations of 3 distinct numbers ≤ 6. Each of the 3 numbers occurs on 2 beetles. There are 6 possibilities for the fourth number and the fourth number chosen is on only one beetle: 23 C (6, 3)C (6, 1) Case 3. The first 2 beetles have numbers ≤ 6 and the last 2 have numbers ≥ 7: 22 C (6, 2)C (6, 2) Case 4. The first beetle has a number ≤ 6 and the last three have numbers ≥ 7: 2C (6, 1)C (6, 3) Case 5. All four beetles have numbers ≥ 7: C (6, 4) Total number of possibilities that give increasing sequences: = 24 (64) + 23 (63)(61) + 22 (62)(62) + 2(61)(63) + (64) = (24 ) 6×4×5×3×4×2 3 + (23 )( 6×3×5×2 4 )(6) + (22 ) 6×2 5 6×2 5 + 2(6)( 6×3×5×2 4 ) + 6×4×5×3×4×2 3 = 3 × 785. Total number of random sequences: 18 × 17 × 16 × 15. Probability of the sequence being increasing is the quotient: (3 × 785)/(18 × 17 × 16 × 15) = 785/(18 × 17 × 16 × 5) = 157/(18 × 17 × 16) = 157/4896. Note on generating functions: Those students familiar with the binomial theorem may recognize the sum 24 (64) + 23 (63)(61) + 22 (62)(62) + 2(61)(63) + (64) as the coefficient of x4 in the product (1 + 2x )6 (1 + x )6 . In fact, the problem can be worked by the method of generating functions, as follows. Think of picking an increasing sequence of numbers on the emerging beetles as selecting either 0 or 1 beetle with the number 1, then selecting either 0 or 1 beetle with the number 2, and so on. Since there are two beetles with each of the numbers ≤ 6, the generating function for each of those numbers is 1 + 2x. There is just one beetle with each of the numbers ≥ 7, so the generating function for each of those numbers is 1 + x. The combined generating function for increasing sequences is thus (1 + 2x )6 (1 + x )6 . The number of increasing sequences of length 4 is the coefficient of x4 . Finish the problem by finding that coefficient and taking the quotient with 18 × 17 × 16 × 15. (Finding the coefficient is a bit of work.) 9. Starting at the node in the center of the diagram, an orb spider moves along its web. It is permissible for the spider to backtrack as often as it likes, in either direction, on segments it has previously travelled. On each move, the spider moves along one of the segments (curved or straight) to some adjacent node that is different from the node that it currently occupies. (a) How many different five-move paths start at the center node and end at the center node? (b) How many different seven-move paths start at the center node and end at the center node? ANSWER: (a) 264 SOLUTION: (a) The various types of paths can be listed and counted. Let O stand for a move to any outside point from the inside, I stand for a move to the inside (center) point, and X stand for a move from any outside point to any other outside point along any path. There are three cases: OXXXI, OXIOI, OIOXI with the following numbers of different paths, respectively, 3 × 4 × 4 × 4 × 1 = 192, 3 × 4 × 1 × 3 × 1 = 36, 3 × 1 × 3 × 4 × 1 = 36. Total=264 ANSWER: (b) 5700 SOLUTION: (b) The various types of paths can be listed and counted, as before. This time the possibilities are OIOIOXI, OIOXIOI, OIOXXXI, OXIOIOI, OXIOXXI, OXXIOXI, OXXXXOI, OXXXXXI. Count as before. Alternatively, work as in the keypad question on the First Round. Label the center node x and the peripheral nodes as a, b, c. Let An , Bn , Cn , and Xn represent the number of paths of length n that start at the center x and end at the nodes a, b, c, x respectively. Now extend the paths one extra step, and use the diagram to deduce this highly symmetrical system of recurrence equations: An+1 = 2Bn + 2Cn + Xn Bn+1 = 2An + 2Cn + Xn Cn+1 = 2An + 2Bn + Xn Xn+1 = An + Bn + Cn ; hence Xn+2 = An+1 + Bn+1 + Cn+1 . Add the top three equations to deduce that the X values satisfy Xn+2 = An+1 + Bn+1 + Cn+1 = 4Xn+1 + 3Xn Next use this recurrence equation to eventually solve for X7 , as follows. Note that by inspection of the network, X1 = 0, X2 = 3. Insert these into the recurrence formula to deduce X3 = 4(3) + 3(0) = 12. Likewise X4 = 4(12) + 3(3) = 57, X5 = 4(57) + 3(12) = 228 + 36 = 264, X6 = 1227 and finally X7 = 5700. 10. (a) You want to arrange 8 biologists of 8 different heights in two rows for a photograph. Each row must have 4 biologists. Height must increase from left to right in each row. Each person in back must be taller than the person directly in front of him. How many different arrangements are possible? (b) You arrange 12 biologists of 12 different heights in two rows of 6, with the same conditions on height as in part (a). How many different arrangements are possible? Remember to justify your answers. (c) You arrange 2n biologists of 2n different heights in two rows of n, with the same conditions on height as in part (a). Give a formula in terms of n for the number of possible arrangements. ANSWER: (a) 14 (b) 132 1 2n 2n 2n 2n 2n 1 2n + 1 (2n)! (c) = − = − = = n+1 n n n−1 n n+1 2n + 1 n (n + 1)!n! These are the Catalan numbers and there are many acceptable forms for them. Any of the forms listed here, for instance, are acceptable answers. SOLUTION: (a) Either list the 14 arrangements or refer to the reasoning shown for either of parts (b) or (c). Here is a systematic list in a lexicographic order: FFFFBBBB; FFFBFBBB; FFFBBFBB; FFFBBBFB; FFBFFBBB; FFBFBFBB; FFBFBBFB; FFBBFFBB; FFBBFBFB; FBFFFBBB; FBFFBFBB; FBFFBBFB; FBFBFFBB; FBFBFBFB. Keep in mind as you list that acceptable strings have the 4 Fs and 4 Bs and the Bs never outnumber the Fs as you move left to right. SOLUTION:(b) We can use a better system than listing. Line up the biologists by height. Start filling in seats. Each new person must go in the next empty seat in either the front row or the back row. Look at the patterns and keep track of how many of the seating arrangements begin with j Fs and k Bs. We will construct a table. (See below.) When j=k we have two full rows: this is what (a) and (b) ask about, j=k=4 and j=k=6. There will be no arrangements with k bigger than j (more B’s than F’s so far) so all entries above the diagonal are 0. 1F & 0B or 2F & 0B, etc. are easy. There is one arrangement with each of these, so the first column is all 1s. Next column, the column with 1 in the back row: 1F & 1B one way. 2F & 1B two ways. Notice that to get 2F & 1B then just before you added the most recent biologist, you had either 1F & 1B and added an F or you had 2F & 0B and added a B. This means each entry is the sum of entry to left + entry above. Fill in the table. 0B 1B 2B 3B 4B 5B 6B 1F 1 1 0 0 0 0 0 2F 1 2 2 0 0 0 0 3F 1 3 5 5 0 0 0 4F 1 4 9 14 14 0 0 5F 1 5 14 28 42 42 0 6F 1 6 20 48 90 132 132 The 4F & 4B entry is the 14 from part (a). For part (b) we want the 6F & 6B entry, 132. SOLUTION: (c) First select n of the 2n biologists to go in the front row. There are (2n n ) ways to make this selection. Given a selection, the front row people and the back row people can be put in order so that height increases left to right. Some of these seating arrangements will satisfy the condition that every person in the back row is taller than the person in front and some of the arrangements will not. We will count how many violate this condition and subtract that from (2n n ). Number the biologists in order of height and then write down FFBBFB.... to record whether each person is seated in the front row or the back row. All (2n n ) of our arrangements have equal numbers of F and B, because we selected n for the front row. The strings that satisfy the last requirement are exactly the strings that have the property that as you count from left to right, the total number of F’s never exceeds the total number of B’s. We want to count the strings that violate this. We will associate to each of the "bad" strings one unique string of n + 1 F’s and n − 1 B’s in such a way that each "bad" string has such an unbalanced string and that each such n + 1/n − 1 string has exactly one "bad" string associated with it. Then all we have to do is count how many of these unbalanced strings there are, the ones with n + 1 F’s and n − 1 B’s. That is, of course, (n2n −1). Here is the association: given a "bad" string, move from left to right until you first have more F’s than B’s. Leave that first excess F in place. To the left of that F you will have equal numbers of F’s and B’s. To the right of that F you will have one more B than F. In every place to the right of the F, change every F to a B and every B to an F. The new string will have n + 1 F’s and n − 1 B’s. To check that the assignment is reversible, consider a string with n + 1 F’s and n − 1 B’s. As you move from left to right, there is a first place the number of F’s exceeds the number of B’s. To the left of that F, the string is balanced. Switch all the F’s and B’s to the right of this F. The resulting string will be the "bad" balanced string that went with the unbalanced string. Therefore, the number of good strings 2n 1 2n is (2n n ) − (n−1). This expression is an acceptable answer. It is also easily simplified to n+1 ( n ). BONUS: You arrange 12 biologists of 12 different heights in three rows of 4, with the same conditions on height as in part 10(a) for all three rows. How many different arrangements are possible? ANSWER. 462 SOLUTION: Work as in part (b), but with a third index for the third row. We will call the rows A, B, and C. The recursive rule for filling in the table is similar to the rule in part (b), but for a three-dimensional array, displayed below in a compressed format as follows: the upper left number in each box is for 0C; the next one is for 1C, and so on. The last entry in the table represents (4A, 4B, 3C) =462. However, this will also equal the next recursive entry: (4A, 4B, 4C) =462. 0B 1B 1 1 0 !A 0 0 1 2 0 2A 2B 1c 2c 3c 1 0 0 3 0 3 6 0 0 0 1 4A 0 4 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 3A 0 5 0 4B 0 2 0 1 3B 0 0 0 0 0 0 5 1c 2c 3c 5 0 16 21 0 21 42 0 0 42 9 14 14 35 70 84 56 168 252 0 210 0 0 462

© Copyright 2016 ExploreDoc