HMMT 二月 1999 · 代数 · 第 9 题

Algebra Solutions Harvard-MIT Math Tournament February 27, 1999 Problem A1 [3 points] 3 3 a − b If a @ b = , for how many real values of a does a @1 = 0? a − b 3 a − 1 3 2 Solution: If = 0, then a − 1 = 0, or ( a − 1)( a + a + 1) = 0. Thus a = 1, which is an a − 1 extraneous solution since that makes the denominator of the original expression 0, or a is a root √ − 1 ± − 3 2 of a + a + 1. But this quadratic has no real roots, in particular its roots are . Therefore 2 there are no such real values of a , so the answer is 0 . Problem A2 [3 points] For what single digit n does 91 divide the 9-digit number 12345 n 789? Solution 1: 123450789 leaves a remainder of 7 when divided by 91, and 1000 leaves a remainder of 90, or -1, so adding 7 multiples of 1000 will give us a multiple of 91. Solution 2: For those who don’t like long division, there is a quicker way. First notice that 91 = 7 · 13, and 7 · 11 · 13 = 1001. Observe that 12345 n 789 = 123 · 1001000+45 n · 1001 − 123 · 1001+123 − 45 n +789 It follows that 91 will divide 12345 n 789 iff 91 divides 123 − 45 n + 789 = 462 − n . The number 462 is divisible by 7 and leaves a remainder of 7 when divided by 13. Problem A3 [4 points] Alex is stuck on a platform floating over an abyss at 1 ft/s. An evil physicist has arranged for the platform to fall in (taking Alex with it) after traveling 100ft. One minute after the platform was launched, Edward arrives with a second platform capable of floating all the way across the abyss. He calculates for 5 seconds, then launches the second platform in such a way as to maximize the time that one end of Alex’s platform is between the two ends of the new platform, thus giving Alex as much time as possible to switch. If both platforms are 5 ft long and move with constant velocity once launched, what is the speed of the second platform (in ft/s)? Solution: The slower the second platform is moving, the longer it will stay next to the first platform. However, it needs to be moving fast enough to reach the first platform before it’s too late. Let v be the velocity of the second platform. It starts 65 feet behind the first platform, so it reaches the 60 70 back of the first platform at seconds, and passes the front at seconds, so the time to switch v − 1 v − 1 10 is . Hence we want v to be as small as possible while still allowing the switch before the first v − 1 platform falls. Therefore the time to switch will be maximized if the back of the second platform lines up with the front of the first platform at the instant that the first platform has travelled 100ft, which occurs after 100 seconds. Since the second platform is launched 65 seconds later and has to travel 105 feet, its speed is 105 / 35 = 3 ft/s. 1

