2016 UNCO Math Contest II Answer Key

1)

2)

3)

4) There are eighteen such numbers:

5)

6) (a) \frac{15−\sqrt{65}}{8}

7. Evaluate S = ∞ ∑ n=2 4n (n 2 − 1) 2 Answer: 5 4 Solution Using the partial fraction decomposition 4n (n 2−1) 2 = 1 (n−1) 2 − 1 (n+1) 2 and then expanding out the sum, we see a telescoping pattern of many canceling paired terms. ( 1 1 2 − 1 3 2 ) + ( 1 2 2 − 1 4 2 ) + ( 1 3 2 − 1 5 2 ) + ( 1 4 2 − 1 6 2 ) + . . . The only terms that do not cancel are the 1 1 2 and the 1 2 2 . The final infinite sum is ( 1 1 2 + 1 2 2 ) = 1 + 1 4 = 5 4 . A B C D E

8. Tree Each circle in this tree diagram is to be assigned a value, chosen from a set S, in such a way that along every pathway down the tree, the assigned values never increase. That is, A ≥ B, A ≥ C, C ≥ D, C ≥ E, and A, B, C, D, E ∈ S. (It is permissible for a value in S to appear more than once in the tree.) (a) How many ways can the tree be so numbered, using only values chosen from the set S = {1, . . . , 6}? (b) Generalize to the case in which S = {1, . . . , n}. Find a formula for the number of ways the tree can be numbered. For maximal credit, express your answer in closed form as an explicit algebraic expression in n. Answers. A. 994 B. 1 120n(n + 1)(n + 2)

8n 2 + 11n + 1 � = n 5 15 + 7n 4 24 + 5n 3 12 + 5n 2 24 + n 60 Solution Once values for A and C are selected, the restrictions on the remaining values imply that they can be chosen in this many ways: (i) B can be chosen A ways; (ii) D and E can be chosen independently, each in C ways. Thus the total number of choices is T = ∑ A=n A=1 (A ∑ C=A C=1 C 2 ). The inner sum simplifies to 1 6 A(1 + A)(1 + 2A) and the total sum is T = ∑ n A=0 p(A) where p(A) = 1 6 A 2 (1 + A)(1 + 2A) This polynomial can be summed by a variety of standard methods, such as the method of undetermined coefficients, Bernoulli number expansions, or the Newton interpolation formula based on forward differences. Below we outline a method based on the idea of expressing p(A) as a linear combination of binomial coefficients and then applying the Hockey Stick Summation Lemma to each term. The Hockey Stick Lemma states that the entries in Pascal’s Triangle satisfy for any fixed k ≥ 0, N ∑ A=0 � A + k k � = � N + k + 1 k + 1 � This is useful for summation of polynomials. As an example, observe that the binomial coeffi- cient ( A+2 3 ) = (A)(A+1)(A+2) 3! has a numerator expressible as a product of linear factors whose roots are consecutive integers. Incidentally, this product formula allows us to extend the binomial coefficients in a meaningful way, even to cases where A is negative. This example illustrates a basic principle: Every binomial coefficient is a product of linear factors that are shifted by consecutive integers. Conversely, any such product of linear factors is expressible as a binomial, hence can be summed by the Hockey Stick Lemma. With this in mind we rewrite the factorization p(A) = 1 6 [(A − 1) + 1]A(1 + A)(1 + 2A) = 1 6 [(A − 1)A(A + 1)(1 + 2A)] + 1 6 A(1 + A)(1 + 2A) = 1 6 [(A − 1)A(A + 1)(2(A + 2) − 3)] + 1 6 A(1 + A)(2(A + 2) − 3) so that it has been expressed in terms of products of consecutive linear factors. Some further multiplication gives p(a) = −1 2 (a − 1)a(a + 1) − 1 2 a(a + 1) + 1 3 (a − 1)a(a + 2)(a + 1) + 1 3 a(a + 2)(a + 1) which preserves the structure of the products of consecutive factors. Now for example, the first term involving ∑ n a=2 1 2 (a − 1)a(a + 1) can be evaluated by changing the summation index to k = a − 2 and then using the Hockey Stick: ∑ n−2 k=0 3 3!(k + 1)(k + 2)(k + 3) = 3 ∑ n−2 k=0 ( k+3 3 ) = 3( n−2+4 4 ) . The same method works for the other three terms to be summed.

