HMMT 二月 1999 · ORAL 赛 · 第 1 题

英文解析

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. Findthe 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 sumis 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 invitedschools. Pei-Hsin usually just stuffs the envelopes, but if Alex leaves the room she has to lick themas well and has a 25% chance of dying from an allergic reaction before he gets back. Licking theglue makes Edward a bit psychotic, so if Alex leaves the room there is a 20% chance that Edwardwill kill Pei-Hsin before she can start licking envelopes. Alex leaves the room and comes back tofind 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. Theenvelope 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 theanswer is 50% , or 1/2 .
Score 20 points for the correct answer, 5 points for a correct justification. Not many places to givepartial 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 possiblevalue of x + y + z .
Solution 1: Without loss of generality let x > y . We must have z expressible as the sum of two 3
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, thusx + 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.
Score 20 points for the correct answer, 5 points for justifying that we can’t do better with z ≤ 5, 51
points for justifying that we can’t do better with z > 5.
Problem O4 [35 points]
∑
∞ cos nθ 1
Evaluate , where cos θ = .
n =0 n
2 5
∑
∞ einθinθ
Solution: cos nθ is the real part of e , so the sum is the real part of . This is a geometricnn =0
√2
e 1 1 2 6 iθseries with initial term 1 and ratio , so its sum is . We are given cos θ = , so sin θ = ± .
2 5 5 iθ
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 rand r be the inradii of triangles ABD and ACD . Prove that r , r , and r can always be the side 1
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 thatr + 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 shouldget 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 setof 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 ofblock 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 dowe know we can’t do it in 2 moves? From any position there are 20 possible permutations via blockmoves, 16 from moving a block of size 1 and 4 from moving a block of size 2. One could simplywrite the 20 permutations of 54321 and the 20 permutations of 12345 and try to see that they havenothing in common, which would suffice since the inverse of a block move is also a block move. Amore 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 permutationsfrom block moves, namely 3421, 3241, 3214, 4231, 4213, 2431, 4312, 1432, 4132, and 2143. The 10
permutations of 1234 are 2134, 2314, 2341, 1324, 1342, 3124, 1243, 4123, 1423, and 3412. These 2
two sets of permutations have nothing in common, thus it takes at least 3 moves to sort 4321, andhence 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 permutationof { 1 , 2 , 3 , 4 , 5 } (or any ordered set), define a descent to be an adjacent pair of numbers in thepermutation 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 byone block move has (at most) one descent, at the left edge of the moved block. Similarly, anypermutation obtained from 54321 by one block move has (at least) three descents, so that we can’tget 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]
∑
∞ n 5
Evaluate .
n =1
n !
∑ ∑ ∑
∞ n ∞ 1 ∞ 1
Solution: We start by noticing that = = = e . Next we see thatn =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 ) = , thenn =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 = 52 e .
Score 30 points for the correct answer, 25 points for a correct justification. If on the right trackwith a good justification, but an arithmetic error is made along the way, score 5 points for eachf ( 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
∑
2 inproblem hard is finding the next prime that can divide such a number. Let T = 42 · 10 .
i =0 n
Then the numbers T modulo a prime p will always be periodic, since T = 100 T + 42, so we justn n nneed to compute one period and see if it contains ± 1. Thus we find that modulo 13 we get 3, 4, 0,1
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 canever divide T ± 1. But 424241 = 29 · 14629, so 29 can also divide numbers of this form. Thereforethe smallest composite number that can divide T ± 1 for some n is 319 , and the smallest such nnnis 83.
Score 30 points for the correct answer, 15 points for showing it is the smallest, 10 points for showingit does work. Just seeing that 11 is the smallest prime divisor is worth 5 points, finding for exactlywhich n is worth 5 more.
Problem O9 [60 points]3
You are somewhere on a ladder with 5 rungs. You have a fair coin and an envelope that containseither a double-headed coin or a double-tailed coin, each with probability 1/2. Every minute youflip a coin. If it lands heads you go up a rung, if it lands tails you go down a rung. If you moveup from the top rung you win, if you move down from the bottom rung you lose. You can openthe envelope at any time, but if you do then you must immediately flip that coin once, after whichyou 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 theq ( n − 1)+ q ( n +1)
probability of winning from the n th rung with just the fair coin, then q ( n ) = , so itis not hard to calculate that q ( n ) = n/ 6. If we open the envelope, then there’s a 1/2 chance that 2
it is heads and we win, and a 1/2 chance that it is tails and we end up one rung down with justthe fair coin (obviously we keep using the double sided coin iff it is double headed). Let us startby 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 theenvelope 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 openthe 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, sowe 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 isp (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 todo on rung 4. Looking at rung 3, we can open the envelope for a probability 1 / 2 + q (2) / 2 = 2 / 3 ofwinning, 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 openthe 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 ≥
1 / 2+ p (4) / 2 p (4) / 2+7 / 242 + . 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 openthe envelope on rung 3. Now p (2) ≥ p (3) / 2 + 1 / 4 ≥ 19 / 32 > 7 / 12, so we should not open the 2
envelope on rung 2. Therefore the best strategy is to open the envelope iff we are on the bottomrung.
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 distinctinteger roots. What are all possible values of A ? Your team has been given a sealed envelope thatcontains 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.
Hint: Consider A = 1 , B = D = 0 , C = 750, and E = 19845.4
Solution: Call the negatives of the roots of the first polynomial a, b, c, d , and the negatives of theroots 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
D = A ( abc + abd + acd + bcd ) = 10 A ( ef g ), and E = 5 A ( abcd ). From these equations we see that 5
since all the variables are integers, it must be the case that A | B , A | 3 C , A | D , and A | E , therefore 2
A, B, C, D , and E can only be relatively prime if A is ± 1 or ± 3 . Now we need numerical examplesto show that both of these are possible. Without loss of generality let g = 0, so D = 0. Then e
√
− 3 B ± 9 B − 30 AC2
and f are , so 9 B − 30 AC must be a perfect square. Let B = 0 in the hope that 2
10 Asolutions 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 fare ± 3. We need a + b + c + d = 0, so let’s try to look for a = − b , c = − d . This doesn’t workfor C = 30 since 3 C/ 5 = 18 is not the sum of two distinct squares. For that we will need to try
C = 5 · 30 = 750, for which we get e, f = ± 15, a, b = ± 3, and c, d = ± 21. Thus for A = ± 1 we can 2
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 numericalexample for ± 1, 20 points for a numerical example for ± 3. If the sealed envelope isn’t presentedat 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 areinfinitely many possible examples, so anything other than the two given above must be checked foraccuracy. 5