HMMT 二月 1999 · ORAL 赛 · 第 6 题

Oral Solutions Harvard-MIT Math Tournament February 27, 1999 Problem O1 [25 points] ◦ ◦ ◦ Start with an angle of 60 and bisect it, then bisect the lower 30 angle, then the upper 15 angle, and so on, always alternating between the upper and lower of the previous two angles constructed. ◦ This process approaches a limiting line that divides the original 60 angle into two angles. Find the measure (degrees) of the smaller angle. 1 1 1 Solution: The fraction of the original angle is − + − + · · · . This is just a geometric series with 2 4 8 ◦ first term 1/2 and ratio -1/2, so the sum is 1/3. Therefore the smaller angle is 20 . Score 20 points for the correct answer, 5 points for a correct justification. Just setting up the sum is worth 6 points, getting 1/3 is worth 9 more. Problem O2 [25 points] Alex, Pei-Hsin, and Edward got together before the contest to send a mailing to all the invited schools. Pei-Hsin usually just stuffs the envelopes, but if Alex leaves the room she has to lick them as well and has a 25% chance of dying from an allergic reaction before he gets back. Licking the glue makes Edward a bit psychotic, so if Alex leaves the room there is a 20% chance that Edward will kill Pei-Hsin before she can start licking envelopes. Alex leaves the room and comes back to find Pei-Hsin dead. What is the probability that Edward was responsible? Solution: There are two possibilities: either Edward killed Pei-Hsin or the envelopes did. The envelope could only be responsible if Edward was not, so the chances of that would be 4 / 5 · 1 / 4 = 1 / 5. This is the same as the probability that Edward killed her, so the events are equally likely and the answer is 50% , or 1/2 . Score 20 points for the correct answer, 5 points for a correct justification. Not many places to give partial credit. Problem O3 [30 points] 2 2 3 If x , y , and z are distinct positive integers such that x + y = z , what is the smallest possible value of x + y + z . 3 Solution 1: Without loss of generality let x > y . We must have z expressible as the sum of two squares, and this first happens when z = 5. Then x and y can be 10 and 5 or 11 and 2. If z > 5 3 2 then z ≥ 10 for z to be a sum of two distinct squares, so x > 500, x > 22, so x + y + z > 32. Thus the smallest possible value of x + y + z is 11 + 2 + 5 = 18 . 3 2 2 Solution 2: If z > 5, then z ≥ 6, so z ≥ 216. Now x + y ≥ 216, so x ≥ 11 and y ≥ 1, thus x + y + z ≥ 18. Since x = 11 , y = 1 , z = 6 does not work, we must have x + y + z > 18, and the solution given is the best possible. 1

Score 20 points for the correct answer, 5 points for justifying that we can’t do better with z ≤ 5, 5 points for justifying that we can’t do better with z > 5. Problem O4 [35 points] ∑ ∞ cos nθ 1 Evaluate , where cos θ = . n n =0 2 5 ∑ inθ ∞ e inθ Solution: cos nθ is the real part of e , so the sum is the real part of . This is a geometric n n =0 2 √ iθ e 1 1 2 6 series with initial term 1 and ratio , so its sum is . We are given cos θ = , so sin θ = ± . iθ 2 5 5 1 − e / 2 √ 10 90 ± 20 i 6 6 √ Thus the sum is = , and the real part is . 105 7 10 − 1 ∓ 2 i 6 Score 20 points for the correct answer, 15 points for a correct justification. Problem O5 [45 points] Let r be the radius of the inscribed circle of triangle ABC . Take a point D on side BC , and let r 1 and r be the inradii of triangles ABD and ACD . Prove that r , r , and r can always be the side 2 1 2 lengths of a triangle. Solution: We must show that r , r , and r satisfy the triangle inequality, i.e. that the sum of any 1 2 two of them exceeds the third. Clearly r is the largest of the three, so we need only verify that r + r > r . Let K and s be the area and semiperimeter of triangle ABC . Similarly define K , 1 2 1 K , s , and s . Observe that s is larger than s or s and that K + K = K . While these facts 2 1 2 1 2 1 2 are almost trivial to verify, they must be stated. Then r = K/s , r = K /s , and r = K /s , so 1 1 1 2 2 2 r + r = K /s + K /s > K /s + K /s = K/s = r . 1 2 1 1 2 2 1 2 The correct use of areas and semiperimeters is worth 25 points, each of the critical facts is worth 10 points. I don’t know of any other way to do this problem, so attempts at alternate proofs should get at most 15 points for effort unless they really on the right track to another solution. Problem O6 [45 points] You want to sort the numbers 5 4 3 2 1 using block moves. In other words, you can take any set of numbers that appear consecutively and put them back in at any spot as a block. For example, 6 5 3 4 2 1 → 4 2 6 5 3 1 is a valid block move for 6 numbers. What is the minimum number of block moves necessary to get 1 2 3 4 5? Solution 1: Here is a sequence of 3 moves that works: 54321 → 32541 → 34125 → 12345. But how do we know we can’t do it in 2 moves? From any position there are 20 possible permutations via block moves, 16 from moving a block of size 1 and 4 from moving a block of size 2. One could simply write the 20 permutations of 54321 and the 20 permutations of 12345 and try to see that they have nothing in common, which would suffice since the inverse of a block move is also a block move. A more clever method is to notice that if we could sort 54321 in 2 moves then we could sort 4321 in 2 moves as well by simply deleting the 5 from each step. But 4321 has only 10 permutations from block moves, namely 3421, 3241, 3214, 4231, 4213, 2431, 4312, 1432, 4132, and 2143. The 10 2

