30th USA Mathematical Olympiad 2001 Problems
A1. What is the smallest number of colors needed to color 8 boxes of 6 balls (one color for each ball), so that the balls in each box are all different colors and any pair of colors occurs in at most one box.
A2. The incircle of the triangle PBC touches BC at U and PC at V. The point S on BC is such that BS = CU. PS meets the incircle at two points. The nearer to P is Q. Take W on PC such that PW = CV. Let BW and PS meet at R. Show that PQ = RS.
A3. Non-negative reals x, y, z satisfy x2 + y2 + z2 + xyz = 4. Show that xyz ≤ xy + yz + zx <= xyz + 2.
B1. ABC is a triangle and X is a point in the same plane. The three lengths XA, XB, XC can be used to form an obtuse-angled triangle. Show that if XA is the longest length, then ∠BAC is acute.
B2. A set of integers is such that if a and b belong to it, then so do a2 - a, and a2 - b. Also, there are two members a, b whose greatest common divisor is 1 and such that a - 2 and b - 2 also have greatest common divisor 1. Show that the set contains all the integers.
B3. Every point in the plane is assigned a real number, so that for any three points which are not collinear, the number assigned to the incenter is the mean of the numbers assigned to the three points. Show that the same number is assigned to every point.
Solution
30th USA Mathematical Olympiad 2001
Problem A1
What is the smallest number of colors needed to color 8 boxes of 6 balls (one color for each ball), so that the balls in each box are all different colors and any pair of colors occurs in at most one box.
Solution
If each color occurs only twice, then we need at least 8·6/2 = 24 colors. But we can do better, so at least one color occurs more than twice.
If a color occurs 4 times or more, let the first 4 boxes each include it. Then those 4 boxes use 1 + 4·5 = 21 colors. Now the 5th box can use at most one color from each of the first 4 boxes, so it must use another 2 colors as well. Now the 6th box can use at most one color from each of the first 5 boxes, so it must use another color as well. We are now up to 24 colors. But we can do better.
So assume a color occurs 3 times. Let the first 3 boxes each include it. Then those 3 boxes use 1 + 3·5 = 16 colors. The 4th box can use at most one color from each of the first 3 boxes, so it needs at least another 3 colors as well. The 5th box can use at most one color from each of the first 4 boxes, so it needs at least another 2 colors as well. Similarly the 6th box needs at least 1 more color. We are now up to 22.
It can be done with 23 colors, as we show later. The question therefore is whether 22 suffice. If so, then we cannot exceed the lower limits given above, so the boxes must be as shown below, where Ax denotes one of A1, A2, A3, A4, A5. Similarly Bx etc. But the three occurrences of Ex F1 must include a repetition, because there are only two Es to choose from. So 22 does not work.
1 A1 A2 A3 A4 A5
1 B1 B2 B3 B4 B5
1 C1 C2 C3 C4 C5
Ax Bx Cx D1 D2 D3
Ax Bx Cx Dx E1 E2
Ax Bx Cx Dx Ex F1
Ax Bx Cx Dx Ex F1
Ax Bx Cx Dx Ex F1
Finally, 23 does work:
1 2 3 4 5 6 1 7 8 9 10 11 1 12 13 14 15 16 2 7 12 17 18 19 3 8 13 17 20 21 4 9 14 17 21 22 5 10 15 18 20 22 6 11 16 19 21 23 Problem A2 The incircle of the triangle PBC touches BC at U and PC at V. The point S on BC is such that BS = CU. PS meets the incircle at two points. The nearer to P is Q. Take W on PC such that PW = CV. Let BW and PS meet at R. Show that PQ = RS. Solution The excircle opposite P touches BC at S (consider tangents - the tangents from P have length PC + CS etc). Contract about P so that the excircle becomes the incircle. The point S goes to a point on PS at which the incircle touches a line parallel to BC. This point must be Q. Let PC touch the excircle at Z. Then Z goes to V, so PQ/QS = PV/VZ = CW/(VC + CZ) = CW/(CU + CS) = CW/(CU + BU) = CW/BC. Now consider the triangle PSC. The line BRW cuts PS at R, CP at W and SC at B, so by Menelaus' theorem, we have (SR/RP) (PW/WC) (CB/SB) = 1. But SB = CU = CV = PW, so this gives SR/RP = CW/BC = PQ/QS. Hence PQ = RS.
Problem A3 Non-negative reals x, y, z satisfy x2 + y2 + z2 + xyz = 4. Show that xyz ≤ xy + yz + zx ≤ xyz + 2. Solution Assume x ≥ y ≥ z. If z > 1, then x2 + y2 + z2 + xyz > 1 + 1 + 1 + 1 = 4. Contradiction. So z ≤ 1. Hence xy + yz + zx ≥ xy ≥ xyz. Put x = u + v, y = u - v, so that u, v ≥ 0. Then the equation given becomes u2(2 + z) + (2 - z)v2 + z2 = 4. So we we keep z fixed and reduce v to nil, then we must increase u. But xy + yz + zx - xyz = (u2 - v2)(1 - z) + 2zu, so decreasing v and increasing u has the effect of increasing xy + yz + zx - xyz. Hence xy + yz + zx - xyz takes its maximum value when x = y. But if x = y, then the equation gives x = y = √(2 - z). So to establish that xy + yz + zx - xyz ≤ 2 it is sufficient to show that 2 - z + 2z√(2 - z) ≤ 2 + z(2 - z). Evidently we have equality if z = 0. If z is non-zero, then the relation is equivalent to 2√(2 - z) ≤ 3 - z or (z - 1)2 ≥ 0. Hence the relation is true and we have equality only for z = 0 or 1.
Problem B1 ABC is a triangle and X is a point in the same plane. The three lengths XA, XB, XC can be used to form an obtuse-angled triangle. Show that if XA is the longest length, then angle BAC is acute. Solution Suppose first that ∠BAC = 90o. We may choose coordinates so that A is (-a, -b), B is (-a, b) and C is (a, -b). Let X be (x, y). We have that XB2 + XC2 - XA2 = (x + a)2 + (y - b)2 + (x - a)2 + (y + b)2 - (x + a)2 - (y + b)2 = (x - a)2 + (y - b)2 ≥ 0. So in this case the lengths XA, XB, XC cannot form an obtuse-angled triangle. Now suppose BAC is obtuse. Let A' be the foot of the perpendicular from C to the line AB. We show that if X is situated so that XA is the longest length, then XA < XA'. But since BA'C is right-angled, we have just shown that XB2 + XC2 ≥ XA2 and hence XB2 + XC2 ≥ XA'2, showing that the lengths XA, XB, XC form an acute-angled triangle. This is almost obvious from a diagram. Let L, M, N be the midpoints of BC, CA, AB. Let N' be the midpoint of A'B. Let the perpendiculars through M, N meet at O. Take P on the line MO on the opposite side of O to M, and Q on the line NO on the opposite side of O to N. So for XA to be the longest length, X must lie on the same side of the line MP as C (for XA ≥ XC) and on the same side of the line NQ as B (for XA ≥ XB). So it must lie in the region bounded by the rays OP and OQ. We now find the similar region for A'BC. The perpendicular bisector of A'C is just the line ML. Take P' on this line on the opposite side of L to M. The perpendicular bisector of AB meets AB at a point N' (say) which must lie on the segment AN. It also passes through L. Take a point Q' on this line on the opposite side of L to N'. Then for XA' ≥ XB, XC we require X to lie in the sector bounded by the lines LP' and LQ'. But the sector bounded by OP and OQ lies entirely inside this sector. [This is obvious from a diagram, but LQ' is parallel to OQ and lies between it and C. OP and LP' both pass through M and OP cuts BC at a point between L and C.] Also the region between LP' and LQ' lies on the same side of the perpendicular bisector of AA' (which is parallel to LQ') as A. So any point in the region is closer to A than A'. This gives us all we need. If XA ≥ XB and XC, then it lies in the region bounded by OP and OQ. Hence it also lies in the region bounded by LP' and LQ', so XA'2 ≤ XB2 + XC2. Since also XA < XA', we have XA2 < XB2 + XC2 and hence XA, XB, XC form an obtuse-angled triangle.
Problem B2 A set of integers is such that if a and b belong to it, then so do a2 - a, and a2 - b. Also, there are two members a, b whose greatest common divisor is 1 and such that a - 2 and b - 2 also have greatest common divisor 1. Show that the set contains all the integers. Solution Suppose 1 belongs to the set. Then so does 0 = 12 - 1.We have 02 - 1 = -1, 12 - (-1) = 2, 22 - 1 = 3, 22 - 0 = 4, 22 - (-1) = 5. Now given that we have every integer up to k2 we can get the integers from k2 + 1 to (k + 1)2 using (k + 1)2 - h for h = 0, 1, ... , 2k (assuming that k ≥ 2). Hence we can get all positive integers. Now to get any negative integer -k just take 02 - k. Now if a, b, c belong to the set, then so do (a2 - b2) + c = a2 - (b2 - c) and -(a2 - b2) + c. So by induction n(a2 - b2) + c belongs for any integer n. Put A = a2 - b2. Now if a' and b' are two other numbers in the set, put B = a'2 - b'2. Then mA + nB + c belongs to the set for all integers m and n. If we could find A and B which were relatively prime, then we would be home, because we could find m, n for which mA + nB = 1 and hence we could find m, n for which mA + nB = -(c - 1), so that mA + nB + c = 1. It is not obvious how to find such A, B. But we can find A, B, C such that the greatest common divisor is 1 and that is sufficient. Let A = a2 - b2, where a, b are the two given numbers. Let B = a3(a - 2) and let C = b3(b - 2). Since a is in the set so is a2 - a and B = (a2 - a)2 - a2. Similarly C. So certainly all numbers mA + nB + rC + a are in the set for any integers m, n, r. If a prime p divides B, then it must divide a or a - 2. If it also divides A, then it cannot divide a, for then it would also divide b2 and hence b, but we are told that a and b have no common factor. So any prime dividing all of A, B and C must divide a - 2. Similarly, it must divide b - 2. But we are told that a - 2 and b - 2 have no common factor. Hence A, B, C have no common factor. So we can find m, n, r such that mA + nB + rC = 1, and hence m, n, r such that mA + nB + rC = -(a - 1) and hence such that mA + nB + rC + a = 1.
Problem B3 Every point in the plane is assigned a real number, so that for any three points which are not collinear, the number assigned to the incenter is the mean of the numbers assigned to the three points. Show that the same number is assigned to every point. Solution Let f(P) be the number assigned to any point P. Let P, Q be any points. Take R on the segment PQ. Its position will be determined later. Take AA' perpendicular to PQ with R its midpoint. Take a rectangle ACFA' on the opposite side of AA' to P and AA'/AC = 3/2. Let B be the midpoint of AC and B' the midpoint of A'F. Take equally spaced points D, E on CF, so that AB = BC = CD = DE = EF = FB' = B'A'. Finally take X on the ray RP. We will choose the lengths XP and RA so that P is the incenter of XAA' and Q is the incenter of XBB'. The incircles of ACD and BCE coincide, so f(A) + f(D) = f(B) + f(E). Hence f(D) - f(E) = f(B) - f(A). Similarly, the incircles of A'EF and B'DF coincide, so f(D) - f(E) = f(A') - f(B'). Hence f(A) + f(A') = f(B) + f(B'). Hence f(P) = ( f(A) + f(A') + f(X) )/3 = ( f(B) + f(B') + f(X) )/3 = f(Q). That is all we need, since it shows that the same number is assigned to two arbitrary points. So it remains to show that XP and RA can be chosen as claimed. The incenter of an isosceles triangle base 2a and height h is ah/(a + √(a2+h2) above the base (if the distance is x, then by similar triangles x/(h-x) = a/√(a2+h2) ). So if we take XR/RA = 3/2 and RA/PR = (1 + √5)/2 then P is the incenter of XAA'.
Labels:
USAMO
Previous Article
