HMMT 二月 1999 · 团队赛 · 第 5 题

Team Solutions Harvard-MIT Math Tournament February 27, 1999 Problem T1 [15] A combination lock has a 3 number combination, with each number an integer between 0 and 39 inclusive. Call the numbers n , n , and n . If you know that n and n leave the same remainder 1 2 3 1 3 when divided by 4, and n and n + 2 leave the same remainder when divided by 4, how many 2 1 possible combinations are there? Solution: There are 40 choices for the last number, and for each of these we have 10 choices for each of the first two numbers, thus giving us a total of 4000 possible combinations. It is interesting to note that these restrictions are actually true for Master locks. Problem T2 [15] A ladder is leaning against a house with its lower end 15 feet from the house. When the lower end is pulled 9 feet farther from the house, the upper end slides 13 feet down. How long is the ladder (in feet)? Solution: Of course the house makes a right angle with the ground, so we can use the Pythagorean theorem. Let x be the length of the ladder and y be the original height at which it touched the 2 2 2 2 2 house. Then we are given x = 15 + y = 24 + ( y − 13) . Isolating y in the second equation we get y = 20, thus x is 25 . Problem T3 [20] How many non-empty subsets of { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 } have exactly k elements and do not contain the element k for some k = 1 , 2 , ..., 8. Solution: Probably the easiest way to do this problem is to count how many non-empty subsets of { 1 , 2 , . . . , n } have k elements and do contain the element k for some k . The element k must have ( ) n − 1 k − 1 other elements with it to be in a subset of k elements, so there are such subsets. Now k − 1 ( ) ∑ n n − 1 n − 1 n − 1 = (1 + 1) = 2 , so that is how many non-empty sets contain some k and have k =1 k − 1 n k elements. The set { 1 , 2 , . . . , n } has 2 subsets (each element either is or is not in a particular subset), one of which is the empty set, so the number of non-empty subsets of { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 } n n − 1 n − 1 have exactly k elements and do not contain the element k for some k is 2 − 2 − 1 = 2 − 1. In the case n = 8, this yields 127 . Problem T4 [20] Consider the equation F ORT Y + T EN + T EN = SIXT Y , where each of the ten letters represents a distinct digit from 0 to 9. Find all possible values of SIXT Y . 1

Solution: Since Y + N + N ends in Y , N must be 0 or 5. But if N = 5 then T + E + E + 1 ends in T, which is impossible, so N = 0 and E = 5. Since F 6 = S we must have O = 9, R + T + T + 1 > 10, and S = F + 1. Now I 6 = 0, so it must be that I = 1 and R + T + T + 1 > 20. Thus R and T are 6 and 7, 6 and 8, or 7 and 8 in some order. But X can’t be 0 or 1 since those are taken, and X cannot be 3 since F and S have to be consecutive, so it must be that R + T + T + 1 is 21 or 23. This is satisfied only for R = 7 , T = 8, so F = 2 , S = 3, and Y = 6. This SIXT Y = 31486 . Problem T5 [30] If a and b are randomly selected real numbers between 0 and 1, find the probability that the nearest a − b integer to is odd. a + b Solution: The only reasonable way I know of to do this problem is geometrically (yes, you can use integrals to find the areas of the triangles involved, but I don’t consider that reasonable). First let a − b 1 a − b 1 us find the points ( a, b ) in the plane for which the nearest integer to is 0, i.e. − ≤ ≤ . a + b 2 a + b 2 1 a − b Taking the inequalities one at a time, − ≤ implies that a + b ≥ 2( b − a ), or b ≤ 3 a , so these 2 a + b a − b 1 points must lie below the line y = 3 x . Similarly, ≤ implies that ( a, b ) must lie above the a + b 2 1 a − b line y = x . Now we can look for the points ( a, b ) for which the nearest integer to is 1, i.e. 3 a + b 1 a − b 3 ≤ ≤ , and we find that all points in the first quadrant that lie above the line y = 3 x satisfy 2 a + b 2 a − b this inequality. Similarly, the closest integer to is -1 for all points in the first quadrant below a + b 1 the line y = x . For a and b between 0 and 1, the locus of points ( a, b ) for which the nearest integer 3 a − b 1 1 to is odd is two right triangles with legs of length 1 and , so together they have area . The a + b 3 3 locus of all points ( a, b ) with a and b between 0 and 1 is a square of side length 1, and thus has a − b 1 area 1. Therefore the probability that the nearest integer to is odd is . a + b 3 Problem T6 [30] √ √ √ √ 3 3 Reduce the number 2 + 5 + 2 − 5. √ √ √ √ √ √ √ √ √ √ 3 3 3 3 3 Solution: Observe that ( 2 + 5+ 2 − 5) = (2+ 5) − 3( 2 + 5) − 3( 2 − 5)+(2 − 5) = √ √ √ √ √ √ √ √ 3 3 3 3 3 4 − 3( 2 + 5 + 2 − 5). Hence 2 + 5 + 2 − 5 is a root of the cubic x + 3 x − 4 = √ √ √ √ 3 3 2 2 ( x − 1)( x + x + 4). The roots of x + x + 4 are imaginary, so 2 + 5 + 2 − 5 = 1 . Problem T7 [30] ∑ 1 ∞ n 2 Let = a x , for what positive integers n does a = n ? 2 3 n n − 1 i =0 1 − x − x − x 2 3 Solution: Multiplying both sides by 1 − x − x − x the right hand side becomes a +( a − a ) x +( a − 0 1 0 2 2 n a − a ) x + . . . , and setting coefficients of x equal to each other we find that a = 1 , a = 1 , a = 2, 1 0 0 1 2 and a = a + a + a for n ≥ 3. Thus the sequence of a ’s starts 1, 1, 2, 4, 7, 13, 24, 44, 81, n n − 1 n − 2 n − 3 n 2 2 149, . . . . So we now see that a = 1 and a = 9 . What makes it impossible for this to happen again 0 8 n is that the sequence is growing exponentially. It will suffice to show that a > 1 . 5 for n > 2, since n 2 2 2 n / ( n − 1) < 1 . 5 for n ≥ 6, thus when a exceeds n at n = 10 there can be no more solutions n − 1 2 to a = n . Observe that a > 1 . 5 a for n = 3 , 4 , 5. By way of induction, assume it for n − 2, n − 1 n n − 1 2

