|
|
| (3 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| − | Twenty-fourth Annual UNC Math Contest Final Round Solutions Jan 2016
| + | 1) <math>84</math> |
| − | Rules: Three hours; no electronic devices. The positive integers are 1, 2, 3, 4, . . .
| |
| − | 1. Pythagorean Triplet The sum of the lengths of the three sides of a right triangle is 56. The
| |
| − | sum of the squares of the lengths of the three sides of the same right triangle is 1250. What is
| |
| − | the area of the triangle?
| |
| − | Answer: The area is 84.
| |
| − | Solution Call the lengths of the three sides a, b, and c, with c the hypotenuse. Then a + b + c =
| |
| − | 56, a
| |
| − | 2 + b
| |
| − | 2 + c
| |
| − | 2 = 1250, and a
| |
| − | 2 + b
| |
| − | 2 = c
| |
| − | 2
| |
| − | . Conclude 2c
| |
| − | 2 = 1250, c
| |
| − | 2 = 625, and c = 25.
| |
| − | Subtract c from both sides of the equation a + b + c = 54 to conclude a + b = 56 − 25 = 31.
| |
| − | Subtract c
| |
| − | 2
| |
| − | from both sides of a
| |
| − | 2 + b
| |
| − | 2 + c
| |
| − | 2 = 1250 to conclude a
| |
| − | 2 + b
| |
| − | 2 = 1250 − 625 = 650. You
| |
| − | can solve these equations for a, b, and c, but what we are asked for is the area of the triangle,
| |
| − | and that is 1
| |
| − | 2
| |
| − | ab. We can take a small shortcut. Compute (a + b)
| |
| − | 2 = a
| |
| − | 2 + 2ab + b
| |
| − | 2
| |
| − | . Use the facts
| |
| − | that a + b = 31 and a
| |
| − | 2 + b
| |
| − | 2 = 625 to conclude 312 = 625 + 2ab. Thus, 2ab = 312 − 625 =
| |
| − | 961 − 625 = 336. The area is 1
| |
| − | 2
| |
| − | ab = 1
| |
| − | 4
| |
| − | 336 = 84.
| |
| − | 2. Fearsome Foursome Factorial Find the complete prime factorization of
| |
| − | (4!)!
| |
| − | [(3!)!]
| |
| − | 4
| |
| − | (The answer will be a product of powers of eight distinct primes.)
| |
| − | Answer: 26 × 3
| |
| − | 2 × 7
| |
| − | 3 × 112 × 13 × 17 × 19 × 23.
| |
| − | Solution One can write the expressions out carefully and cancel common factors systematically.
| |
| − | However, this can also be solved quickly using Legendre’s simple but useful formula
| |
| − | for finding the prime factorization of a factorial. The formula makes use of the greatest integer
| |
| − | function [[ ]] that rounds down to the nearest integer. As an example, the power of 2 in the
| |
| − | prime factorization of 24!, computed by Legendre’s method, is
| |
| − | [[24/2]] + [[24/22
| |
| − | ]] + [[24/23
| |
| − | ]] + [[24/24
| |
| − | ]] + . . . = 12 + 6 + 3 + 1 = 22
| |
| | | | |
| − | 3. Polyhedral Die A cube that is one inch wide has
| + | 2) <math>2^6 \cdot 3^2 \cdot 7^3\cdot 11^2 \cdot 13\cdot 17\cdot 19\cdot 23</math> |
| − | had its eight corners shaved off. The cube’s vertices
| |
| − | have been replaced by eight congruent equilateral triangles,
| |
| − | and the square faces have been replaced by six
| |
| − | congruent octagons. If the combined area of the eight
| |
| − | triangles equals the area of one of the octagons, what is
| |
| − | that area? (Each octagonal face has two different edge
| |
| − | lengths that occur in alternating order.)
| |
| − | Answer: 2
| |
| − | √
| |
| − | 3 | |
| − | 1+2
| |
| − | √
| |
| − | 3 | |
| − | =
| |
| − | 12−2
| |
| − | √
| |
| − | 3
| |
| − | 11 . | |
| − | Solution Let x be the amount that is cut off of each edge of the original square at the corners,
| |
| − | so that one side length on the resulting octahedron is 1 − 2x and the other side length is √
| |
| − | 2x.
| |
| − | Find the area of each octagon by subtracting the area of the four cut off corners from area of
| |
| − | the square. Each cut off corner is a right isosceles triangle with legs of length x. The area of
| |
| − | each of these cut off corners is 1
| |
| − | 2
| |
| − | x
| |
| − | 2
| |
| − | . Thus the area of one of the octagons is 1 − 2x
| |
| − | 2
| |
| − | . Each of the
| |
| − | new triangular faces is an equilateral triangle with side length √
| |
| − | 2x and height
| |
| − | √
| |
| − | 3
| |
| − | 2
| |
| − | √
| |
| − | 2x. The
| |
| − | area of each equilateral corner face is 1
| |
| − | 2
| |
| − | √
| |
| − | 3
| |
| − | 2
| |
| − | √
| |
| − | 2x
| |
| − | √
| |
| − | 2x = (
| |
| − | √
| |
| − | 3
| |
| − | 2
| |
| − | )x
| |
| − | 2
| |
| − | . Set eight of these equal to the
| |
| − | area of one octagon:
| |
| − | 8
| |
| − | √
| |
| − | 3
| |
| − | 2
| |
| − | x
| |
| − | 2 = 1 − 2x
| |
| − | 2
| |
| − | .
| |
| − | Solve the equation for x. Since what we are asked for is the area 1 − 2x
| |
| − | 2
| |
| − | , we might as well
| |
| − | solve for x
| |
| − | 2 | |
| − | .
| |
| | | | |
| − | 4. Number Sieve How many positive integers less than 100 are divisible by exactly two of the
| + | 3) <math>\frac{2\sqrt{3}}{1+2\sqrt{3}}=\frac{12-2\sqrt{3}}{11}</math> |
| − | numbers 2, 3, 4, 5, 6, 7, 8, 9? For example, 75 is such a number: it is divisible by 3 and by 5, but
| |
| − | is not divisible by any of the others on the list. (If you show the integers you find, then you
| |
| − | may be assigned partial credit if you have accurately found most of them, even if you do not
| |
| − | find all of them.)
| |
| − | Answer. There are eighteen such numbers:
| |
| − | 4, 9, 10, 14, 15, 21, 27, 35, 44, 50, 52, 68, 75, 76, 81, 92, 98, 99
| |
| − | Solution A reasonable way to do this one is to check each integer. Many of the integers will
| |
| − | be rejected quickly- the multiples of 4, perfect squares, and the primes, for instance.
| |
| | | | |
| − | 5. Rock and Roll. Zeus has decreed that Sisyphus must spend each day removing al the rocks
| + | 4) There are eighteen such numbers: |
| − | in a certain valley and transferring them to Mount Olympus. Each night, each rock Sisyphus
| + | <math>4, 9, 10, 14, 15, 21, 27, 35, 44, 50, 52, 68, 75, 76, 81, 92, 98, 99</math> |
| − | places on Mount Olympus is subject to the whims of Zeus: it will either be vaporized (with
| |
| − | probability 10%), be rolled back down into the valley (with probability 50% ), or be split by a
| |
| − | thunderbolt into two rocks that are both rolled down into the valley (with probability 40%).
| |
| − | When the sun rises, Sisyphus returns to work, delivering rocks to Olympus. At sunrise on
| |
| − | the first day of his punishment, there is only one rock in the valley and there are no rocks
| |
| − | on Mount Olympus. What is the probability that there are exactly two rocks in the valley at
| |
| − | sunrise on the third day? (If a rock is vaporized, it is gone.)
| |
| − | Answer: 0.332
| |
| − | Solution. A tree diagram shows that the possibilities are
| |
| − | (i) the first rock is preserved the first night and split the second night (.5)(.4) = .2;
| |
| − | (ii) the first rock is split into two the first night, and the second night both rocks are preserved
| |
| − | (.4)(.5)(.5) = .1;
| |
| − | (iii) the first rock is split into two the first night, and the second night one of those two is
| |
| − | preserved and the other is vaporized: 2(.4)(.1)(.4) = .032.
| |
| − | In total, .2 + .1 + .032 = 0.332
| |
| | | | |
| − | 6. Rock and Roll Forever? (a) Given the situation in Question 5, what is the probability that
| + | 5) <math>0.332</math> |
| − | Sisyphus must labor forever? That is, if Sisyphus begins with one rock in the valley on his
| |
| − | first morning, what is the probability that the Olympian rocks are never all vaporized?
| |
| − | (b) Suppose that the whims of Zeus obey the following rules instead: a rock will either be
| |
| − | vaporized (with probability 10%), be rolled back down into the valley (with probability 20%),
| |
| − | be split by a thunderbolt into two rocks that are both rolled down into the valley (with probability
| |
| − | 30%), or be split by two thunderbolts into three rocks that are all rolled down into the
| |
| − | valley (with probability 40%). Now what is the probability that Sisyphus must labor forever?
| |
| − | Answer: (a) 3
| |
| − | 4
| |
| − | .
| |
| − | Solution Let P be the probability that starting with one rock, the subsequent rocks are eventually
| |
| − | all vaporized. Observe that if Zeus gives you two rocks, the probability that the strings
| |
| − | of successors of both rocks disappear eventually is P
| |
| − | 2
| |
| − | , because these are independent events.
| |
| − | Now use recursiveness to compute the probability from the viewpoint of the second day. Note
| |
| − | P = .1 (1/10 of the time that first rock is gone on the second day)
| |
| − | +.5P (half the time you start over with one rock on the second day and P is the probability
| |
| − | that it and all its successors are eventually gone )
| |
| − | +.4P
| |
| − | 2
| |
| − | (4/10 of the time you get two rocks and the probability that the strings of successors
| |
| − | of both rocks disappear eventually is P
| |
| − | 2
| |
| − | ) .
| |
| − | Solve this quadratic for P. You get two solutions: P = 1 and P = .25.
| |
| − | Another approach: The polynomial p(x) = .1 + .5x + .4x
| |
| − | 2
| |
| − | encodes the whims of Zeus: the
| |
| − | coefficient of x
| |
| − | k
| |
| − | in p(x) gives the probability of there being k rocks in the valley at sunrise on
| |
| − | the second day. The coefficient of x
| |
| − | k
| |
| − | in the composite function p(p(x)) gives the probability
| |
| − | of there being k rocks in the valley at sunrise on the third day. The coefficient of x
| |
| − | k
| |
| − | in the
| |
| − | three-fold composition p(p(p(x))) gives the probability of there being k rocks in the valley at
| |
| − | sunrise on the fourth day, and so on.
| |
| − | The constant term of the polynomial is telling the probability that there are zero rocks in the
| |
| − | valley, that is, the probability that all the rocks have been vaporized.
| |
| − | Look at the (very simple) graph of y = p(x) and y = x to track down p(0) and then p(p(0))
| |
| − | and so on: use a cobweb picture to find that p(p(p(. . .(0). . .)))) is the fixed point x where
| |
| − | x = p(x). Solve to find x = 1
| |
| − | 4
| |
| − | . Conclude that the complementary event that the labor never
| |
| − | ends is 3
| |
| − | 4
| |
| − | .
| |
| − | Out[2]=
| |
| − | Figure 1: The curves cross at the fixed points x = p(x) where x = .25 and x = 1
| |
| − | (b) Answer: 15−
| |
| − | √
| |
| − | 65
| |
| − | 8
| |
| − | .
| |
| − | Solution This time you solve P = .1 + .2P + .3P
| |
| − | 2 + .4P
| |
| − | 3
| |
| − | . Observe that P = 1 is one solution,
| |
| − | so divide by the known linear factor P − 1 and solve the remaining quadratic, which is
| |
| − | 4P
| |
| − | 2 + 7P − 1 = 0. The solutions are P =
| |
| − | −7±
| |
| − | √
| |
| − | 65
| |
| − | 8
| |
| − | . Choose the positive P =
| |
| − | −7+
| |
| − | √
| |
| − | 65
| |
| − | 8
| |
| − | . The
| |
| − | complementary probability desired is 1 − P =
| |
| − | 15−
| |
| − | √
| |
| − | 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
| |
| | | | |
| | + | 6) (a) <math>\frac{3}{4}</math> (b)<math>\frac{15-\sqrt{65}}{8}</math> |
| | | | |
| | + | 7) <math>\frac{5}{4}</math> |
| | | | |
| − | 8. Tree Each circle in this tree diagram is to be assigned | + | 8) a)<math>994</math> b) <math>\frac{1}{120}n(n + 1)(n + 2)(8n^22 + 11n + 1)</math> |
| − | 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
| + | 9) There are <math>\frac{64!}{56!4!4!}</math> arrangements of the colored pawns on the standard board. |
| − | 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.
