HMMT 二月 1999 · 代数 · 第 5 题

英文解析

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 − ba − 1 3 23
Solution: If = 0, then a − 1 = 0, or ( a − 1)( a + a + 1) = 0. Thus a = 1, which is ana − 1
extraneous solution since that makes the denominator of the original expression 0, or a is a root
√
− 1 ± − 3
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 .2
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 theplatform to fall in (taking Alex with it) after traveling 100 ft. One minute after the platform waslaunched, 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 thetime that one end of Alex’s platform is between the two ends of the new platform, thus giving Alexas much time as possible to switch. If both platforms are 5 ft long and move with constant velocityonce 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 vbe 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 switchv − 1 v − 1
is . Hence we want v to be as small as possible while still allowing the switch before the first 10
v − 1
platform falls. Therefore the time to switch will be maximized if the back of the second platformlines up with the front of the first platform at the instant that the first platform has travelled 100 ft,
which occurs after 100 seconds. Since the second platform is launched 65 seconds later and has totravel 105 feet, its speed is 105 / 35 = 3 ft/s.
Problem A4 [4 points]1
2 2 d
Find all possible values of where a − 6 ad + 8 d = 0, a 6 = 0.
d da
2 2 2 2
Solution: Dividing a − 6 ad + 8 d = 0 by a , we get 1 − 6 + 8( ) = 0. The roots of this quadratica 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, theyellow 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 minesor open two doors when only one is armed/closed will reset the system to its initial state. What isthe 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 buttonr times, the yellow button y times, and the green button g times, there will be 3 + r − 2 y armedmines and 3 + y − 2 g closed doors, so we want the values of r , y , and g that make both of thesequantities 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, andr = 2 y − 3 ≥ 3, so r + y + g ≥ 9. Call the red, yellow, and green buttons 1, 2, and 3 respectively fornotational convenience, then a sequence of buttons that would get you out is 123123123. Anotherpossibility 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.
Thus in the first day they complete a + b + c = (1 / 6 + 1 / 3 + 1 / 5) = 7 / 20, leaving 13/20 for Anne 1
13 / 202
and Bob to complete. This takes = 39 / 20 days, for a total of .59
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 pilesbut 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 commonmultiple 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 = 41 ,2
hence it must be 41 .
Problem A8 [6 points]2
If f ( x ) is a monic quartic polynomial such that f ( − 1) = − 1, f (2) = − 4, f ( − 3) = − 9, andf (4) = − 16, find f (1).
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 2
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 waysto tile a 3 × 2. Let T be the number of tilings of a 3 × n rectangle, where n is even. From thediagram below we see the recursion T = 3 T + 2( T + T + . . . + T + T ). Given that, wenn n − 2 n − 4 n − 6 2 0
can just calculate T = 11, T = 41, and T is 153 .
4 6 8
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 insuch 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 thepyramid, choosing each of the possible paths with probability each time. What is the probability 1
that he ends up at the point (8 , 9 , 0)?9
Solution 1: Start by figuring out the probabilities of ending up at each point on the way down thepyramid. Obviously we start at the top vertex with probability 1, and each point on the next leveldown with probability 1/9. Since each probability after n steps will be some integer over 9 , wenwill look only at those numerators. The third level down has probabilities as shown below. Thinkof this as what you would see if you looked at the pyramid from above, and peeled off the top twolayers.
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
What we can observe here is not only the symmetry along vertical, horizontal, and diagonal axes,3
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 forthe probability of ending up at (8 , 9 , 0), we need only know that this is true for the top two rowsof the square of probabilities, which depend only on the top two rows of the previous layer. Thiswill follow from the calculation of the top row of each square, which we can do via an algorithmsimilar to Pascal’s triangle. In the diagram below, each element is the sum of the 3 above it.
1 1 11
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 factis easily proved by induction on n , so the details are left to the reader. Now we can calculate the 2
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
(8,9,0) is .550
Solution 2: At each move, the x and y coordinates can each increase by 1, decrease by 1, or stay 910
the same. The y coordinate must increase 9 times and stay the same 1 times, the x coordinate caneither increase 8 times and stay the same 1 time or decrease 1 time and increase 9 times. Now weconsider every possible case. First consider the cases where the x coordinate decreases once. If thex 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!
paths to (8,9,0), out of 9 0 possible paths to the bottom, so the probability of ending up at the 1
point (8,9,0) is .550
4910