n n − 1 n − 2 n − 2 2 n +1 n − 1, and n , then a = a + a + a > 1 . 5 +1 . 5 +1 . 5 = 1 . 5 (1+1 . 5+1 . 5 ) > 1 . 5 . n +1 n n − 1 n − 2 n Thus, by induction, a > 1 . 5 for n > 2, so the only solutions are 1, 9 . n Problem T8 [35] 2 2 2 Find all the roots of ( x + 3 x + 2)( x − 7 x + 12)( x − 2 x − 1) + 24 = 0. 2 2 2 Solution: We re-factor as ( x + 1)( x − 3)( x + 2)( x − 4)( x − 2 x − 1) + 24, or ( x − 2 x − 3)( x − 2 2 2 x − 8)( x − 2 x − 1) + 24, and this becomes ( y − 4)( y − 9)( y − 2) + 24 where y = ( x − 1) . Now, ( y − 4)( y − 9)( y − 2) + 24 = ( y − 8)( y − 6)( y − 1), so y is 1, 6, or 8. Thus the roots of the original √ √ polynomial are 0 , 2 , 1 ± 6 , 1 ± 2 2 . Problem T9 [40] ∑ 2 17 n + n +1 Evaluate . 4 3 2 n =2 n +2 n − n − 2 n 4 3 2 Solution: Observe that the denominator n + 2 n − n − 2 n = n ( n − 1)( n + 1)( n + 2). Thus we can 2 n − n +1 a b c d rewrite the fraction as = + + + for some real numbers a , b , c , and d . This 4 3 2 n − 1 n n +1 n +2 n +2 n − n − 2 n 4 3 2 method is called partial fractions . Condensing the right hand side as a fraction over n +2 n − n − 2 n 2 3 2 3 2 3 2 3 we get n − n + 1 = a ( n + 3 n + 2 n ) + b ( n + 2 n − n − 2) + c ( n + n − 2 n ) + d ( n − n ). Comparing coefficients of each power of n we get a + b + c + d = 0, 3 a +2 b + c = 2, 2 a − b − 2 c − d = 2, and − 2 b = 2. This is a system of 4 equations in 4 variables, and its solution is a = 1 / 2 , b = − 1 / 2 , c = 1 / 2, and d = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 − 1 / 2. Thus the summation becomes (1 − + − + − + − + − + − + · · · + − + − ). 2 2 3 4 2 3 4 5 3 4 5 6 16 17 18 19 1 1 1 1 592 Notice that almost everything cancels to leave us with (1 + − − ) = . 2 3 17 19 969 Problem T10 [45] If 5 points are placed in the plane at lattice points (i.e. points ( x, y ) where x and y are both integers) such that no three are collinear, then there are 10 triangles whose vertices are among these points. What is the minimum possible number of these triangles that have area greater than 1/2? Solution: By the pigeonhole principle, the 5 points cannot all be distinct modulo 2, so two of them must have a midpoint that is also a lattice point. This midpoint is not one of the 5 since no 3 are collinear. Pick’s theorem states that the area of a polygon whose vertices are lattice points is B/ 2 + I − 1 where B is the number of lattice points on the boundary and I is the number in the interior. Thus those two points form the base of 3 triangles whose area will be greater than 1/2 by Pick’s theorem since there are 4 lattice points on the boundary. Now it also turns out that at least one of the triangles must contain a lattice point, thus giving us a fourth triangle with area greater than 1/2. This is actually pretty easy to show with the aid of a picture or some visualization. Suppose we have 4 points and we’re trying to find a 5th one so that no triangle will contain an interior lattice point. The 4 lattice points must form a quadrilateral of area 1, so in fact it is a parallelogram (think deeply about it). Draw the four sides, extending them throughout the plain. Each vertex is now the tip of an infinite triangular region of the plane, and if the 5th lattice point is chosen in that region then the triangle formed by the 5th point and the two vertices of the parallelogram adjacent to the one we are considering will form a triangle containing the vertex we 3

