HMMT 二月 1999 · ADV 赛 · 第 8 题

Advanced Topics Solutions Harvard-MIT Math Tournament February 27, 1999 Problem AT1 [3 points] One of the receipts for a math tournament showed that 72 identical trophies were purchased for $-99.9-, where the first and last digits were illegible. How much did each trophy cost? Solution: The price must be divisible by 8 and 9. Thus the last 3 digits must be divisible by 8, so the price ends with 992, and the first digit must be 7 to make the total divisible by 9. $799 . 92 / 72 =$ 11 . 11 . Problem AT2 [3 points] Stacy has d dollars. She enters a mall with 10 shops and a lottery stall. First she goes to the lottery and her money is doubled, then she goes into the first shop and spends 1024 dollars. After that she alternates playing the lottery and getting her money doubled (Stacy always wins) then going into a new shop and spending $1024. When she comes out of the last shop she has no money left. What is the minimum possible value of d ? Solution: Work backwards. Before going into the last shop she had $1024, before the lottery she had $512, then$1536, $768, . . . . We can easily prove by induction that if she ran out of money 10 − n after n shops, 0 ≤ n ≤ 10, she must have started with 1024 − 2 dollars. Therefore d is 1023 . Problem AT3 [4 points] An unfair coin has the property that when flipped four times, it has the same probability of turning up 2 heads and 2 tails (in any order) as 3 heads and 1 tail (in any order). What is the probability of getting a head in any one flip? Solution: Let p be the probability of getting a head in one flip. There are 6 ways to get 2 heads and 2 2 2 tails, each with probability p (1 − p ) , and 4 ways to get 3 heads and 1 tail, each with probability 3 2 2 3 p (1 − p ). We are given that 6 p (1 − p ) = 4 p (1 − p ). Clearly p is not 0 or 1, so we can divide by 3 2 p (1 − p ) to get 6(1 − p ) = 4 p . Therefore p is . 5 Problem AT4 [4 points] You are given 16 pieces of paper numbered 16, 15, ..., 2, 1 in that order. You want to put them in the order 1, 2, ..., 15, 16 switching only two adjacent pieces of paper at a time. What is the minimum number of switches necessary? Solution: Piece 16 has to move to the back 15 times, piece 15 has to move to the back 14 times, . . . , piece 2 has to move to the back 1 time, piece 1 has to move to the back 0 times. Since only one piece can move back in each switch, we must have at least 15 + 14 + . . . + 1 = 120 switches. 1

Problem AT5 [5 points] For any finite set S , let f ( S ) be the sum of the elements of S (if S is empty then f ( S ) = 0). Find f ( E ) the sum over all subsets E of S of for S = { 1 , 2 , ..., 1999 } . f ( S ) n 1998 Solution: An n element set has 2 subsets, so each element of S appears in 2 subsets E , so our 1+2+ ... +1999 1998 1998 sum is 2 · = 2 . 1+2+ ... +1999 Problem AT6 [5 points] Matt has somewhere between 1000 and 2000 pieces of paper he’s trying to divide into piles of the same size (but not all in one pile or piles of one sheet each). He tries 2, 3, 4, 5, 6, 7, and 8 piles but ends up with one sheet left over each time. How many piles does he need? Solution: The number of sheets will leave a remainder of 1 when divided by the least common multiple of 2, 3, 4, 5, 6, 7, and 8, which is 8 · 3 · 5 · 7 = 840. Since the number of sheets is between 2 1000 and 2000, the only possibility is 1681. The number of piles must be a divisor of 1681 = 41 , hence it must be 41 . Problem AT7 [5 points] 2 Find an ordered pair ( a, b ) of real numbers for which x + ax + b has a non-real root whose cube is 343. 3 2 Solution: The cube roots of 343 are the roots of x − 343, which is ( x − 7)( x + 7 x + 49). Therefore the ordered pair we want is (7,49) . Problem AT8 [6 points] Let C be a circle with two diameters intersecting at an angle of 30 degrees. A circle S is tangent to both diameters and to C , and has radius 1. Find the largest possible radius of C . Solution: For C to be as large as possible we want S to be as small as possible. It is not hard to see √ √ that this happens in the situation shown below. Then the radius of C is 1 + csc 15 = 1 + 2 + 6 . The computation of sin 15 can be done via the half angle formula. 1 15 S C 2

Problem AT9 [7 points] As part of his effort to take over the world, Edward starts producing his own currency. As part of an effort to stop Edward, Alex works in the mint and produces 1 counterfeit coin for every 99 real ones. Alex isn’t very good at this, so none of the counterfeit coins are the right weight. Since the mint is not perfect, each coin is weighed before leaving. If the coin is not the right weight, then it is sent to a lab for testing. The scale is accurate 95% of the time, 5% of all the coins minted are sent to the lab, and the lab’s test is accurate 90% of the time. If the lab says a coin is counterfeit, what is the probability that it really is? Solution: 5% of the coins are sent to the lab, and only .95% of the coins are sent to the lab and counterfeit, so there is a 19% chance that a coin sent to the lab is counterfeit and an 81% chance that it is real. The lab could correctly detect a counterfeit coin or falsely accuse a real one of being counterfeit, so the probability that a coin the lab says is counterfeit really is counterfeit is 19 / 100 · 9 / 10 19 = . 19 / 100 · 9 / 10+81 / 100 · 1 / 10 28 Problem AT10 [8 points] Find the minimum possible value of the largest of xy , 1 − x − y + xy , and x + y − 2 xy if 0 ≤ x ≤ y ≤ 1. √ 2 s ± s − 4 p Solution: I claim the answer is 4/9. Let s = x + y , p = xy , so x and y are . Since x 2 2 and y are real, s − 4 p ≥ 0. If one of the three quantities is less than or equal to 1/9, then at least one of the others is at least 4/9 by the pigeonhole principle since they add up to 1. Assume 2 2 that s − 2 p < 4 / 9, then s − 4 p < (4 / 9 + 2 p ) − 4 p , and since the left side is non-negative we get 5 4 1 4 1 4 2 0 ≤ p − p + = ( p − )( p − ). This implies that either p ≤ or p ≥ , and either way we’re 9 81 9 9 9 9 4 done. This minimum is achieved if x and y are both 1/3, so the answer is , as claimed. 9 3