HMMT 二月 1999 · 团队赛 · 第 10 题

英文解析

Team Solutions
Harvard-MIT Math Tournament
February 27, 1999
Problem T1 [15]
A combination lock has a 3 number combination, with each number an integer between 0 and 39
inclusive. Call the numbers n , n , and n . If you know that n and n leave the same remainder
1 2 3 1 3
when divided by 4, and n and n + 2 leave the same remainder when divided by 4, how many
2 1
possible combinations are there?
Solution: There are 40 choices for the last number, and for each of these we have 10 choices foreach of the first two numbers, thus giving us a total of 4000 possible combinations. It is interestingto note that these restrictions are actually true for Master locks.
Problem T2 [15]
A ladder is leaning against a house with its lower end 15 feet from the house. When the lower endis pulled 9 feet farther from the house, the upper end slides 13 feet down. How long is the ladder
(in feet)?
Solution: Of course the house makes a right angle with the ground, so we can use the Pythagoreantheorem. Let x be the length of the ladder and y be the original height at which it touched the
2 2 2 2 2
house. Then we are given x = 15 + y = 24 + ( y − 13) . Isolating y in the second equation weget y = 20, thus x is 25 .
Problem T3 [20]
How many non-empty subsets of { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 } have exactly k elements and do not containthe element k for some k = 1 , 2 , ..., 8.
Solution: Probably the easiest way to do this problem is to count how many non-empty subsets of
{ 1 , 2 , . . . , n } have k elements and do contain the element k for some k . The element k must have
( )
n − 1
k − 1 other elements with it to be in a subset of k elements, so there are such subsets. Nowk − 1
( )
∑
n n − 1
n − 1 n − 1 = (1 + 1) = 2 , so that is how many non-empty sets contain some k and havek =1
k − 1
k elements. The set { 1 , 2 , . . . , n } has 2 subsets (each element either is or is not in a particularnsubset), one of which is the empty set, so the number of non-empty subsets of { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 }
n n − 1 n − 1
have exactly k elements and do not contain the element k for some k is 2 − 2 − 1 = 2 − 1.
In the case n = 8, this yields 127 .
Problem T4 [20]
Consider the equation F ORT Y + T EN + T EN = SIXT Y , where each of the ten letters representsa distinct digit from 0 to 9. Find all possible values of SIXT Y .
Solution: Since Y + N + N ends in Y , N must be 0 or 5. But if N = 5 then T + E + E + 1 ends in 1
T, which is impossible, so N = 0 and E = 5. Since F 6 = S we must have O = 9, R + T + T + 1 > 10,
and S = F + 1. Now I 6 = 0, so it must be that I = 1 and R + T + T + 1 > 20. Thus R and T are
6 and 7, 6 and 8, or 7 and 8 in some order. But X can’t be 0 or 1 since those are taken, and Xcannot be 3 since F and S have to be consecutive, so it must be that R + T + T + 1 is 21 or 23.
This is satisfied only for R = 7 , T = 8, so F = 2 , S = 3, and Y = 6. This SIXT Y = 31486 .
Problem T5 [30]
If a and b are randomly selected real numbers between 0 and 1, find the probability that the nearesta − binteger to is odd.
a + b
Solution: The only reasonable way I know of to do this problem is geometrically (yes, you can useintegrals to find the areas of the triangles involved, but I don’t consider that reasonable). First leta − b 1 a − b 1
us find the points ( a, b ) in the plane for which the nearest integer to is 0, i.e. − ≤ ≤ .
a + b 2 a + b 2
1 a − b
Taking the inequalities one at a time, − ≤ implies that a + b ≥ 2( b − a ), or b ≤ 3 a , so these
2 a + ba − b 1
points must lie below the line y = 3 x . Similarly, ≤ implies that ( a, b ) must lie above thea + b 2
1 a − bline y = x . Now we can look for the points ( a, b ) for which the nearest integer to is 1, i.e.
3 a + b
1 a − b 3
≤ ≤ , and we find that all points in the first quadrant that lie above the line y = 3 x satisfy
2 a + b 2
a − bthis inequality. Similarly, the closest integer to is -1 for all points in the first quadrant belowa + bthe line y = x . For a and b between 0 and 1, the locus of points ( a, b ) for which the nearest integer 1
a − b 1 13
to is odd is two right triangles with legs of length 1 and , so together they have area . Thea + b 3 3
locus of all points ( a, b ) with a and b between 0 and 1 is a square of side length 1, and thus hasa − b 1
area 1. Therefore the probability that the nearest integer to is odd is .
a + b 3
Problem T6 [30]
√ √
√ √
3 3
Reduce the number 2 + 5 + 2 − 5.
√ √ √ √
√ √ √ √ √ √
3 3 3 3
Solution: Observe that ( 2 + 5+ 2 − 5) = (2+ 5) − 3( 2 + 5) − 3( 2 − 5)+(2 − 5) =3
√ √ √ √
√ √ √ √
3 3 3 3
4 − 3( 2 + 5 + 2 − 5). Hence 2 + 5 + 2 − 5 is a root of the cubic x + 3 x − 4 =3
√ √
√ √
3 3
2 2
( x − 1)( x + x + 4). The roots of x + x + 4 are imaginary, so 2 + 5 + 2 − 5 = 1 .
Problem T7 [30]
∑
1 ∞
n 2
Let = a x , for what positive integers n does a = n ?
2 3 n n − 1
i =0
1 − x − x − x
2 3
Solution: Multiplying both sides by 1 − x − x − x the right hand side becomes a +( a − a ) x +( a −
0 1 0 2
2 na − a ) x + . . . , and setting coefficients of x equal to each other we find that a = 1 , a = 1 , a = 2,
1 0 0 1 2
and a = a + a + a for n ≥ 3. Thus the sequence of a ’s starts 1, 1, 2, 4, 7, 13, 24, 44, 81,
n n − 1 n − 2 n − 3 n
2 2
149, . . . . So we now see that a = 1 and a = 9 . What makes it impossible for this to happen again
0 8
is that the sequence is growing exponentially. It will suffice to show that a > 1 . 5 for n > 2, sincenn
2 2 2
n / ( n − 1) < 1 . 5 for n ≥ 6, thus when a exceeds n at n = 10 there can be no more solutionsn − 1
to a = n . Observe that a > 1 . 5 a for n = 3 , 4 , 5. By way of induction, assume it for n − 2,2
n − 1 n n − 1
n n − 1 n − 2 n − 2 2 n +12
n − 1, and n , then a = a + a + a > 1 . 5 +1 . 5 +1 . 5 = 1 . 5 (1+1 . 5+1 . 5 ) > 1 . 5 .
n +1 n n − 1 n − 2
Thus, by induction, a > 1 . 5 for n > 2, so the only solutions are 1, 9 .nn
Problem T8 [35]
2 2 2
Find all the roots of ( x + 3 x + 2)( x − 7 x + 12)( x − 2 x − 1) + 24 = 0.
2 2 2
Solution: We re-factor as ( x + 1)( x − 3)( x + 2)( x − 4)( x − 2 x − 1) + 24, or ( x − 2 x − 3)( x −
2 2
2 x − 8)( x − 2 x − 1) + 24, and this becomes ( y − 4)( y − 9)( y − 2) + 24 where y = ( x − 1) . Now,
( y − 4)( y − 9)( y − 2) + 24 = ( y − 8)( y − 6)( y − 1), so y is 1, 6, or 8. Thus the roots of the original
√ √
polynomial are 0 , 2 , 1 ± 6 , 1 ± 2 2 .
Problem T9 [40]
∑
17 n + n +12
Evaluate .
4 3 2
n =2
n +2 n − n − 2 n
4 3 2
Solution: Observe that the denominator n + 2 n − n − 2 n = n ( n − 1)( n + 1)( n + 2). Thus we cann − n +1 a b c d 2
rewrite the fraction as = + + + for some real numbers a , b , c , and d . This
4 3 2
n − 1 n n +1 n +2
n +2 n − n − 2 n
4 3 2
method is called partial fractions . Condensing the right hand side as a fraction over n +2 n − n − 2 n
2 3 2 3 2 3 2 3
we get n − n + 1 = a ( n + 3 n + 2 n ) + b ( n + 2 n − n − 2) + c ( n + n − 2 n ) + d ( n − n ). Comparingcoefficients of each power of n we get a + b + c + d = 0, 3 a +2 b + c = 2, 2 a − b − 2 c − d = 2, and − 2 b = 2.
This is a system of 4 equations in 4 variables, and its solution is a = 1 / 2 , b = − 1 / 2 , c = 1 / 2, and d =
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 − 1 / 2. Thus the summation becomes (1 − + − + − + − + − + − + · · · + − + − ).
2 2 3 4 2 3 4 5 3 4 5 6 16 17 18 19
1 1 1 1 592
Notice that almost everything cancels to leave us with (1 + − − ) = .
2 3 17 19 969
Problem T10 [45]
If 5 points are placed in the plane at lattice points (i.e. points ( x, y ) where x and y are bothintegers) such that no three are collinear, then there are 10 triangles whose vertices are amongthese points. What is the minimum possible number of these triangles that have area greater than
1/2?
Solution: By the pigeonhole principle, the 5 points cannot all be distinct modulo 2, so two of themmust have a midpoint that is also a lattice point. This midpoint is not one of the 5 since no 3
are collinear. Pick’s theorem states that the area of a polygon whose vertices are lattice points is
B/ 2 + I − 1 where B is the number of lattice points on the boundary and I is the number in theinterior. Thus those two points form the base of 3 triangles whose area will be greater than 1/2 by
Pick’s theorem since there are 4 lattice points on the boundary. Now it also turns out that at leastone of the triangles must contain a lattice point, thus giving us a fourth triangle with area greaterthan 1/2. This is actually pretty easy to show with the aid of a picture or some visualization.
Suppose we have 4 points and we’re trying to find a 5 th one so that no triangle will contain aninterior lattice point. The 4 lattice points must form a quadrilateral of area 1, so in fact it is aparallelogram (think deeply about it). Draw the four sides, extending them throughout the plain.
Each vertex is now the tip of an infinite triangular region of the plane, and if the 5 th lattice pointis chosen in that region then the triangle formed by the 5 th point and the two vertices of theparallelogram adjacent to the one we are considering will form a triangle containing the vertex weare considering. But the part of the plane that isn’t in one of these 4 regions contains no lattice 3
points or else we could draw a parallelogram congruent to the first one with lattice point verticesand containing that lattice point, but that would violate Pick’s theorem since the parallelogram hasarea 1. Therefore we must have a fourth triangle with area greater than 1/2 (one must justify that this really is in addition to the 3 triangles we already knew we’d get). An example that achievesthis minimum is the points (0,0), (1,0), (1,1), (2,1), and (2,-1). Therefore the minumum possiblenumber of these triangles that have area greater than 1/2 is 4 .
A less trivial example that achieves the minimum is (0,0), (1,1), (2,1), (3,2), and (7,5).
Problem T11 [55]
Circles C , C , C have radius 1 and centers O, P, Q respectively. C and C intersect at A , C and
1 2 3 1 2 2
° °
6 6
C intersect at B , C and C intersect at C , in such a way that AP B = 60 , BQC = 36 , and
3 3 1
°
COA = 72 . Find angle ABC (degrees).6
Solution: Using a little trig, we have BC = 2 sin 18, AC = 2 sin 36, and AB = 2 sin 30 (see left
2 2 2
diagram). Call these a , b , and c , respectively. By the law of cosines, b = a + c − 2 ac cos ABC ,
2 2 2
sin 18+sin 30 − sin 36
therefore cos ABC = . In the right diagram below we let x = 2 sin 18 and see
2 sin 18 sin 30
√
− 1+ 5
that x + x = 1, hence sin 18 = . Using whatever trig identities you prefer you can find that 2
√4
2 5 − 5 1 2 2 2
sin 36 = , and of course sin 30 = . Now simplification yields sin 18 + sin 30 − sin 36 = 0,
4 2
°
so ABC = 90 .6
Note that this means that if a regular pentagon, hexagon, and decagon are inscribed in a circle,
then we can take one side from each and form a right triangle.
x 36
x 1
72 2
36 x
3672
x 1
Problem T12 [65]
A fair coin is flipped every second and the results are recorded with 1 meaning heads and 0
meaning tails. What is the probability that the sequence 10101 occurs before the first occuranceof the sequence 010101?
Solution: Call it a win if we reach 10101, a loss if we reach 010101. Let x be the probability ofwinning if the first flip is a 1, let y be the probability of winning if the first flip is a 0. Then the probability of winning is ( x + y ) / 2 since the first flip is 1 or 0, each with probability 1/2. If we everget two 1’s in a row, that is the same as starting with a 1 as far as the probability is concerned.
Similarly, if we get two 0’s in a row, then we might as well have started with a single 0.
start
1 0
11 10... 01 00...
101 100... 011...010
1010 1011... 0101 0100...
10101 10100... 01011... 01010
010101 010100...
From the tree of all possible sequences, shown above, in which the probability of moving along any 4
particular line is 1/2, we see that x = x (1 / 2 + 1 / 8) + y (1 / 4 + 1 / 16) + 1 / 16, and y = x (1 / 4 + 1 / 16) +
y (1 / 2 + 1 / 8 + 1 / 32). Solving these two equations in two unknowns we get x = 11 / 16 and y = 5 / 8.
Therefore the probablity that the sequence 10101 occurs before the first occurance of the sequence
010101 is 21/32 . 5