are considering. But the part of the plane that isn’t in one of these 4 regions contains no lattice points or else we could draw a parallelogram congruent to the first one with lattice point vertices and containing that lattice point, but that would violate Pick’s theorem since the parallelogram has area 1. Therefore we must have a fourth triangle with area greater than 1/2 (one must justify that this really is in addition to the 3 triangles we already knew we’d get). An example that achieves this minimum is the points (0,0), (1,0), (1,1), (2,1), and (2,-1). Therefore the minumum possible number of these triangles that have area greater than 1/2 is 4 . A less trivial example that achieves the minimum is (0,0), (1,1), (2,1), (3,2), and (7,5). Problem T11 [55] Circles C , C , C have radius 1 and centers O, P, Q respectively. C and C intersect at A , C and 1 2 3 1 2 2 ◦ ◦ 6 6 C intersect at B , C and C intersect at C , in such a way that AP B = 60 , BQC = 36 , and 3 3 1 ◦ 6 COA = 72 . Find angle ABC (degrees). Solution: Using a little trig, we have BC = 2 sin 18, AC = 2 sin 36, and AB = 2 sin 30 (see left 2 2 2 diagram). Call these a , b , and c , respectively. By the law of cosines, b = a + c − 2 ac cos ABC , 2 2 2 sin 18+sin 30 − sin 36 therefore cos ABC = . In the right diagram below we let x = 2 sin 18 and see 2 sin 18 sin 30 √ − 1+ 5 2 that x + x = 1, hence sin 18 = . Using whatever trig identities you prefer you can find that 4 √ 2 5 − 5 1 2 2 2 sin 36 = , and of course sin 30 = . Now simplification yields sin 18 + sin 30 − sin 36 = 0, 4 2 ◦ 6 so ABC = 90 . Note that this means that if a regular pentagon, hexagon, and decagon are inscribed in a circle, then we can take one side from each and form a right triangle. 36 x 1 x 72 2 x 36 72 36 1 x Problem T12 [65] A fair coin is flipped every second and the results are recorded with 1 meaning heads and 0 meaning tails. What is the probability that the sequence 10101 occurs before the first occurance of the sequence 010101? Solution: Call it a win if we reach 10101, a loss if we reach 010101. Let x be the probability of winning if the first flip is a 1, let y be the probability of winning if the first flip is a 0. Then the probability of winning is ( x + y ) / 2 since the first flip is 1 or 0, each with probability 1/2. If we ever get two 1’s in a row, that is the same as starting with a 1 as far as the probability is concerned. Similarly, if we get two 0’s in a row, then we might as well have started with a single 0. start 1 0 11 10... 01 00... 101 100... 011...010 1010 1011... 0101 0100... 10101 10100... 01011... 01010 010101 010100... 4

From the tree of all possible sequences, shown above, in which the probability of moving along any particular line is 1/2, we see that x = x (1 / 2 + 1 / 8) + y (1 / 4 + 1 / 16) + 1 / 16, and y = x (1 / 4 + 1 / 16) + y (1 / 2 + 1 / 8 + 1 / 32). Solving these two equations in two unknowns we get x = 11 / 16 and y = 5 / 8. Therefore the probablity that the sequence 10101 occurs before the first occurance of the sequence 010101 is 21/32 . 5