permutations of 1234 are 2134, 2314, 2341, 1324, 1342, 3124, 1243, 4123, 1423, and 3412. These two sets of permutations have nothing in common, thus it takes at least 3 moves to sort 4321, and hence at least 3 moves to sort 54321. Solution 2: There is a more elegant way to show we need at least 3 moves. Given a permutation of { 1 , 2 , 3 , 4 , 5 } (or any ordered set), define a descent to be an adjacent pair of numbers in the permutation such that the left number is greater than the right one. For example, 12345, 34215, and 54321 have 0, 2, and 4 descents, respectively. Any permutation obtained from 12345 by one block move has (at most) one descent, at the left edge of the moved block. Similarly, any permutation obtained from 54321 by one block move has (at least) three descents, so that we can’t get from 54321 to 12345 by two block moves. Score 20 points for the correct answer, 10 points for a numerical example proving that is attainable, and 15 points for proving it can’t be done in 2 or fewer moves. Problem O7 [55 points] ∑ 5 ∞ n Evaluate . n =1 n ! ∑ ∑ ∑ ∞ n ∞ 1 ∞ 1 Solution: We start by noticing that = = = e . Next we see that n =1 n =1 n =0 n ! ( n − 1)! n ! ∑ ∑ ∑ ∑ ∑ ∑ 2 k ∞ n ∞ n ∞ 1+ n ∞ 1 ∞ n ∞ n = = = + = e + e = 2 e . Let f ( k ) = , then n =1 n =1 n =0 n =0 n =0 n =1 n ! ( n − 1)! n ! n ! n ! n ! k − 1 ( ) ∑ ∑ ∑ ∑ k k − 1 (1+ n ) ∞ ∞ ∞ k − 1 k − 1 n n = = , so by the binomial theorem f ( k ) = · f ( j ). n =1 n =1 n =0 j =0 n ! ( n − 1)! n ! j Armed with this formula, we can easily compute f (3) = f (0) + 2 f (1) + f (2) = e + 2 e + 2 e = 5 e , f (4) = 1 · e + 3 · e + 3 · 2 e + 1 · 5 e = 15 e , and f (5) = 1 · e + 4 · e + 6 · 2 e + 4 · 5 e + 1 · 15 e = 52e . Score 30 points for the correct answer, 25 points for a correct justification. If on the right track with a good justification, but an arithmetic error is made along the way, score 5 points for each f ( j ) , j = 0 , 1 , 2 , 3 , 4, correctly computed. Problem O8 [55 points] What is the smallest square-free composite number that can divide a number of the form 4242 . . . 42 ± 1? Solution: It is easy to see that such a number can never be divisible by 2, 3, 5, or 7. They can be divisible by 11, the smallest example being 4242424241 = 11 · 547 · 705073. What makes this ∑ n 2 i problem hard is finding the next prime that can divide such a number. Let T = 42 · 10 . n i =0 Then the numbers T modulo a prime p will always be periodic, since T = 100 T + 42, so we just n n n 1 need to compute one period and see if it contains ± 1. Thus we find that modulo 13 we get 3, 4, 0, 3, . . . , modulo 17 we get 8, 9, 7, 11, 3, 2, 4, 0, 8, . . . , modulo 19 we get 4, 5, 10, 16, 8, 6, 15, 3, 0, 4, . . . , and modulo 23 we get 19, 10, 7, 6, 21, 3, 20, 18, 2, 12, 0, 19, . . . , so none of these primes can ever divide T ± 1. But 424241 = 29 · 14629, so 29 can also divide numbers of this form. Therefore n the smallest composite number that can divide T ± 1 for some n is 319 , and the smallest such n n is 83. Score 30 points for the correct answer, 15 points for showing it is the smallest, 10 points for showing it does work. Just seeing that 11 is the smallest prime divisor is worth 5 points, finding for exactly which n is worth 5 more. 3

