29th USA Mathematical Olympiad 2000 Problems
A1. Show that there is no real-valued function f on the reals such that ( f(x) + f(y) )/2 ≥ f( (x+y)/2 ) + |x - y| for all x, y.
A2. The incircle of the triangle ABC touches BC, CA, AB at D, E, F respectively. We have AF ≤ BD ≤ CE, the inradius is r and we have 2/AF + 5/BD + 5/CE = 6/r. Show that ABC is isosceles and find the lengths of its sides if r = 4.
A3. A player starts with A blue cards, B red cards and C white cards. He scores points as he plays each card. If he plays a blue card, his score is the number of white cards remaining in his hand. If he plays a red card it is three times the number of blue cards remaining in his hand. If he plays a white card, it is twice the number of red cards remaining in his hand. What is the lowest possible score as a function of A, B and C and how many different ways can it be achieved?
B1. How many squares of a 1000 x 1000 chessboard can be chosen, so that we cannot find three chosen squares with two in the same row and two in the same column?
B2. ABC is a triangle. C1 is a circle through A and B. We can find circle C2 through B and C touching C1, circle C3 through C and A touching C2, circle C4 through A and B touching C3 and so on. Show that C7 is the same as C1.
B3. x1, x2, ... , xn, and y1, y2, ... , yn are non-negative reals. Show that ∑ min(xixj, yiyj) ≤ ∑ min(xiyj, xjyi), where each sum is taken over all n2 pairs (i, j).
Solution
29th USA Mathematical Olympiad 2000
Problem A1
Show that there is no real-valued function f on the reals such that ( f(x) + f(y) )/2 ≥ f( (x+y)/2 ) + |x - y| for all x, y.
Solution
Put x = a + b, y = a - b with b > 0. Then we have f(a) ≤ 1/2 f(a+b) + 1/2 f(a-b) - 2b. Also f(a + b/2) ≤ 1/2 f(a) + 1/2 f(a+b) - b, f(a - b/2) ≤ 1/2 f(a-b) + 1/2 f(a) - b, and f(a) ≤ 1/2 f(a - b/2) + 1/2 f(a + b/2) - b ≤ 1/4 f(a-b) + 1/2 f(a) + 1/4 f(a+b) - 2b. Hence f(a) ≤ 1/2 f(a-b) + 1/2 f(a+b) - 4b. But a and b are arbitrary (apart from b > 0) so this argument can now be repeated to show that f(a) ≤ 1/2 f(a-b) + 1/2 f(a+b) + 2nb for any positive integer n. Contradiction. Problem A2
The incircle of the triangle ABC touches BC, CA, AB at D, E, F respectively. We have AF ≤ BD ≤ CE, the inradius is r and we have 2/AF + 5/BD + 5/CE = 6/r. Show that ABC is isosceles and find the lengths of its sides if r = 4.
Solution
Answer: sides 24, 15, 15. AF = 3, BD = CE = 12.
Let the incenter be I. The triangle AFI has ∠AFI = 90o, ∠FAI = A/2, and FI = r. So r/AF = tan A/2. Similarly, r/BD = tan B/2, r/CE = tan C/2. So the given relation is 2 tan A/2 + 5 tan B/2 + 5 tan C/2 = 6. We have A/2 = 90o - (B/2 + C/2), so we can eliminate A/2, using tan A/2 = cot(B/2 + C/2) = (1 - tan B/2 tan C/2)/(tan B/2 + tan C/2). Hence 5 tan2B/2 + 5 tan2C/2 + 8 tan B/2 tan C/2 - 6 tan B/2 - 6 tan C/2 + 2 = 0 (*).
It is not immediately clear where we go from here. But we are asked to prove that ABC is isosceles. Since the given relation is symmetrical in B and C, presumably AB = AC and angle B = angle C, in which case (*) reduces to (3 tan B/2 - 1)2 = 0. So our goal must be to show that 3 tan B/2 - 1 = 3 tan C/2 - 1 = 0. If we use 3 tan B/2 - 1 and 3 tan C/2 - 1 as variables, we have (3 tan B/2 - 1)2 = 9 tan2B/2 - 6 tan B/2 + 1, (3 tan C/2 - 1)2 = 9 tan2C/2 - 6 tan C/2 + 1, (3 tan B/2 - 1)(3 tan C/2 - 1) = 9 tan B/2 tan C/2 - 3 tan B/2 - 3 tan C/2 + 1. Comparing to (*), we see that it can be written as 5 (3 tan B/2 - 1)2 + 5 (3 tan C/2 - 1)2 + 8(3 tan B/2 - 1)(3 tan C/2 - 1) = 0. But 82 < 4·5·5, so this implies 3 tan B/2 - 1 = 3 tan C/2 - 1 = 0. So tan A/2 = 4/3 and we have found all the angles in the triangle. We have AF = r cot A/2 = 3, BD = CE = r cot B/2 = 12. So the triangle has sides 3 + 12 = 15, 3 + 12 = 15 and 12 + 12 = 24.
A player starts with A blue cards, B red cards and C white cards. He scores points as he plays each card. If he plays a blue card, his score is the number of white cards remaining in his hand. If he plays a red card it is three times the number of blue cards remaining in his hand. If he plays a white card, it is twice the number of red cards remaining in his hand. What is the lowest possible score as a function of A, B and C and how many different ways can it be achieved?
Solution
Answer: the lowest score is min(AC, 2BC, 3AB). If the maximum of B, A/2, C/3 is unique, then there is only one way to achieve the lowest score. If B = A/2 > C/3, there are C+1 ways; if B = C/3 > A/2, there are A+1 ways; if A/2 = C/3 > B, there are B+1 ways. If B = A/2 = C/3, then there are A+B+C ways.
Solution by Ralph Furmaniak, which is significantly simpler than my original solution
If A = 0, then the unique solution is to play all the red cards followed by all the white cards (total score nil). Similarly, if B = 0, the unique solution is to play all the white cards followed by all the blue cards, and if C = 0, the unique solution is to play all the blue cards followed by all the red cards. So assume A, B, C are all non-zero.
It is never correct to play a red card immediately before a blue card, because the score would be reduced by 3 if the order was reversed. Similarly, it is never correct to play a white card immediately before a red card, or a blue card immediately before a white card. Hence the optimum play must be either (1) BRWBRWB ... or (2) RWBRWB ... or (3) WBRWB ... , where B denotes the play of one or more blue cards, R denotes the play of one or more red cards and W denotes the play of one or more white cards.
Suppose the optimum involves two or more separate plays of blue cards, so we have ... b, r, w, b' , ... meaning that the sequence includes the plays b blue cards, followed by r red cards, followed by w white cards, followed by b' blue cards. Then the score for ... (b-1), r, w, (b'+1), ... is (w-3r) lower. That is independent of b. So if w is not equal to 3r, then the sequence cannot be optimal, because either ... (b+b'), r, w, ... or ... r, w, (b+b'), ... gives a lower score. If w = 3r, then both ... (b+b'), r, w, ... and ... r, w, (b+b'), ... are also optimal. But that implies that the original sequence cannot have had any more terms, it must have been simply b, r, w, b', otherwise one of ... (b+b'), r, w, ... or ... r, w, (b+b'), ... would involve playing a white card immediately before a red, which is never optimal.
A similar argument applies to two or more separate plays of red cards and to two or more separate plays of white cards. So one of BRW, RWB, WBR is always optimal. They give scores of AC, 3AB, 2BC respectively, so the minimum score is min(AC, 3AB, 2BC).
The argument above also shows that if a play sequence is optimal, then it must be one of the three above or BRWB, RWBR or WBRW. Also BRWB can only be optimal if C = 3B. Similarly, RWBR can only be optimal if 3A = 2C and WBRW can only be optimal if 2B = A.
If BRW, RWB and WBR are all optimal, then A = B/2 = C/3. In this case, BRWB, RWBR and WBRW are also optimal. There are A possibilities for BRW or BRWB (start with 1, 2, 3, ... or A blue cards, then play all the red, then all the white, then any remaining blue). Similarly, there are B possibilities for RWB and RWBR and C for WBR and WBRW, so A+B+C possibilities in total. So assume BRW, RWB and WBR are not all optimal.
If BRWB is optimal, then BRW and RWB must also be optimal, so A/2 < B = C/3. So there are A+1 possibilities (start with 0, 1, 2, ... or A blue cards, then all the red, then all the white, then any remaining blue).
Similarly, if RWBR is optimal, then B < A/2 = C/3. There are B+1 possibilities (start with 0, 1, 2, ... or B red cards, then all the white, then all the blue, then any remaining red). Similarly, if WBRW is optimal, then C/3 < B = A/2 and there are C+1 possibilities (start with 0, 1, 2, ... or C white cards, then all the blue, then all the red, then any remaining white).
If none of BRWB, RWBR, WBRW are optimal, then B, A/2 and C/3 are all unequal and the solution is unique.
How many squares of a 1000 x 1000 chessboard can be chosen, so that we cannot find three chosen squares with two in the same row and two in the same column?
Solution
Answer: 1998. Choose every square in the first row or column but not both.
We prove the slightly more general result that the maximum number for an m x n rectangle is n if m = 1, or m + n - 2 for m, n > 1.
We may assume m ≤ n. We use induction on m. The result for m = 1 is obvious. For m = 2, if we choose two in the same row, then we cannot choose any more, so it is better (or no worse for n = 2) to choose all the squares in a column giving n = m + n - 2 in total. That establishes the result for m = 1 and 2.
Now suppose n ≥ m > 2 and that the result is true for smaller m. We can certainly do at least m + n - 2 by choosing all the squares in the first row or column but not both. Assume we have m columns. If no two are in the same row, then there are at most n which we know is not optimal. So assume there are two in the same row. Now there cannot be any more in the two corresponding columns. So consider the remaining m-2 columns. If m > 3, then by induction we cannot choose more than m-2 + n - 2 in those columns and with the two already chosen that gives m + n - 2. If m = 3, then we cannot choose more than n in the remaining column. But we can combine at most n-1 of those with the existing two, since if we pick the square in the same row as the two squares already chosen, then we cannot choose any others. So for this case also we can do at most n+1 = m + n - 2. Hence the result is true for all m.
ABC is a triangle. C1 is a circle through A and B. We can find circle C2 through B and C touching C1, circle C3 through C and A touching C2, circle C4 through A and B touching C3 and so on. Show that C7 is the same as C1.
Solution
Let Oi be the center of Ci. Evidently Oi lies on the perpendicular bisector of the relevant side. Since C1 and C2 touch, O1, B and O2 must be collinear. Let M be the midpoint of AB. Let ∠MO1A = x1. Define xi similarly. Since O1, B and O2 are collinear, we have (90o - x1) + B + (90o - x2) = 180o. So B = x1 + x2. Similarly, x2 + x3 = C, x3 + x4 + A, x4 + x5 = B, x5 + x6 = C, x6 + x7 = A. Hence (x1 + x2) + (x3 + x4) + (x5 + x6) = A + B + C = (x2 + x3) + (x4 + x5) + (x6 + x7). So x1 = x7. Hence O1 = O7.
x1, x2, ... , xn, and y1, y2, ... , yn are non-negative reals. Show that ∑ min(xixj, yiyj) ≤ ∑ min(xiyj, xjyi), where each sum is taken over all n2 pairs (i, j).
Solution
Let f(x1, y1, x2, y2, ... , xn, yn) = S ( min(xiyj, xjyi) - min(xixj, yiyj) ). So we have to show that f(x1, y1, ... , xn, yn) ≥ 0. We use induction on n. There is nothing to prove for n = 1. Suppose the result is true for all positive integers < n.
If any xi or yi is zero, or if any xi = yi, then the result follows immediately from that for n-1. Suppose x1/y1 = x2/y2. We claim that f(x1, ... , yn) = f(x1+x2, y1+y2, x3, y3, ... , xn, yn). Note that the rhs has one less pair of terms. For convenience we write x1 = k y1, so x2 = k y2. The sum of the (1, i) and (2, i) terms on the lhs is min( x1yi, y1xi) + min( x2yi, y2xi) - min( x1xi, y1yi) - min( x2xi, y2yi) = (y1 + y2) min(kyi, xi) - (y1 + y2) min(kxi, yi). The corresponding (1+2, i) term on the rhs is min( (x1+x2)yi, (y1+y2)xi) - min( (x1+x2)xi, (y1+y2)yi) = (y1+y2) min(kyi, xi) - (y1+y2) min(kxi, yi), which is the same. Similarly for the (i, 1) + (i, 2) versus (i, 1+2) terms. The (i, j) terms (with i, j > 2) are obviously unchanged. So we just have to consider the various 1, 2 terms. On the lhs there are four of them: the (1, 1), (1, 2) = (2, 1) and the (2, 2) terms. Their sum is x1y1 - min(x12, y12) + x2y2 - min(x22, y22) + 2min(x1y2, x2y1) - 2min(x1x2, y1y2) = ky12 - y12min(k2, 1) + ky22 - y22min(k2, 1) + 2ky1y2 - 2y1y2min(1,k2) = (y1+y2)2(k - min(1,k2) ). On the rhs there is just the one term (x1+x2)(y1+y2) - min( (x1+x2)2, (y1+y2)2) = k(y1+y2)2 - (y1+y2)2min(k2, 1), which is the same. So we have established the claim. Thus if we have any distinct i, j such that xi/yi = xj/yj, then the result for n follows from that for n-1.
We now show that the same is true if we have xi/yi = yj/xj. Assume for convenience that x1/y1 = y2/x2. We can also assume without loss of generality that x1 ≤ y2. So we can take x2 = ky1, y2 = k x1 with k ≥ 1. Then we claim that f(x1, ... , yn) = f(x2 - y1, y2 - x1, x3, y3, ... , xn, yn). Again, the rhs has one less pair of terms than the lhs. On the lhs the sum of the (1, i) and (2, i) terms on the lhs is min( x1yi, y1xi) + min( x2yi, y2xi) - min( x1xi, y1yi) - min( x2xi, y2yi) = (k-1) min(x1xi, y1yi) - (k-1) min(x1yi, y1xi) . The corresponding (1+2, i) term on the rhs is min( (x2-y1)yi, (y2-x1)xi) - min( (x2-y1)xi, (y2-x1)yi) = (k-1) min(y1yi, x1xi) - (k-1) min(y1xi, x1yi), which is the same. Similarly, the 1, 2 terms on the lhs are x1y1 - min(x12, y12) + x2y2 - min(x22, y22) + 2min(x1y2, x2y1) - 2min(x1x2, y1y2) = x1y1 - min(x12, y12) + k2x1y1 - k2min(x12, y12) + 2k min(x12, y12) - 2kx1y1 = (1 - k)2x1y1 - (1 - k)2min(x12, y12). On the rhs we have (x2 - y1)(y2 - x1) - min( (x2 - y1)2, (y2 - x1)2) = (k - 1)2x1y1 - (k - 1)2min(y12, x12), which is the same. Again the terms not involving 1 or 2 are the same on both sides. So we have shown that if we have any distinct i, j such that xi/yi = yj/xj then the result for n follows from that for n-1.
Put ri = max(xi/yi, yi/xi). Reordering the pairs, if necessary, we can take 1 ≤ r1 ≤ r2 ≤ ... ≤ rn. Now let us consider all the xi, yi as fixed except y1. For convenience, let us write t = y1. We have 1 ≤ r1 ≤ r2, so t can take any value in the interval [x1, x1r2] or any value in the interval [x1/r2, x1]. We examine f on each of these intervals. Since only t is varying, the only terms in f which vary are the (1, 1), (1, i) and (i, 1) terms. Writing their sum as g(t), we have g(t) = x1t - min(x12, t2) + 2 ∑ min(x1yi, t xi) - 2 ∑ min(x1xi, t yi). Now if xi ≥ yi, then xi/yi = ri ≥ r2 ≥ t/x1, so x1xi ≥ t yi. Also t xi ≥ x1xi ≥ x1yi, so min(x1yi, t xi) = x1yi, and min(x1xi, t yi) = t yi. So if we put zi = - yi, then these two terms in g(t) give 2(t - x1) zi. Similarly, if xi < yi, then x1yi ≥ t xi and t yi ≥ x1xi, so if we put zi = xi, then the two terms in g(t) still give 2(t - x1) zi. Thus g(t) = x1t - x12 + 2(t - x1) ∑ zi, which is linear in t. But a linear function takes its minimum value in an interval at one of the endpoints, so the minimum value of g(t) (and hence of f as t varies) must occur at t = x1 or x1r2. But then we have r1 = 1 or r2 and in both those cases we have established that the value of f equals the value of f for n-1 pairs and is therefore non-negative.
Now suppose t is in the other interval [x1/r2, x1]. Again, we put g(t) equal to the sum of the variable terms. So g(t) = x1t - min(x12, t2) + 2 ∑ min(x1yi, t xi) - 2 ∑ min(x1xi, t yi). Again, we consider separately the case xi ≥ yi which gives a pair of terms with sum 2(x1 - t)zi if we put zi = yi, whilst if xi < yi, then the pair of terms has the sum 2(x1 - t)zi if we put zi = -xi. So we get g(t) = x1t - t2 + 2(x1 - t) ∑ zi. This time we have a quadratic. But the leading term - t2 has a negative coefficient, so g(t) has a single maximum as t varies over all real values. Thus it is again true that the minimum value over the interval [x1/r2, x1] must occur at one of the endpoints. So again the minimum value of f as t varies over the allowed range is at r1 = r2 or 1 and is hence non-negative by induction.
So the induction is complete and the result established.
Comment. No one made any headway with this in the USAMO exam. As an olympiad problem, it is exceptionally (and unreasonably) difficult.
Labels:
USAMO
Previous Article
