tceic.com

学霸学习网 这下你爽了

学霸学习网 这下你爽了

Algebra

Harvard-MIT Math Tournament

February 27, 1999

a3 ?b3 a?b ,

1. If a@b =

for how many real values of a does a@1 = 0?

2. For what single digit n does 91 divide the 9-digit number 12345n789? 3. Alex is stuck on a platform ?oating 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 ?oating 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)? 4. Find all possible values of

d a

where a2 ? 6ad + 8d2 = 0, a = 0.

5. 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? 6. 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 ?rst day and can’t come back? Express your answer as a fraction in lowest terms. 7. 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? 8. If f (x) is a monic quartic polynomial such that f (?1) = ?1, f (2) = ?4, f (?3) = ?9, and f (4) = ?16, ?nd f (1). 9. How many ways are there to cover a 3 × 8 rectangle with 12 identical dominoes? 10. 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 pyramid, choosing each of the possible paths with probability 1 9 each time. What is the probability that he ends up at the point (8, 9, 0)?

Algebra Solutions

Harvard-MIT Math Tournament

February 27, 1999

Problem A1 [3 points]

a3 ?b 3 a?b ,

3

If a@b =

for how many real values of a does a@1 = 0?

?1 3 2 Solution: If a a?1 = 0, then a ? 1 = 0, or (a ? 1)(a + a + 1) = 0. Thus a = 1, which is an 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 12345n789? 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 12345n789 = 123 · 1001000+45n · 1001 ? 123 · 1001+123 ? 45n +789 It follows that 91 will divide 12345n789 i? 91 divides 123 ? 45n + 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 ?oating 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 ?oating 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 ?rst platform. However, it needs to be moving fast enough to reach the ?rst platform before it’s too late. Let v be the velocity of the second platform. It starts 65 feet behind the ?rst platform, so it reaches the 70 back of the ?rst platform at v60 ?1 seconds, and passes the front at v ?1 seconds, so the time to switch is v10 ?1 . Hence we want v to be as small as possible while still allowing the switch before the ?rst platform falls. Therefore the time to switch will be maximized if the back of the second platform lines up with the front of the ?rst platform at the instant that the ?rst 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 = 3ft/s. 1

Problem A4 [4 points] Find all possible values of

d a

where a2 ? 6ad + 8d2 = 0, a = 0.

d 2 d + 8( a ) = 0. The roots of this quadratic Solution: Dividing a2 ? 6ad + 8d2 = 0 by a2 , we get 1 ? 6 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 ? 2y armed mines and 3 + y ? 2g 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 = 2y ? 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 ?rst 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. Thus in the ?rst day they complete a + b + c = 1 2 (1/6 + 1/3 + 1/5) = 7/20, leaving 13/20 for Anne 13/20 and Bob to complete. This takes 1/3 = 39/20 days, for a total of 59 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 1000 and 2000, the only possibility is 1681. The number of piles must be a divisor of 1681 = 412 , 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, ?nd f (1). Solution: The given data tells us that the roots of f (x) + x2 are -1, 2, -3, and 4. Combining with the fact that f is monic and quartic we get f (x) + x2 = (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 Tn be the number of tilings of a 3 × n rectangle, where n is even. From the diagram below we see the recursion Tn = 3Tn?2 + 2(Tn?4 + Tn?6 + . . . + T2 + T0 ). Given that, we can just calculate T4 = 11, T6 = 41, and T8 is 153.

...

...

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 pyramid, choosing each of the possible paths with probability 1 9 each time. What is the probability that he ends up at the point (8, 9, 0)? Solution 1: Start by ?guring 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 down with probability 1/9. Since each probability after n steps will be some integer over 9n , 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 o? 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 1 3 2 3 2 1 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

+1) Now observe that the ?rst 3 numbers in row n, where the top is row 0, are 1, n, n(n2 . This fact 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 ?rst row. Therefore the probability of ending up at the point . (8,9,0) is 550 910

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 and 2 that are di?erent, which can be done in 10! 8! = 90 ways. If the x coordinate decreases while the y coordinate stays the same, then we have 9 moves that are the same and 1 other, which can be done in 10! 9! = 10 ways. Now consider the cases where the x coordinate stays the same twice. If the 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 7!2! = 360 ways. If the y coordinate stays the same while the x coordinate stays the same, then we have 8 moves that are the same and 2 that are di?erent, which can be done in 10! 8! = 90 ways. Therefore there are 360 + 90 + 90 + 10 = 550 paths to (8,9,0), out of 91 0 possible paths to the bottom, so the probability of ending up at the point (8,9,0) is 550 . 910

4