|
|
| Line 8: |
Line 8: |
| | | | |
| | 4) There are eighteen such numbers: | | 4) There are eighteen such numbers: |
| − | <cmath>4, 9, 10, 14, 15, 21, 27, 35, 44, 50, 52, 68, 75, 76, 81, 92, 98, 99</cmath> | + | <math>4, 9, 10, 14, 15, 21, 27, 35, 44, 50, 52, 68, 75, 76, 81, 92, 98, 99</math> |
| | | | |
| | 5) <math>0.332</math> | | 5) <math>0.332</math> |
| | | | |
| − | 6) (a) <math>\frac{3}{4} | + | 6) (a) <math>\frac{3}{4}</math> |
| − | (b)</math>\frac{15−\sqrt{65}}{8} | + | (b)<math>\frac{15-\sqrt{65}}{8}</math> |
| | | | |
| | | | |
| − | 7. Evaluate | + | 7) <math>\frac{5}{4}</math> |
| − | 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) a)<math>994</math> |
| | + | b) <math>\frac{1}{120}n(n + 1)(n + 2)(8n^22 + 11n + 1)</math> |
| | | | |
| − | 8. Tree Each circle in this tree diagram is to be assigned
| + | 9) There are <math>\frac{64!}{56!4!4!}</math> arrangements of the colored pawns on the standard board. |
| − | 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.
| |
| | | | |
| − | | + | 10) There are <math>\frac{1}{32}[\frac{64!}{56!4!4!} + 3\frac{ 32!}{28!2!2!}+ 12\frac{16!}{14!1!1!}]= 9682216530 </math> different wallpaper patterns. |
| − | 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
| |
(b)
b) 
arrangements of the colored pawns on the standard board.
![$\frac{1}{32}[\frac{64!}{56!4!4!} + 3\frac{ 32!}{28!2!2!}+ 12\frac{16!}{14!1!1!}]= 9682216530$](http://latex.artofproblemsolving.com/3/3/f/33fd69678909703cb7f56b1be4c59c9bb85f3c6b.png)
different wallpaper patterns.