Problem A4 [4 points] d 2 2 Find all possible values of where a − 6 ad + 8 d = 0, a 6 = 0. a d d 2 2 2 2 Solution: Dividing a − 6 ad + 8 d = 0 by a , we get 1 − 6 + 8( ) = 0. The roots of this quadratic a a 1 1 are , . 2 4 Problem A5 [5 points] You are trapped in a room with only one exit, a long hallway with a series of doors and land mines. To get out you must open all the doors and disarm all the mines. In the room is a panel with 3 buttons, which conveniently contains an instruction manual. The red button arms a mine, the yellow button disarms two mines and closes a door, and the green button opens two doors. Initially 3 doors are closed and 3 mines are armed. The manual warns that attempting to disarm two mines or open two doors when only one is armed/closed will reset the system to its initial state. What is the minimum number of buttons you must push to get out? Solution: Clearly we do not want to reset the system at any time. After pressing the red button r times, the yellow button y times, and the green button g times, there will be 3 + r − 2 y armed mines and 3 + y − 2 g closed doors, so we want the values of r , y , and g that make both of these quantities 0 while minimizing r + y + g . From the number of doors we see that y must be odd, from the number of mines we see y = (3 + r ) / 2 ≥ 3 / 2, so y ≥ 3. Then g = (3 + y ) / 2 ≥ 3, and r = 2 y − 3 ≥ 3, so r + y + g ≥ 9. Call the red, yellow, and green buttons 1, 2, and 3 respectively for notational convenience, then a sequence of buttons that would get you out is 123123123. Another possibility is 111222333, and of course there are others. Therefore the answer is 9 . Problem A6 [5 points] Carl and Bob can demolish a building in 6 days, Anne and Bob can do it in 3, Anne and Carl in 5. How many days does it take all of them working together if Carl gets injured at the end of the first day and can’t come back? Express your answer as a fraction in lowest terms. Solution: Let a be the portion of the work that Anne does in one day, similarly b for Bob and c for Carl. Then what we are given is the system of equations b + c = 1 / 6, a + b = 1 / 3, and a + c = 1 / 5. 1 Thus in the first day they complete a + b + c = (1 / 6 + 1 / 3 + 1 / 5) = 7 / 20, leaving 13/20 for Anne 2 13 / 20 59 and Bob to complete. This takes = 39 / 20 days, for a total of . 1 / 3 20 Problem A7 [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 . 2

Problem A8 [6 points] If f ( x ) is a monic quartic polynomial such that f ( − 1) = − 1, f (2) = − 4, f ( − 3) = − 9, and f (4) = − 16, find f (1). 2 Solution: The given data tells us that the roots of f ( x ) + x are -1, 2, -3, and 4. Combining with 2 the fact that f is monic and quartic we get f ( x ) + x = ( x + 1)( x − 2)( x + 3)( x − 4). Hence f (1) = (2)( − 1)(4)( − 3) − 1 = 23 . Problem A9 [7 points] How many ways are there to cover a 3 × 8 rectangle with 12 identical dominoes? Solution: Trivially there is 1 way to tile a 3 × 0 rectangle, and it is not hard to see there are 3 ways to tile a 3 × 2. Let T be the number of tilings of a 3 × n rectangle, where n is even. From the n diagram below we see the recursion T = 3 T + 2( T + T + . . . + T + T ). Given that, we n n − 2 n − 4 n − 6 2 0 can just calculate T = 11, T = 41, and T is 153 . 4 6 8 . . . . . . etc... Problem A10 [8 points] Pyramid EARLY is placed in ( x, y, z ) coordinates so that E = (10 , 10 , 0), A = (10 , − 10 , 0), R = ( − 10 , − 10 , 0), L = ( − 10 , 10 , 0), and Y = (0 , 0 , 10). Tunnels are drilled through the pyramid in such a way that one can move from ( x, y, z ) to any of the 9 points ( x, y, z − 1), ( x ± 1 , y, z − 1), ( x, y ± 1 , z − 1),( x ± 1 , y ± 1 , z − 1). Sean starts at Y and moves randomly down to the base of the 1 pyramid, choosing each of the possible paths with probability each time. What is the probability 9 that he ends up at the point (8 , 9 , 0)? Solution 1: Start by figuring out the probabilities of ending up at each point on the way down the pyramid. Obviously we start at the top vertex with probability 1, and each point on the next level n down with probability 1/9. Since each probability after n steps will be some integer over 9 , we will look only at those numerators. The third level down has probabilities as shown below. Think of this as what you would see if you looked at the pyramid from above, and peeled off the top two layers. 1 2 3 2 1 2 4 6 4 2 3 6 9 6 3 2 4 6 4 2 1 2 3 2 1 3

What we can observe here is not only the symmetry along vertical, horizontal, and diagonal axes, but also that each number is the product of the numbers at the ends of its row and column (e.g. 6 = 2 · 3). This comes from the notion of independence of events, i.e. that if we east and then south, we end up in the same place as if we had moved south and then east. Since we are only looking for the probability of ending up at (8 , 9 , 0), we need only know that this is true for the top two rows of the square of probabilities, which depend only on the top two rows of the previous layer. This will follow from the calculation of the top row of each square, which we can do via an algorithm similar to Pascal’s triangle. In the diagram below, each element is the sum of the 3 above it. 1 1 1 1 1 2 3 2 1 1 3 6 7 6 3 1 1 4 10 16 19 16 10 4 1 1 5 15 30 45 51 45 30 15 5 1 n ( n +1) Now observe that the first 3 numbers in row n , where the top is row 0, are 1, n , . This fact 2 is easily proved by induction on n , so the details are left to the reader. Now we can calculate the top two rows of each square via another induction argument, or by independence, to establish that the second row is always n times the first row. Therefore the probability of ending up at the point 550 (8,9,0) is . 10 9 Solution 2: At each move, the x and y coordinates can each increase by 1, decrease by 1, or stay the same. The y coordinate must increase 9 times and stay the same 1 times, the x coordinate can either increase 8 times and stay the same 1 time or decrease 1 time and increase 9 times. Now we consider every possible case. First consider the cases where the x coordinate decreases once. If the x coordinate decreases while the y coordinate increases, then we have 8 moves that are the same 10! and 2 that are different, which can be done in = 90 ways. If the x coordinate decreases while 8! the y coordinate stays the same, then we have 9 moves that are the same and 1 other, which can be 10! done in = 10 ways. Now consider the cases where the x coordinate stays the same twice. If the 9! y coordinate stays the same while the x coordinate increases, then we have 7 moves that are the 10! same, 2 that are the same, and 1 other, which can be done in = 360 ways. If the y coordinate 7!2! stays the same while the x coordinate stays the same, then we have 8 moves that are the same and 2 10! that are different, which can be done in = 90 ways. Therefore there are 360 + 90 + 90 + 10 = 550 8! 1 paths to (8,9,0), out of 9 0 possible paths to the bottom, so the probability of ending up at the 550 point (8,9,0) is . 10 9 4