Problem O9 [60 points] You are somewhere on a ladder with 5 rungs. You have a fair coin and an envelope that contains either a double-headed coin or a double-tailed coin, each with probability 1/2. Every minute you flip a coin. If it lands heads you go up a rung, if it lands tails you go down a rung. If you move up from the top rung you win, if you move down from the bottom rung you lose. You can open the envelope at any time, but if you do then you must immediately flip that coin once, after which you can use it or the fair coin whenever you want. What is the best strategy (i.e. on what rung(s) should you open the envelope)? Solution: First consider the probability of winning if you never open the envelope. Let q ( n ) be the q ( n − 1)+ q ( n +1) probability of winning from the n th rung with just the fair coin, then q ( n ) = , so it 2 is not hard to calculate that q ( n ) = n/ 6. If we open the envelope, then there’s a 1/2 chance that it is heads and we win, and a 1/2 chance that it is tails and we end up one rung down with just the fair coin (obviously we keep using the double sided coin iff it is double headed). Let us start by analyzing rung 1. If we don’t open the envelope, then we have a 1/2 chance of losing and a 1/2 chance of ending up on rung 2 with the envelope. If we do open the envelope, then we have a 1/2 chance of losing and a 1/2 chance of winning, which is a better outcome, so we should open the envelope on rung 1. Next we look at rung 5. If we don’t open the envelope, then we have a 1/2 chance of winning and a 1/2 chance of moving down to rung 4 with the envelope. If we do open the envelope, then we we have a 1/2 chance of winning and a 1/2 chance of moving down to rung 4 without the envelope. Let p ( n ) be the probability of winning from rung n if we are there with the envelope still unopened. Then clearly p ( n ) ≥ q ( n ) for all n if we’re using optimal strategy, so we should not open the envelope on rung 5. Next we look at rung 4. If we open the envelope, then our chance of winning is 1 / 2 + q (3) / 2 = 3 / 4. If we don’t, then our chance of winning is p (5) / 2 + p (3) / 2. We do know that p (5) = 1 / 2 + p (4) / 2, but this is not enough to tell us what to do on rung 4. Looking at rung 3, we can open the envelope for a probability 1 / 2 + q (2) / 2 = 2 / 3 of winning, and we can not open the envelope for a probability p (4) / 2 + p (2) / 2 of winning. On rung 2, we can open the envelope for a probability 1 / 2 + q (1) / 2 = 7 / 12 of winning, and we can not open the envelope for a probability p (3) / 2 + p (1) / 2 = p (3) / 2 + 1 / 4 of winning. Now we can use all this information together for the complete answer. We know p (2) ≥ 7 / 12, 1 / 2+ p (4) / 2 therefore p (3) ≥ p (4) / 2 + 7 / 24, and we know p (4) ≥ p (5) / 2 + p (3) / 2 ≥ + p (3) / 2 ≥ 2 1 / 2+ p (4) / 2 p (4) / 2+7 / 24