9. Chess Masters Four identical white pawns and four identical black pawns are to be placed on a standard 8 × 8, two-colored chessboard. How many distinct arrangements of the colored pawns on the colored board are possible? No two pawns occupy the same square. The color of a pawn need not match the color of the square it occupies, but it might. You may give your answer as a formula involving factorials or combinations: you are not asked to compute the number. Answer: There are 64! 56!4!4! arrangements of the colored pawns on the standard board. Solution First choose four squares from the 64 on the board for the black pawns. There are 64! 60!4! possibilities. Then choose four squares from the 60 remaining squares for the white pawns. This gives 64! 60!4! 60! 56!4! = 64! 56!4!4! arrangements.

10. Chess Wallpaper How many distinct plane wallpaper patterns can be created by cloning the chessboard arrangements described in Question 9? Each periodic wallpaper pattern is generated by this method: starting with a chessboard arrangement from Question 9 (the master tile), use copies of that tile to fill the plane seamlessly, placing the copies edge-to-edge and corner-to-corner. Note that the resulting wallpaper pattern repeats with period 8, horizontally and vertically. When the tiling is done, the chessboard edges and corners vanish, leaving only an infinite periodic pattern of black and white pawns visible on the wallpaper. Regard two of the infinite wallpaper patterns as the same if and only if there is a plane translation that slides one wallpaper pattern onto an exact copy of the other one. You may slide vertically, horizontally, or a combination of both, any number of squares. (Rotations and reflections are not allowed, just translations.) Note that the wallpaper pattern depicted above can be generated by many different master tiles (by regarding any square 8 × 8 portion of the wallpaper as the master tile chessboard). The challenge is to account for such duplication. Remember that each master tile has exactly four pawns of each color. You may give your answer as an expression using factorials and/or combinations (binomial coefficients). You are not asked to compute the numerical answer. Answer: There are 1 32 h 64! 56!4!4! + 3 � 32! 28!2!2! � + 12� 16! 14!1!1! �i = 1 32 h ( 64 4 )(60 4 ) − 3 � ( 32 2 )(30 2 ) − 3( 16 1 )(15 1 ) � − 7( 16 1 )(15 1 ) i + 1 16 h 3 � ( 32 2 )(30 2 ) − 3( 16 1 )(15 1 ) �i + 1 8 h 7( 16 1 )(15 1 ) i = 9, 682, 216, 530 different wallpaper patterns. Solution By "8 × 8 pattern" we will mean a pattern as described in the question, that is, a standard 8 × 8 chessboard that has a light square in the upper left corner and that contains four black pawns and four white pawns. The difficulty in counting the wallpaper patterns generated by these 8 × 8 patterns is that two different 8 × 8 patterns sometimes produce the same wallpaper pattern. Moreover, the number of distinct 8 × 8 patterns that produce a particular wallpaper depends on the subpatterns of the pattern. We cannot simply divide the number of 8 × 8 patterns by a single integer to account for the duplication. We must sort the 8 × 8 patterns according to how much duplication they produce. Begin with any 8 × 8 pattern and extend it to its wallpaper. The other 8 × 8 patterns that produce the same wallpaper are exactly the patterns obtained by placing an 8 × 8 window over the wallpaper so that the upper left corner of the window is one of the light colored squares on the original board. There are 32 possible 8 × 8 patterns obtained this way, but some of these 32 may be duplicates. This duplication occurs precisely when the 8 × 8 board comes from a wallpaper that has sub patterns. This duplication is what we must account for. We show two different solutions. The first is a general system known as the Burnside method. The second solution directly counts the number of different patterns. Examine the possibilities, as follows. Consider any two squares in an 8 × 8 pattern and look at the two new 8 × 8 patterns obtained by placing an 8 × 8 window so that each of the two selected squares is in the upper left corner. If the resulting 8 × 8 patterns are identical then we say the two squares "match" for these boards and wallpapers. This means the two squares are functionally the same for this pattern. For instance, in the example shown here (the one shown in Question 9) all of the squares with black pawns match each other. All of the squares with white pawns match each other. All of the squares just to the right of a white pawn match each other, and so on. (It is patterns like this, the ones with subpatterns, that produce duplications.) Again consider a particular 8 × 8 pattern. If exactly k squares match one of the squares in the pattern, then exactly k squares match each of the other squares in the pattern. In the example, k = 4. The 64 squares in the 8 × 8 pattern are partitioned into families of matching squares with k members each. Thus k is a factor of 64. Because there are just four pawns of each color, k cannot be more than four. We conclude that k = 1, 2, or 4. Call the number of squares in each matching family the "symmetry number" of the 8 × 8 pattern. For the example, k = 4. Matching squares are the same color, so each family is either light or dark, and there are 32 k families of light squares and 32 k families of dark squares. The families are constructed so that putting the upper left corner of the 8 × 8 window at one square in the family always matches the 8 × 8 pattern that is obtained by putting the window at another square of the family and never matches the pattern obtained by putting the upper left corner of the window at a square from a different family. Each family produces one 8 × 8 pattern. Since the upper left corner is always light and since there are 32 k families of light squares, there are exactly 32 k different 8 × 8 patterns that generate the wallpaper pattern. For the pattern in the example, there are 32 4 = 8 different 8×8 patterns that generate the wallpaper pattern: put any of the light squares in the top two rows in the upper left corner. Each choice makes a different 8 × 8 pattern and all will produce the same wallpaper pattern. If you put any other square in the upper left corner, your 8 × 8 pattern will be the same as the pattern you get by choosing the square in the top two rows that matches your square. Rewrite the fact that there are 32 k different patterns for the wallpaper for a pattern with symmetry number k using multiplication instead of division, [symmetry number] × [number of different 8 × 8 patterns that generate the wallpaper] = 32 The 8×8 patterns can be grouped by their associated wallpaper patterns. There is a set of 8×8 patterns for each wallpaper pattern. If you combine all the sets for all the distinct wallpaper patterns you will get all the 8 × 8 patterns. Here is the first nice trick: The product [symmetry number] × [number of different 8 × 8 patterns that generate the wallpaper] can be viewed as the sum of one copy of the symmetry number for each pattern that generates the wall paper pattern. It is what you get if you add up all the symmetry numbers of all the 8 × 8 patterns for a single wallpaper pattern. That is, in symbols [symmetry number] × [number of different 8 × 8 patterns that generate the wallpaper] = ∑ k where the sum is taken over all the 8 × 8 patterns that generate the wallpaper pattern. For a single wallpaper pattern the symmetry numbers are all the same. The sum is a complicated way to write a simple quantity. So far we have obtained that for a single wallpaper pattern ∑ k = 32 where the sum is taken over all the 8 × 8 patterns that generate the wallpaper and k is the symmetry number of each 8 × 8 pattern. Now add up all the symmetry numbers for all the 8 × 8 patterns - not just for one single wallpaper, but for all the wallpaper patterns. That is, sum over all wallpaper patterns. On the right hand side, you will get 32 times the number of different wallpaper patterns!!!!!!!!!!!! That is, calling the number of different wallpaper patterns W, ∑ k = 32W. where the sum is now taken over all of the different 8 × 8 patterns for all of the wallpaper patterns and k is symmetry number. The plan is to find the sum of all the symmetry numbers of all the patterns and divide by 32. Remember that the symmetry number of a particular 8 × 8 pattern is the number of squares in that pattern that "match" the square in the upper left corner (include the corner itself). The sum of all the symmetry numbers is the sum of the number of squares that match the upper left corner, taken over all 8 × 8 patterns. We need to count all the squares that match the upper left corners in all the patterns. We could do this by counting those squares, 8 × 8 pattern by 8 × 8 pattern. Think of having a stack of cards, each with one of the patterns, and going through them, one by one, counting the squares that match the upper left corner. Here is the second nice trick: Turn this around and instead of counting pattern by pattern, look square by square. For each square in the 8 × 8 chessboard, count the number of 8 × 8 patterns for which that square matches the upper left corner. That is, instead of going card by card, go square by square. Pick a square and go through all the cards, counting the number of cards for which this square matches the upper left corner. Go through the stack once for each of the 64 squares. (This is similar to adding up all the entries in a matrix by either going row by row or going column by column.) It turns out that it is not hard to count square by square: None of the dark squares ever match the upper left corner, so the contributions from those squares are all zero. Now we must look at the 32 light squares. No square in any even numbered column or even numbered row can match the upper left corner. There are several ways to see this. Suppose the square diagonally below the upper left corner, for instance, matches the corner. Then so also does the next one diagonally down. And so on: there will have to be 8 matching squares. However, there are never more than four matching squares. We conclude that the square diagonally below the upper left corner will never match the corner. The reasoning is similar for all squares in even numbered rows or columns. There remain 16 squares to look at. The upper left square matches itself for all 8 × 8 patterns, so the number for this square is 64! 56!4!4! Suppose the third square in the top row matches the corner. Then so also do the fifth and seventh. We find that the pattern must consist of repeats of the first two columns and that there must be exactly one white pawn and one black pawn in those first two columns. Also, any such pattern will make this third square in the top row match the corner. Choose one of the 16 squares for the black pawn and one of the remaining 15 squares for the white pawn. There are 16! 14! such patterns. Similar analysis produces the numbers for the other squares. For instance, count how many patterns have the fifth square in the top row matching the corner. In this case we find the pattern consists of a repeat of the first four columns and that any pattern that consists of repeats of its first four columns will do. There will be two pawns of each color in those first four columns. Some of the patterns will have subpatterns in those first four columns, e.g. the second pair of columns could be a repeat of the first pair. The beauty of this method is that this does not matter here! We have 32 squares in which to place 2 black pawns and 2 white pawns. Choose 2 squares out of 32 and then 2 more out of the remaining 30. The number of patterns is 32! 28!2!2! Continuing, we obtain that the upper left corner square matches itself for all 64! 56!4!4! patterns, three of the squares (the one in the fifth column and first row, the one in the fifth row and first column, and the one in the fifth row and fifth column) match the corner for 32! 28!2!2! patterns, and the remaining twelve squares each match the corner for 16! 14! patterns. Summarizing, the count over all the 8 × 8 patterns of all the squares matching the upper left corner is 64! 56!!4!4! + 3( 32! 28!2!2!) + 12( 16! 14!1!1!). Divide by 32 to get the number of different wallpaper patterns. A second way to solve the problem: Direct enumeration Follow the first solution until you come to the "first nice trick." Instead of using the trick, we will attempt to enumerate the number of different patterns directly by counting the number of patterns with each symmetry number. Denote by Wk the number of different wallpaper patterns that have symmetry number k and denote by Bk the number of different 8 × 8 patterns that have symmetry number k. The statement above says that 32 k × Wk = Bk . The thing we have been asked to count is W = W1 + W2 + W4, the total number of distinct wallpaper patterns. To obtain W, we can count the Bk and compute W = ( 1 32 × B1) + ( 1 16 × B2) + ( 1 8 × B4) First we find B4, the number of distinct 8 × 8 patterns with symmetry number four. For each such pattern, the 64 squares fall into 16 families of 4 matching squares. From each family select the square that is in the highest row. If there are several in the same row, then take the one of those that is farthest left. This will partition the 8 × 8 pattern into four blocks of 16 squares. Each block will contain one black and one white pawn. The block containing the upper left square can be either the top two rows, the left two columns, or a 4x4 square. The pawns can occupy any two squares in the block, so there are 16 × 15 different possible blocks of each shape. Beginning with a two row block, one pattern results from repeating the block four times down the 8 × 8 pattern. Another results from cloning the first two rows and shifting them right two squares for the second two rows, to the right another two squares for the third pair of rows, and right another two squares for the last pair of rows. A third pattern results from cloning and shifting right four squares each time. A fourth pattern results from cloning and shifting right six squares. After that, the we come back to the original cloning with no shift. We conclude that four different 8 × 8 patterns can be obtained from a single choice of two rows that contains one pawn of each color. We get 4 × 16 × 15 patterns. Beginning with a square block, we obtain patterns in three ways. Cloning and tiling the 8 × 8 pattern with four of the clones gives one pattern. Clone the square block and put one copy in the upper left corner and one in the lower left corner. Put the other two in the right side of the square, but offset them so that they are shifted down two squares relative to the left side. This turns out to produce a pattern that will have as its assigned block its top two rows, so we do not obtain a new pattern. Lastly, we can put two of the 4x4 squares in the top half of the 8 × 8 pattern and put the other two below, offset by two squares. We find that each of the 16 × 15 different 4x4 blocks produces two new 8 × 8 patterns. Beginning with a two column block, one pattern results from repeating the block four times across the 8 × 8 pattern. Another results from cloning the first two columns and shifting them down two squares for the second two columns, down another two squares for the third pair of columns, and down another two squares for the last pair of columns. A third pattern results from cloning and shifting down four squares each time. A fourth pattern results from cloning and shifting down six squares. After that, the we come back to the original cloning with no shift. The second and fourth possibilities turn out to have already been counted among the patterns with the top two rows for blocks. The third possibility was already counted with the patterns whose block is 4x4. Thus only one of the ways to use the two column block produces new patterns. We conclude that in all there are 7 × 16 × 15 different 8 × 8 blocks with symmetry number 4. B4 = 7 × 16 × 15 and W4 = 4 32 × B4 = 1 8 × B4 = 1 8 × 7 × 16 × 15. Now we find B2, the number of distinct 8 × 8 patterns with symmetry number two. This time, the 64 squares fall into 32 families of 2 matching squares. Choose one square from each family just as in the case above. This time we obtain two possible shapes for the blocks and each block contains two pawns of each color. This time the block that contains the upper left corner can be either the top four rows or the left four columns. The pawns can occupy any four squares in the block, so there are ( 32 2 ) × ( 30 2 ) different ways to distribute the pawns in each block. In the case of B2, however, not all of the choices for filling the 32 squares produce a pattern with symmetry number 2. Blocks that have a subsymmetry will produce patterns with symmetry number 4. Reasoning as we did for finding B4, we find that if there is a subpattern, then the pattern is made in one of three ways. For the case of the block with four rows and eight columns either the right half of the rectangle is a clone of the left half, the bottom half of the rectangle is a clone of the top half, or the bottom half of the rectangle is the same as the top half shifted half way across the rectangle. The structure is analogous for the rectangular block with eight rows and four columns. In all these cases, we can obtain a pattern by placing one pawn of each color in a single one of the 16-square halves of the pattern. Thus the number of such blocks that produce patterns with symmetry number 4 instead of 2 is 3 × 16 × 15. We conclude that there are ( 32 2 ) × ( 30 2 ) − 3 × 16 × 15 useful basic blocks of 32 that are four rows by eight columns and the same number that are eight columns by four rows. There are two different 8 × 8 patterns that can be produced from each of these basic blocks- either clone the basic block to the other half of the 8 × 8 square or clone it and shift it half way. Cloning a vertical one and shifting half way will also be obtained by cloning a horizontal pattern and shifting half way. Thus, B2 = 3 × (( 32 2 ) × ( 30 2 ) − 3 × 16 × 15) and W2 = 2 32 × B2 = 1 16 × 3 × (( 32 2 ) × ( 30 2 ) − 3 × 16 × 15). Finding B1 is now easy, because each 8 × 8 pattern that does not have symmetry number 2 or 4 must have symmetry number 1. That is, B1 = total number of 8 × 8 patterns (computed in problem 9) −B2 − B4 = 64! 56!4!4! − 3 × (( 32 2 ) × ( 30 2 ) − 3 × 16 × 15) − 7 × 16 × 15 and W1 = 1 32B1 Now we compute W = ( 1 32 × B1) + ( 1 16 × B2) + ( 1 8 × B4) = 1 32� 64! 56!4!4! − 3(( 32 2 )(30 2 ) − 3 × 16 × 15) − 7 × 16 × 15� + 1 16� 3

( 32 2 )(30 2 ) − 3 × 16 × 15� � + 1 8 (7 × 16 × 15) For neatness, we can write 16 × 15 as ( 16 1 )(15 1 ) and 64! 56!4!4! as ( 64 4 )(60 4 ). This gives W = 1 32 h ( 64 4 )(60 4 ) −3 � ( 32 2 )(30 2 ) −3( 16 1 )(15 1 ) � −7( 16 1 )(15 1 ) i + 1 16 h 3 � ( 32 2 )(30 2 ) −3( 16 1 )(15 1 ) �i + 1 8 h 7( 16 1 )(15 1 ) i END OF CONTEST