11th USA Mathematical Olympiad 1982 Problems
1. A graph has 1982 points. Given any four points, there is at least one joined to the other three. What is the smallest number of points which are joined to 1981 points?
2. Show that if m, n are positive integers such that (xm+n + ym+n + zm+n)/(m+n) = (xm + ym + zm)/m (xn + yn + zn)/n for all real x, y, z with sum 0, then {m, n} = {2, 3} or {2, 5}.
3. D is a point inside the equilateral triangle ABC. E is a point inside DBC. Show that area DBC/(perimeter DBC)2 > area EBC/(perimeter EBC)2.
4. Show that there is a positive integer k such that, for every positive integer n, k 2n + 1 is composite.
5. O is the center of a sphere S. Points A, B, C are inside S, OA is perpendicular to AB and AC, and there are two spheres through A, B, and C which touch S. Show that the sum of their radii equals the radius of S.
Solution
11th USA Mathematical Olympiad 1982
Problem 1
A graph has 1982 points. Given any four points, there is at least one joined to the other three. What is the smallest number of points which are joined to 1981 points?
Solution
Answer: 1979.
Suppose there were 4 points not joined to 1981 points. Let one of them be A. Take a point B not joined to A. Now if X and Y are any two other points, X and Y must be joined, because otherwise none of the points A, B, X, Y could be joined to the other 3. There must be two other points C and D not joined to 1981 points. We have just shown that C must be joined to every point except possibly A and B. So it must be not joined to one of those. Similarly D. But now none of A, B, C, D is joined to the other 3. Contradiction. So there cannot be 4 points not joined to 1981 points. But there can be 3. Just take the graph to have all edges except AB and AC. Problem 2
Show that if m, n are positive integers such that (xm+n + ym+n + zm+n)/(m+n) = (xm + ym + zm)/m (xn + yn + zn)/n for all real x, y, z with sum 0, then {m, n} = {2, 3} or {2, 5}.
Solution
Put z = - x - y. If m and n are both odd, the lhs has a term in xm+n but the rhs does not. So at least one of m and n is even. Suppose both are even. Then comparing terms in xm+n we get 2/(m+n) = 4/mn. Put m = 2M, n = 2N, then MN = M+N. So M must divide N and N must divide M. Hence M = N = 2. So m = n = 4. But put x = y = 1, z = -2, the lhs is (1 + 1 + 256)/8 = 129/4 and the rhs is ( (1 + 1 + 16)/4)2 = 81/4. So one of m, n must be odd and the other even. Without loss of generality we may take m odd.
Comparing the terms in xm+n-1y, the coefficient on the lhs is 1. On the rhs it is 1 x 2/n. So we must have n = 2. Put x = y = 1, z = -2. We get lhs = (1 + 1 - 2m+2)/(m+2) and rhs = (1 + 1 + 4)/2 x (1 + 1 - 2m)/m. So (6 - m)2m-1= 2m+6. We cannot have m > 6 or the lhs is negative. Trying m = 1, 3, 5 we find that 3 and 5 are the only solutions.
Arguably, we still have to verify that m=3, n=2 and m=5, n=2 are solutions. That is just tedious algebra. [We do have equality for those values.]
D is a point inside the equilateral triangle ABC. E is a point inside DBC. Show that area DBC/(perimeter DBC)2 > area EBC/(perimeter EBC)2.
Solution
Let us find an expression for t = (area DBC)/(perimeter DBC)2. Let angle B = 2x, angle C = 2y and angle D = 2z and let the inradius be r. Then area DBC = r/2 x perimeter DBC. Also BC = r cot x + r cot y, and similarly for the other sides, so perimeter = 2r(cot x + cot y + cot z). Hence t = 1/(4 (cot x + cot y + cot z) ). Putting z = 90o - x - y, we get 1/4t = cot x + cot y + (cot x + cot y)/(cot x cot y - 1). Now EBC has both x and y smaller than DBC, and cot x is a decreasing function of x (certainly for x in the range 0 to 30o). So writing u = cot x, v = cot y, it is sufficient to show that u + v + (u + v)/(uv - 1) is an increasing function of u. [It is symmetric, so it follows that it is also an increasing function of v.] We have x, y < 30o, and hence u, v > √3, so we need the result at least for u, v > √3.
We have u + v + (u + v)/(uv - 1) = u + v + 1/v (uv - 1)/(uv - 1) + (v + 1/v)/(uv - 1). In considering the dependence on u, we can ignore the terms that do not depend on u, so we have u + (1 + 1/v2)/(u - 1/v). Put k = u - 1/v, then we have to consider k + h2/k, where h2 = 1 + 1/v2. But this is an increasing function for k > h (see below). Thus u + v + (u + v)/(uv - 1) is an increasing function of u for u - 1/v > (1 + 1/v2)1/2, or for u > 1/v + (1 + 1/v2)1/2. This bound is highest for the smallest v in other words for v = √3, when it is √3. So for v > √3, u + v + (u + v)/(uv - 1) is an increasing function of u for u > √3.
[To see that k + h2/k is increasing for k > h, take k' > k > h. Then k' + h2/k' - k - h2/k = (k' - k) - h2(1/k - 1/k') = (k' - k)(1 - h2/kk') > 0.]
Show that there is a positive integer k such that, for every positive integer n, k 2n + 1 is composite.
Solution
Answer: k = 542258 (for example).
Suppose p is a prime dividing 2b - 1, 0 ≤ a < b and k = -2b-a mod p. Then if n = a mod b, we have k 2n = -2b-a2a+hb = -2(h+1)b = -1 mod p, so k 2n + 1 is divisible by p. So we would like to find a collection of pairs (a, b), such that every positive integer n satisfies n = a mod b for at least one member of the collection. We need the corresponding p distinct so that we can be sure of finding k by the Chinese Remainder theorem which satisfies k = -2b-a mod p for all members of the collection. For the congruences n = a mod b to cover all the integers, we need the lcm of the b to be small relative to their size, so we look for an lcm with many factors.
6 = 2.3 does not work because 22 - 1 = 3, 23 - 1 = 7, 26 - 1 = 327, we cannot find distinct primes p. 10 = 2.5 does not work because there are not enough factors to cover all integers. The mod 2 residue covers 1/2, the mod 5 residue covers 1/5 and the mod 10 residue covers 1/10, but that adds up to less than 1. Similarly 12 does not work. We must drop one of 2, 3, 6. But then the rest cover at most 11 residue classes mod 12. So we try 24. Again we drop 6, but we have:
2: 22 - 1 = 3
3: 23 - 1 = 7
4: 25 - 1 has factor 5
8: 28 - 1 has factor 17
12: 212 - 1 has factor 13
24: 224 - 1 has factor 241
We now find, for example, the following covering set:
0 mod 2 covers the even residues
1 mod 3 covers 1, 7, 13, 19
3 mod 4 covers 3, 11, 15, 23
5 mod 8 covers 5, 21
5 mod 12 covers 17
9 mod 24 covers 9
So we now need k which is
-4 mod 3
-4 mod 7
-2 mod 5
-8 mod 17
-128 mod 13
-215 mod 241
The Chinese Remainder Theorem gives 542258. Comment. This is one of the hardest problems ever set in the USAMO. You have almost no hope of solving it in a reasonable time if you have not seen it before.
O is the center of a sphere S. Points A, B, C are inside S, OA is perpendicular to AB and AC, and there are two spheres through A, B, and C which touch S. Show that the sum of their radii equals the radius of S.
Solution
Let D be the circumcenter of ABC. The triangle ABC is in the plane normal to OA. The two spheres both contain through the circumcircle of ABC, so their centers must lie on a line L normal to the plane ABC and hence parallel to OA. Take the plane through OA and the line L. Suppose the centers are P and Q. The sphere center P must touch S at a point X on the line OP. Similarly, the sphere center Q must touch S at a point Y on the line OQ. Since the spheres pass through A, we have PA = PX and hence OP + PA = R, the radius of the sphere S. Similarly OQ + QA = R. Indeed if K is any point on the line L such that OK + KA = R, then the sphere center K will touch S and pass through A. Since it will also have KD perpendicular to DA, it will contain all points on the circumcircle of ABC. But the locus of points such that OK + KA = R is an ellipse with foci O and A. So it meets the line L in just two points, which must therefore be P and Q. Moreover, since the line L is parallel to OA the points must be equidistant from the midpoint of OA (which is the center of the ellipse). Hence OP = AQ and so AQ + AP = R, as required.
Labels:
USAMO
Previous Article
