31th USA Mathematical Olympiad 2002 Problems
A1. Let S be a set with 2002 elements and P the set of all its subsets. Prove that for any n (in the range from zero to |P|) we can color n elements of P white, and the rest black, so that the union of any two elements of P with the same color has the same color.
A2. The triangle ABC satisfies the relation cot2A/2 + 4 cot2B/2 + 9 cot2C/2 = 9(a+b+c)2/(49r2), where r is the radius of the incircle (and a = |BC| etc, as usual). Show that ABC is similar to a triangle whose sides are integers and find the smallest set of such integers.
A3. p(x) is a polynomial of degree n with real coefficients and leading coefficient 1. Show that we can find two polynomials q(x) and r(x) which both have degree n, all roots real and leading coefficient 1, such that p(x) = q(x)/2 + r(x)/2.
B1. Find all real-valued functions f on the reals such that f(x2 - y2) = x f(x) - y f(y) for all x, y.
B2. Show that we can link any two integers m, n greater than 2 by a chain of positive integers m = a1, a2, ... , ak+1 = n, so that the product of any two consecutive members of the chain is divisible by their sum. [For example, 7, 42, 21, 28, 70, 30, 6, 3 links 7 and 3.]
B3. A tromino is a 1 x 3 rectangle. Trominoes are placed on an n x n board. Each tromino must line up with the squares on the board, so that it covers exactly three squares. Let f(n) be the smallest number of trominoes required to stop any more being placed. Show that for all n > 0, n2/7 + hn ≤ f(n) ≤ n2/5 + kn for some reals h and k.
Solution
31th USA Mathematical Olympiad 2002
Problem A1
Let S be a set with 2002 elements and P the set of all its subsets. Prove that for any n (in the range from zero to |P|) we can color n elements of P white, and the rest black, so that the union of any two elements of P with the same color has the same color.
Solution
Let S have m elements and P be the set of its subsets. We show by induction on m that a coloring is possible for any n ≤ |P|. If m = 1, we color both subsets black for n = 0, the empty set white (and the other subset black) for n = 1, and both subsets white for n = 2. Suppose now that a coloring is possible for m (and any n). Consider a set S with m+1 elements. Let b be any element of S. For n ≤ 2m, use induction to color just n subsets of S - {b} white and color black all subsets of S which include b. Then the union of two white subsets is still a subset of S - {b} and hence (by assumption) white. The union of two black subsets of S - {b} is black for the same reason. If one black subset includes b, then so does the union, which must therefore be black. For n > 2m, we have 2m+1 - n < 2m, so we can find a coloring for 2m+1 - n and then swap the colors. Problem A2
The triangle ABC satisfies the relation cot2A/2 + 4 cot2B/2 + 9 cot2C/2 = 9(a+b+c)2/(49r2), where r is the radius of the incircle (and a = |BC| etc, as usual). Show that ABC is similar to a triangle whose sides are integers and find the smallest set of such integers.
Solution
Answer: a =13, b = 40, c = 45.
Let the incenter be I. Consider the triangle IBC. It has angle IBC = B/2, angle ICB = C/2 and height r. Hence a = r cot B/2 + r cot C/2. With the two similar relations for the other sides, that gives 2r cot A/2 = (b + c - a), 2r cot B/2 = (c + a - b), 2r cot C/2 = (a + b - c). So the given relation becomes: 49( (b + c - a)2 + 4(c + a - b)2 + 9(a + b - c)2) = 36(a + b + c)2.
Multiplying out is a mistake. It leads nowhere. It is more helpful to change variable to d = b + c - a, e = c + a - b, f = a + b - c giving 49(d2 + 4e2 + 9f2) = 36(d + e + f)2, or 13d2 + 160e2 + 405f2 - 72(de + ef + fd) = 0. We would like to express this as (hd + ke)2 + (h'e + k'f)2 + (h''f + k''d)2 = 0. Presumably 13 = 32 + 22. Then 72 = 2·3·something and 2·2·something, giving 12 and 18. Squares 144, 324. Fortunately, we see that 160 = 122+ 42, 405 = 182 + 92 and 2·4·9 = 72. So putting that together we get: (2d - 18f)2 + (3d - 12e)2 + (4e - 9f)2 = 0.
So we conclude that b + c - a = 9(a + b - c) = 4(c + a - b), or 5a + 4b = 5c, 5a + 3c = 5b, or a = 13k, b = 40k, c = 45k. We get the smallest triangle with integer sides by taking k = 1.
p(x) is a polynomial of degree n with real coefficients and leading coefficient 1. Show that we can find two polynomials q(x) and r(x) which both have degree n, all roots real and leading coefficient 1, such that p(x) = q(x)/2 + r(x)/2.
Solution
The easiest way to show that a polynomial has a root between a and b is to show that it changes sign. So the idea is to take some polynomial that obviously changes sign n times. Then if we take k s(x) and -k s(x) + 2p(x), for sufficiently large k the sign of -k s(x) + 2p(x) should be dominated by s(x). That does not quite deal with the leading coefficient. But we know that ultimately the leading term dominates, so something like k s(x) + xn and -k s(x) - xn + 2p(x) ought to work.
Specifically, put s(x) = (1 - x)(2 - x)(3 - x) ... (n-1 - x). It is zero at x = 1, 2, 3, ... , n-1. It is alternately positive and negative at x = 1/2, 1 1/2, ... , n - 1/2. Suppose n is even. Let M = nn so that xn < M on the interval [0, n]. Clearly, if we take k sufficiently large (in relation to M), then k s(x) + xn has the same sign as s(x) at x = 1/2, 1 1/2, ... , n - 1/2. In particular, it is negative at x = n - 1/2, but, whatever k, if x is sufficiently large k s(x) + xn is positive. So k s(x) + xn changes sign at least n times and hence has n real roots.
Similarly, for k sufficiently large (in relation to M and the max value of 2p(x) over the interval [0, n] ), -k s(x) - xn + 2p(x) will have the opposite sign to s(x) at x = 1/2, 1 1/2, ... , n - 1/2 and in particular will be negative at x = 1/2. But the leading term in - k s(x) - xn + 2p(x) is xn and n is even, so for x sufficiently negative, the sign will be positive. Thus - k s(x) - xn + 2p(x) also changes sign at least n times and hence has n real roots.
Exactly similar arguments work for n odd. We get n-1 sign changes from the k s(x) term and one extra for x large and positive or large and negative (this time k s(x) has the same sign at x = 1/2 and x = n - 1/2, but xn has different signs for large positive and large negative).
Find all real-valued functions f on the reals such that f(x2 - y2) = x f(x) - y f(y) for all x, y.
Solution
Answer: f(x) = kx for some real k.
Putting y = 0, f(x2) = x f(x). Hence f(x2 - y2) = f(x2) - f(y2). So for any non-negative x, y, we have f(x - y) = f(x) - f(y). Hence also f(x) = f(x + y - y) = f(x + y) - f(y), so f(x + y) = f(x) + f(y) for non-negative x, y. Also f(0) = f(02) = 0 f(0) = 0, and for non-negative y, f(-y) = f(0 - y) = f(0) - f(y) = -f(y). Hence also f(-y) = -f(y) for negative y. So we have f(x + y) = f(x) + f(y) for non-negative x and any y. But now if x is negative, f(x + y) = -f(-x - y) = - (f(-x) - f(y) ) = f(x) + f(y). So f(x + y) = f(x) + f(y) for all x and y.
Now for any x we have f(x) + f(x - 1) = f(2x - 1) = f( x2 - (x - 1)2) = x f(x) - (x - 1) f(x - 1) = x f(x - 1) + x f(1) - (x - 1) f(x - 1) = x f(1) + f(x - 1), so f(x) = x f(1). So if f(1) = k, then f(x) = kx. It is trivial to check that this does indeed satsify the equation given for any k.
Show that we can link any two integers m, n greater than 2 by a chain of positive integers m = a1, a2, ... , ak+1 = n, so that the product of any two consecutive members of the chain is divisible by their sum. [For example, 7, 42, 21, 28, 70, 30, 6, 3 links 7 and 3.]
Solution
We write a ↔ b if (a + b) divides ab. The starting point is that for n > 1 we have n ↔ n(n - 1). As slight variants we also have 2n ↔ n(n - 2) for n > 2, and in any case where a ↔ b, then also ma ↔ mb (for m > 0). That allows us to link n > 2 and 2n, thus: n ↔ n(n - 1) ↔ n(n - 1)(n - 2) = n(n - 2) ↔ 2n.
To go much further we need some inspiration. Note that n(n - 3) + 2 = (n - 1)(n - 2). So 2(n - 1)(n - 2) ↔ n(n - 3)(n - 1)(n - 2). That is critical, for it is a general way of allowing us to reduce the largest factor. Thus for n > 3, n ↔ n(n - 1) ↔ n(n - 1)(n - 2) ↔ n(n - 1)(n - 2)(n - 3) ↔ 2(n - 1)(n - 2) ↔ (n - 1)(n - 2) ↔ n - 1. But linking n and n-1 obviously allows us to link any two integers > 3. That leaves 3 itself, but the question already shows how to link that to at least one integer > 3, which is all we need.
A tromino is a 1 x 3 rectangle. Trominoes are placed on an n x n board. Each tromino must line up with the squares on the board, so that it covers exactly three squares. Let f(n) be the smallest number of trominoes required to stop any more being placed. Show that for all n > 0, n2/7 + hn ≤ f(n) ≤ n2/5 + kn for some reals h and k.
Solution
A tromino may be placed in n - 2 positions in each row and column, so there are 2n2 - 4n possible positions in total. Placing a tromino occupies or blocks at most 14 of these positions (5 parallel and 9 perpendicular). Hence any placement of (2n2 - 4n)/14 = n2/7 - 2n/7 trominoes will block further trominoes. So f(n) >= n2/7 - 2n/7.
If we place trominoes roughly like this:
x x x o o x x x o o x x x o o x x x o o x
o x x x o o x x x o o x x x o o x x x o o
o o x x x o o x x x o o x x x o o x x x o
x o o x x x o o x x x o o x x x o o x x x
x x o o x x x o o x x x o o x x x o o x x
x x x o o x x x o o x x x o o x x x o o x
it is obvious that no further trominoes are possible and the number of occupied squares is about 3n2/5. Hence the number of trominoes is about n2/5. But we need to do some tidying up in relation to edge effects. The safe way to deal with partial trominoes at the beginning or end of rows is to pull them completely onto the board. Each complete group of five cells in a row needs a tromino, but we may need one extra at the start and one extra at the end. So [n/5] + 2 will always suffice for the row. Thus n2/5 + 2n will suffice for the board and so f(n) ≤ n2/5 + 2n.
Labels:
USAMO
Previous Article