• . Isolating p (4) in this inequality, we get p (4) ≥ 1 / 2+7 / 24 > 3 / 4, therefore we 2 2 should not open the envelope on rung 4. Now from p (4) = p (5) / 2+ p (3) / 2 and p (5) = 1 / 2+ p (4) / 2 1 / 2+ p (4) / 2 we have p (4) = + p (3) / 2, so p (3) = 3 p (4) / 2 − 1 / 2 ≥ 11 / 16 > 2 / 3, so we should not open 2 the envelope on rung 3. Now p (2) ≥ p (3) / 2 + 1 / 4 ≥ 19 / 32 > 7 / 12, so we should not open the envelope on rung 2. Therefore the best strategy is to open the envelope iff we are on the bottom rung. For each rung, score 4 points for the correct answer and 8 more for a correct justification. Problem O10 [75 points] A, B, C, D , and E are relatively prime integers (i.e., have no single common factor) such that the 4 3 2 3 2 polynomials 5 Ax + 4 Bx + 3 Cx + 2 Dx + E and 10 Ax + 6 Bx + 3 Cx + D together have 7 distinct integer roots. What are all possible values of A ? Your team has been given a sealed envelope that contains a hint for this problem. If you open the envelope, the value of this problem decreases by 20 points. To get full credit, give the sealed envelope to the judge before presenting your solution. 4

Hint: Consider A = 1 , B = D = 0 , C = 750, and E = 19845. Solution: Call the negatives of the roots of the first polynomial a, b, c, d , and the negatives of the roots of the second polynomial e, f, g (using the negatives avoids negative signs for the rest of the 4 3 2 proof, thus preventing the possibility of dropping a sign). Then 5 Ax + 4 Bx + 3 Cx + 2 Dx + E = 3 2 5 A ( x + a )( x + b )( x + c )( x + d ) and 10 Ax + 6 Bx + 3 Cx + D = 10 A ( x + e )( x + f )( x + g ). Thus 5 5 5 10 B = A ( a + b + c + d ) = A ( e + f + g ), C = A ( ab + ac + ad + bc + bd + cd ) = A ( ef + eg + f g ), 4 3 3 3 5 D = A ( abc + abd + acd + bcd ) = 10 A ( ef g ), and E = 5 A ( abcd ). From these equations we see that 2 since all the variables are integers, it must be the case that A | B , A | 3 C , A | D , and A | E , therefore A, B, C, D , and E can only be relatively prime if A is ± 1 or ± 3 . Now we need numerical examples to show that both of these are possible. Without loss of generality let g = 0, so D = 0. Then e √ 2 − 3 B ± 9 B − 30 AC 2 and f are , so 9 B − 30 AC must be a perfect square. Let B = 0 in the hope that 10 A solutions will still exist to this simplified problem. First let us try to find an example with A = − 1, so we need 30 C to be a perfect square. This first happens for C = 30, and in that case e and f are ± 3. We need a + b + c + d = 0, so let’s try to look for a = − b , c = − d . This doesn’t work for C = 30 since 3 C/ 5 = 18 is not the sum of two distinct squares. For that we will need to try 2 C = 5 · 30 = 750, for which we get e, f = ± 15, a, b = ± 3, and c, d = ± 21. Thus for A = ± 1 we can use B = D = 0 , C = ∓ 750, and E = ± 19845. Similarly we can find A = ± 3 , B = D = 0 , C = ∓ 250, and E = ± 735, for which ( a, b, c, d, e, f, g ) = (1 , − 1 , 7 , − 7 , 5 , − 5 , 0). Note that these give us quintic polynomials with integer coefficients possessing 4 relative extrema 5 3 and 3 points of inflection at lattice points, such as 3 x − 250 x + 735 x . Score 20 points for the correct answer, 15 points for a correct justification, 20 points for a numerical example for ± 1, 20 points for a numerical example for ± 3. If the sealed envelope isn’t presented at the beginning of the solution, no credit is given for the ± 1 example. If the ± is forgotten, give 10 points for the answer, 10 for the justification, and 10 for each numerical example. There are infinitely many possible examples, so anything other than the two given above must be checked for accuracy. 5