2010b数学竞赛Mandelbrot Competition 2008 team problems and solutions

Team Play Solutions Part i: There are many lines with slope 1 that thread the lattice; for example, any line of the form y = x+b having a y-intercept in the range 1 ≤ b ≤ 3 will do, such as y = x+√2. (We omit the sketch of the line and the nearby lattice squares.) Note that there are plenty of such lines that cleanly thread the lattice. Next we consider slope − 12 lines. In this case any line of the form y = − 12x + b with 4 ≤ b ≤ 5 works; all except the b = 4 and b = 5 intercepts cleanly thread. (There are other answers as well.) For slope 23 , however, we must choose the y-intercept carefully. Two possible answers are y = 23x + 1 and y = 2 3x + 4 1 3 . Every possible answer only barely threads the lattice, though. Finally, any line of the form y = 3x+ b with 1 ≤ b ≤ 2 will thread the lattice; all except b = 1 and b = 2 cleanly thread. (Again, other answers are possible.) Part ii: Suppose that we have drawn a line in the plane with slope m that cleanly threads the lattice. Consider a reflection of the entire plane over the horizontal line y = 3. It straight-forward to verify that the lattice squares wind up in exactly the same positions as before, while the reflected line has slope −m. Clearly the new line still cleanly threads the lattice, so we’re done. The same type of argument can be used to show that there is also a line with slope 1m that cleanly threads the lattice by reflecting the diagram over the line y = x. Finally, if we perform both of these reflections (in either order), we obtain a line with slope − 1m that cleanly threads the lattice. Part iii: The lower endpoint of the shadow is found by determining the equation of the line through the lower right corner of the (5, 5)-square, which has coordinates (6, 5). This equation is y = 34x + 1 2 . Since the y-intercept is 12 , the shadow cast on the y-axis must begin at y = 1 2 . In the same way we find that the line throught the upper left corner (5, 6) is y = 34x+2 1 4 , so the upper endpoint of the shadow on the y-axis is 2 1 4 . Hence, the length of the shadow is 2 14 − 12 = 1 34 . Part iv: Since the (5, 5)-square’s shadow overlaps with that of the (0, 0)- square, it stands to reason that the (10, 10)-squares’s shadow will overlap with that of the (5, 5)-square. Indeed, the lines with slope 34 that just touch the (10, 10)-square on either side are y = 34x+1 3 4 and y = 3 4x+4. Thus its shadow on the y-axis is the segment from y = 1 34 to y = 4, which is higher than the shadow of the (5, 5)-square but overlaps it. Consider the shadows of the squares along the main diagonal, which include the (−5,−5), (0, 0), (5, 5), (10, 10)-squares, and so on. We claim that they form an interlocking set of shadows which cover the entire y-axis. We have already seen that each such shadow has length 1 34 . Furthermore, as we step from one square to the next along the diagonal, the shadow is raised by the same amount at each step. But we have already seen the lower endpoint of the shadow moved up from y = 12 to y = 1 34 in going from the (5, 5)-square to the (10, 10)-square, a shift of only 1 14 . Hence all these shadows overlap, as claimed. We are now able to conclude that no line with slope 34 is able to thread the lattice. For any such line must intersect the y-axis at a point which is in the interior of some shadow. This shadow is cast by some square via a slope 34 line; hence our line must have passed through the interior of this square, which means that it does not thread the lattice. Part v: To begin, it is easy to confirm that the shadow cast by the (0, 0)-square stretches from y = −pq to y = 1. (Check this.) Now let the (5c, 5d)-square be an arbitrary square in the lattice. If this square is to cast a shadow which overlaps with that of the (0, 0)-square, then the line with slope m = pq and passing through (5c+ 1, 5d) (the lower right corner of the square) must have a y-intercept b satisfying −pq < b < 1. We can determine the y-intercept by writing y = mx+ b =⇒ 5d = p q (5c+ 1) + b =⇒ b = 5d− p q (5c+ 1). Hence we wish to find integers c and d such that −p q < 5d− p q (5c+ 1) < 1 =⇒ 0 < dq − cp < p+ q 5 . But p and q are relatively prime positive integers (we can safely assume that the fraction pq is written in lowest terms), hence there is a multiple of q which is exactly 1 greater than a multiple of p. (This is a standard fact from elementary number theory; you should test it out if you are unfamiliar with it.) Let dq and cp be these multiples, so that dq−cp = 1. Since p+ q > 5, we have found a solution to the above inequality. Part vi: Our argument will closely mimic part iv. Let c and d be the integers found in the previous part. The idea is that whenever we step from a square in the lattice to the square 5c units away in the x-direction and 5d units away in the y-direction, we reach a new square whose shadow is slightly higher than but overlaps with the previous shadow. The whole sequence of squares obtained in this manner will provide a set of interlocking shadows which completely cover the y-axis. Hence no line with slope pq can thread the lattice, using the same logic as above. Finally, it turns out that whenever p+q = 5 there is a line with slope m = pq that threads the lattice, but only barely. And slopes for which p + q < 5 permit lines that cleanly thread the lattice, as the first part suggests. In case you were wondering, a line with an irrational slope can never thread the lattice. (Can you prove this?) Of course, there is a natural extension to lattices in which every kth square is shaded, instead of every fifth square. The same sorts of results hold in this more general setting, a fact which the reader is invited to confirm. c© Greater Testing Concepts 2008 January 2009 Round One Solutions Greater Testing Concepts The Mandelbrot Team Play PO Box 760 web.mandelbrot.org Potsdam, NY 13676 info@mandelbrot.org Team Play Solutions Part i: Substituting in b = 0 we obtain FaF0 + Fa+1F1 = Fa+1. Since F0 = 0 and F1 = 1, this reduces to just Fa+1 = Fa+1, which is obviously true. Next, substituting b = 1 gives FaF1 + Fa+1F2 = Fa+2. Since F2 = 1 also, this time the relationship reduces to Fa + Fa+1 = Fa+2, which is again clearly true by definition of the Fibonacci sequence. When a = 5 and b = 7 we must confirm that F5F7+F6F8 = F13. We first compute F5 = 5, F6 = 8, F7 = 13 and F8 = 21. Hence the left-hand side becomes (5)(13) + (8)(21) = 65+ 168 = 233. But F13 = 233, so the relationship holds in this case as well. Part ii: We have seen that the relationship FaFb +Fa+1Fb+1 = Fa+b+1 holds for b = 0 and b = 1. To prove that it holds in general, we assume that it is true for all values of b from b = 0 up to b = k, for some fixed number k. We will then argue that it is also true for b = k + 1, from which the result will follow by induction. Since the statement is true for b = k − 1 and b = k, we know that FaFk−1 + Fa+1Fk = Fa+k and FaFk + Fa+1Fk+1 = Fa+k+1 holds for all a ≥ 0. Adding these two equalities yields Fa(Fk−1 + Fk) + Fa+1(Fk + Fk+1) = Fa+k + Fa+k+1, which simplifies to FaFk+1 + Fa+1Fk+2 = Fa+k+2. But this is exactly the case b = k + 1 which we wished to prove, so we are done. Part iii: Replacing b by a−1 in the identity FaFb+Fa+1Fb+1 = Fa+b+1 we find that FaFa−1+Fa+1Fa = F2a. Factoring out an Fa on the left, we have Fa(Fa−1+Fa+1) = F2a. Since the product of Fa and another integer (namely Fa−1+Fa+1) gives F2a, we conclude that F2a is a multiple of Fa. We can use the same technique again by choosing b = 2a−1 instead. This time we obtain FaF2a−1+Fa+1F2a = F3a. We cannot immediately factor out an Fa as before, but we already know that F2a is a multiple of Fa, hence the entire left-hand side must be also. More precisely, we could substitute our expression for F2a from above, ultimately yielding Fa(F2a−1 + Fa−1Fa+1 + F 2a+1) = F3a, making it clear that F3a is also a multiple of Fa. Part iv: The first eight rows of the Fibonomial triangle look like 1 1 1 1 1 1 1 2 2 1 1 3 6 3 1 1 5 15 15 5 1 1 8 40 60 40 8 1 1 13 104 260 260 104 13 1 Part v: The identity (( n+1 k+1 )) = Fn−k+1 (( n k )) + Fk (( n k+1 )) is one of many marvelous relationships among the Fibonacci numbers. To prove it, we use the formula defining (( n k )) , then find a common denominator. To save space, we have already cancelled all the factors from Fn−k down to F1 in the expression for (( n k )) . We find that Fn−k+1 (( n k )) + Fk (( n k + 1 )) = Fn−k+1 Fn · · ·Fn−k+1 Fk · · ·F1 + Fk Fn · · ·Fn−k Fk+1 · · ·F1 = Fk+1Fn−k+1 Fn · · ·Fn−k+1 Fk+1 · · ·F1 + FkFn−k Fn · · ·Fn−k+1 Fk+1 · · ·F1 = (Fk+1Fn−k+1 + FkFn−k) Fn · · ·Fn−k+1 Fk+1 · · ·F1 = (Fn+1) Fn · · ·Fn−k+1 Fk+1 · · ·F1 = (( n+ 1 k + 1 )) . In the fourth line we used the identity FaFb + Fa+1Fb+1 = Fa+b+1 with a = k and b = n − k. These steps are valid as long as n > k (so that(( n k+1 )) is defined) and k > 0 (so that we can write Fk · · ·F1). When k = 0 the identity reduces to just Fn+1 = Fn+1, which is obviously true. Assuming that all the entries in one row of the Fibonomial triangle are integers, we can now deduce that all the entries in the next row are also. The above identity ensures that (( n+1 k+1 )) is an integer, except that it doesn’t apply to (( n+1 0 )) , (( n+1 1 )) or (( n+1 n+1 )) since we must have n > k > 0. But it is routine to check that these Fibonomials have values 1, Fn+1 and 1, which are still integers. Part vi: The following statements are all equivalent to the original one: F 2n+1 − F 2n−1 = 2F 2n + F 2n−1 − F 2n−2 (Fn+1 − Fn−1)(Fn+1 + Fn−1) = 2F 2n + (Fn−1 − Fn−2)(Fn−1 + Fn−2) (Fn)(Fn+1 + Fn−1) = 2F 2n + (Fn−1 − Fn−2)(Fn) Fn+1 + Fn−1 = 2Fn + Fn−1 − Fn−2 Now cancelling the Fn−1 term and using Fn − Fn−2 = Fn−1, we arrive at Fn+1 = Fn + Fn−1, which is clearly true. It appears that the coefficients in these remarkable identities are Fibonomial numbers! Following the same pattern, we conjecture that F 4n+1 = 5F 4 n + 15F 4 n−1 − 15F 4n−2 − 5F 4n−3 ± F 4n−4, where it is not clear yet whether we should use a ‘+’ or a ‘−’ for the final term. Testing our conjecture for n = 5 yields 84 = 5(54) + 15(34)− 15(24)− 5(14)± (14) = 3125 + 1215− 240− 5± 1 = 4095± 1. Since 84 = 212 = 4096, it is now clear that we should use the ‘+’ sign. In general, it turns out that the plus and minus signs alternate in pairs. Thanks to Ron Knott for assembling an informative web page from which some of the material on this test was drawn. The interested reader should Google “Knott fibonomial” to visit his page. c© Greater Testing Concepts 2009 February 2009 Round Two Solutions Greater Testing Concepts The Mandelbrot Team Play PO Box 760 web.mandelbrot.org Potsdam, NY 13676 info@mandelbrot.org Team Play Solutions Part i: Proving that 4ISU ∼= 4IWU is fairly routine—we are given that US ∼= UW , we know that IS ∼= IW since each segment is a radius of the incircle, and clearly IU ∼= IU . So 4ISU ∼= 4IWU by SSS. But it is also possible to prove that 4ISU ∼= 4IWU without using the fact that US ∼= UW . Just argue that IS ∼= IW and IU ∼= IU as before, observe that 6 IWU and 6 ISU are right angles becauseW and S are points of tangency, then use HL (hypotenuse-leg) congruence. (This is how it is possible to deduce that US ∼= UW in the first place.) Regardless, we next show that m6 WIS = m6 B. Since the sum of the angles of quadrilateral IWUS is 360◦ and 6 IWU and 6 ISU are right angles, it follows that m6 WIS + m6 WUS = 180◦. But we also have m6 AUV +m6 WUS = 180◦, so we deduce that m6 WIS = m 6 AUV . Lastly, m6 AUV = m6 ABC = m6 B, by the given. Dividing the above result by two gives 12m6 WIS = 1 2m 6 B. Since m6 WIU = m 6 SIU and together these two angles make up 6 WIS, we conclude that each is equal to 12m 6 WIS. Hence m6 SIU = 1 2m 6 B. Part ii: It is common knowledge that the three angle bisectors of a tri- angle each pass through the center I of the inscribed circle. Therefore we know that m 6 RBI = 12m6 B, just as m6 SIU = 1 2m 6 B. (If desired, one could prove that4RBI ∼= 4TBI using HL congruence, but it is OK to omit this step.) Furthermore, m 6 BRI = m6 ISU = 90◦. Therefore 4BRI ∼ 4ISU by AA similarity. Comparing ratios in these similar triangles yields SU/IS = RI/BR. But IS = IR = r and BR = sb by the givens. Therefore multiplying through by IS yields SU = r2/sb, as desired. Part iii: In an analogous fashion one may show that 4ITV ∼ 4CRI, which leads to TV = r2/sc upon comparing equal ratios. (We omit the details.) Next note that UV = UW +WV = SU + TV . Thus UV = r2 sb + r2 sc = r2 ( sb + sc sbsc ) = r2 ( a rra ) = ar ra , where we used the fact that sb+ sc = 2s− b− c = (a+ b+ c)− b− c = a and also that sbsc = rra, as mentioned in the Facts section. Part iv: It is possible to prove the given equality solely by algebraic means, utilizing some of the relationships listed in the Facts section. It is quite satisfying to watch this identity resolve itself, if you enjoy that sort of thing. We leave the demonstration to the interested reader, and instead follow the advice to try a geometric approach. Based on our previous work, we recognize the quantities appearing in the given expression. Thus sa − (r2/sc) = AT − TV = AV , and in the same way sa − (r2/sb) = AS − SU = AU . Of course b = AC and c = AB, so proving the given equality is tantamount to proving that AC/AB = AV/AU . And clearly this would follow at once if we could show that 4ABC ∼ 4AUV . But this is straight-forward; we are given that 6 AUV ∼= 6 ABC and both triangles share 6 A. Hence the triangles are similar by AA, and you’re done. Part v: To prove this unexpected area equality we will first find an expression for area(BCUV ). To begin, since4ABC ∼ 4AUV we know that the ratio of their areas is equal to the square of the ratios of their sides. Thus area(AUV ) area(ABC) = ( UV BC )2 = ( ar/ra a )2 = r2 r2a . Letting K = area(ABC), we have area(AUV ) = Kr2/r2a, which means that area(BCUV ) = area(ABC)− area(AUV ) = K −Kr2/r2a. Hence area(BCUV ) = K ( 1− r 2 r2a ) = rasa ( 1 + r ra )( 1− r ra ) . Multiplying ra(1 + r/ra) gives (r+ ra), which is one part of the desired expression. It remains to show that sa(1 − r/ra) = UV = ar/ra. This is equivalent to sa(ra− r) = ar, upon multiplying through by ra. Using the fact rasa = rs we find that sa(ra − r) = rasa − sar = rs− (s− a)r = ar, which completes the argument. Part vi: This formula is reminiscent of Hero’s formulaK = √ ssasbsc for a triangle. Except here we have a quadrilateral, and we are multiplying sides lengths instead of quantities like sa. Nonetheless, the formula is correct, as we shall show. First note that BV = BT + TV = sb + r2/sc = (sbsc + r2)/sc. In the same manner we find that CU = (sbsc + r2)/sb. Therefore we have √ (BC)(BV )(CU)(UV ) = √ a ( sbsc + r2 sc )( sbsc + r2 sb )( ra ra ) = a(sbsc + r2) √ r (sbsc)ra = a(rra + r2) √ r (rra)ra = ( ra ra ) (ra + r) = (UV )(ra + r) = area(BCUV ), according to the result of the previous part. Well-read students may be familiar with a delightful area formula for quadrilaterals which possess both an incircle and a circumcircle (neither condition occurs in general). It states that if the quadrilateral has sides of length a, b, c and d then its area is given by √ abcd. This provides an alternate means of proving the given statement, as long as one explains why this formula works, and also verifies that BCUV has a circumcircle. c© Greater Testing Concepts 2009 March 2009 Round Three Solutions Greater Testing Concepts The Mandelbrot Team Play PO Box 760 web.mandelbrot.org Potsdam, NY 13676 info@mandelbrot.org January 2009 Round One Test Time Limit: 60 minutes� � � � Setup: consider an infinite sheet of graph paper in which every fifth square is filled in. More precisely, plot every point (x, y) in the Cartesian plane with 5c ≤ x ≤ 5c + 1 and 5d ≤ y ≤ 5d+1 for integers c and d, meaning that the x and y coordinates are each at most one more than a multiple of five. We call this collection of squares a lattice, and refer to a given square by the coordinates of its lower left corner. A portion of the lattice is shown below, including the (0, 0)-square, the (5, 0)-square, the (0, 5)-square and the (5, 5)-square. Now let y = mx + b be the equation of a line. We say that this line cleanly threads the lattice if it does not intersect any of the squares in the lattice at all. Next, we say that the line barely threads the lattice if the line contains the vertices of some of the squares, but does not pass through their interiors. Finally, if a line crosses into the interior of any square then it does not thread the lattice. These three situations are illustrated by the top, middle, and bottom lines in the diagram.� � � � Problems Part i: (4 points) Find a line with slope 1 that threads the lattice. Give the equation of such a line and sketch it in the plane along with at least four nearby lattice squares. Now do the same for lines having slopes −1 2 , 2 3 and 3. Which line only barely threads the lattice? Part ii: (5 points) Show that if there is a line with slope m that cleanly threads the lattice, then there are lines with slope −m, 1 m and − 1 m that also cleanly thread the lattice. (You do not need to work with equations of lines here; a geometric argument is sufficient.) Part iii: (4 points) Suppose that light rays with slope 3 4 shine from the right. Describe the shadow cast onto the y-axis by the (5, 5)-square. (Give its endpoints and length.) Part iv: (5 points) Continuing the previous part, demonstrate that there is another square in the lattice whose shadow is slightly higher than but overlaps with that of the (5, 5)-square. Extend these ideas to prove that a slope 3 4 line cannot thread the lattice. Part v: (5 points) In general, let m = p q be a slope which is a positive rational number, and consider light rays with slope m. Prove that if p + q > 5 then there exists a square in the lattice whose shadow on the y-axis overlaps with the shadow cast by the (0, 0)-square. Part vi: (5 points) Let m = p q be a positive fraction with p+ q > 5 as before. Prove that a slope m line cannot thread the lattice. Finally, conjecture what happens if p+ q = 5. c© Greater Testing Concepts 2008 February 2009 Round Two Test Time Limit: 60 minutes� � � � Facts: The Fibonacci numbers are the sequence of integers 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . in which each number is the sum of the two previous numbers. The kth Fibonacci number is written Fk, so this sequence satisfies F0 = 0, F1 = 1, and Fk+1 = Fk + Fk−1 for k ≥ 1.� � � � Setup: We will write “k Fibonacci-factorial,” denoted as FF (k), to represent the product of the k Fibonacci numbers from Fk down to F1. Thus FF (5) = 5 · 3 · 2 · 1 · 1 = 30. We also declare that FF (0) = 1. We can now define (( n k )) , called a Fibonomial, as(( n k )) = FF (n) FF (k) · FF (n− k) . Thus (( 5 3 )) = FF (5) FF (3)·FF (2) = 30 2·1 = 15. One can also confirm that (( 7 6 )) = 13 and that (( 0 0 )) = 1. � � � � Problems Part i: (4 points) One of the more delightful relationships among the Fibonacci numbers states that FaFb + Fa+1Fb+1 = Fa+b+1. To begin, explain why this statement is true when b = 0 or b = 1. Also confirm the equality when a = 5 and b = 7. Part ii: (5 points) Now prove that FaFb + Fa+1Fb+1 = Fa+b+1 holds for all a ≥ 0 and all b ≥ 0 by using induction on b. (The previous part demonstrates the base cases.) Part iii: (5 points) By choosing a strategic value for b in the above relationship, show that for a ≥ 1, F2a is a multiple of Fa. Based on this, next show that F3a is also a multiple of Fa. Part iv: (4 points) There is a “Fibonomial triangle” whose nth row consists of the numbers(( n 0 )) , (( n 1 )) , up to (( n n )) . Compute rows n = 0 through n = 7, listing them on top of one another in a triangular arr