31th USA Mathematical Olympiad 2002 Problems

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 cot²A/2 + 4 cot²B/2 + 9 cot²C/2 = 9(a+b+c)²/(49r²), 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(x² - y²) = 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 = a₁, a₂, ... , a_k+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, n²/7 + hn ≤ f(n) ≤ n²/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 ≤ 2^m, 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 > 2^m, we have 2^m+1 - n < 2^m, so we can find a coloring for 2^m+1 - n and then swap the colors. Problem A2

The triangle ABC satisfies the relation cot²A/2 + 4 cot²B/2 + 9 cot²C/2 = 9(a+b+c)²/(49r²), 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)² + 4(c + a - b)² + 9(a + b - c)²) = 36(a + b + c)².

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(d² + 4e² + 9f²) = 36(d + e + f)², or 13d² + 160e² + 405f² - 72(de + ef + fd) = 0. We would like to express this as (hd + ke)² + (h'e + k'f)² + (h''f + k''d)² = 0. Presumably 13 = 3² + 2². Then 72 = 2·3·something and 2·2·something, giving 12 and 18. Squares 144, 324. Fortunately, we see that 160 = 12²+ 4², 405 = 18² + 9² and 2·4·9 = 72. So putting that together we get: (2d - 18f)² + (3d - 12e)² + (4e - 9f)² = 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.

---

Problem 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.

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) + xⁿ and -k s(x) - xⁿ + 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 = nⁿ so that xⁿ < M on the interval [0, n]. Clearly, if we take k sufficiently large (in relation to M), then k s(x) + xⁿ 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) + xⁿ is positive. So k s(x) + xⁿ 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) - xⁿ + 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) - xⁿ + 2p(x) is xⁿ and n is even, so for x sufficiently negative, the sign will be positive. Thus - k s(x) - xⁿ + 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 xⁿ has different signs for large positive and large negative).

---

Problem B1

Find all real-valued functions f on the reals such that f(x² - y²) = x f(x) - y f(y) for all x, y.

Solution

Answer: f(x) = kx for some real k.

Putting y = 0, f(x²) = x f(x). Hence f(x² - y²) = f(x²) - f(y²). 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(0²) = 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( x² - (x - 1)²) = 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.

---

Problem B2

Show that we can link any two integers m, n greater than 2 by a chain of positive integers m = a₁, a₂, ... , a_k+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.

---

Problem 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, n²/7 + hn ≤ f(n) ≤ n²/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 2n² - 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 (2n² - 4n)/14 = n²/7 - 2n/7 trominoes will block further trominoes. So f(n) >= n²/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 3n²/5. Hence the number of trominoes is about n²/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 n²/5 + 2n will suffice for the board and so f(n) ≤ n²/5 + 2n.

[Read More...]

30th USA Mathematical Olympiad 2001 Problems

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 x² + y² + z² + 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 a² - a, and a² - 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 x² + y² + z² + xyz = 4. Show that xyz ≤ xy + yz + zx ≤ xyz + 2. Solution Assume x ≥ y ≥ z. If z > 1, then x² + y² + z² + 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 u²(2 + z) + (2 - z)v² + z² = 4. So we we keep z fixed and reduce v to nil, then we must increase u. But xy + yz + zx - xyz = (u² - v²)(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)² ≥ 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 = 90^o. 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 XB² + XC² - XA² = (x + a)² + (y - b)² + (x - a)² + (y + b)² - (x + a)² - (y + b)² = (x - a)² + (y - b)² ≥ 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 XB² + XC² ≥ XA² and hence XB² + XC² ≥ XA'², 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'² ≤ XB² + XC². Since also XA < XA', we have XA² < XB² + XC² 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 a² - a, and a² - 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 = 1² - 1.We have 0² - 1 = -1, 1² - (-1) = 2, 2² - 1 = 3, 2² - 0 = 4, 2² - (-1) = 5. Now given that we have every integer up to k² we can get the integers from k² + 1 to (k + 1)² using (k + 1)² - 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 0² - k. Now if a, b, c belong to the set, then so do (a² - b²) + c = a² - (b² - c) and -(a² - b²) + c. So by induction n(a² - b²) + c belongs for any integer n. Put A = a² - b². Now if a' and b' are two other numbers in the set, put B = a'² - b'². 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 = a² - b², where a, b are the two given numbers. Let B = a³(a - 2) and let C = b³(b - 2). Since a is in the set so is a² - a and B = (a² - a)² - a². 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 b² 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 + √(a²+h²) above the base (if the distance is x, then by similar triangles x/(h-x) = a/√(a²+h²) ). So if we take XR/RA = 3/2 and RA/PR = (1 + √5)/2 then P is the incenter of XAA'.

[Read More...]

29th USA Mathematical Olympiad 2000 Problems

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. C₁ is a circle through A and B. We can find circle C₂ through B and C touching C₁, circle C₃ through C and A touching C₂, circle C₄ through A and B touching C₃ and so on. Show that C₇ is the same as C₁.

B3.  x₁, x₂, ... , x_n, and y₁, y₂, ... , y_n are non-negative reals. Show that ∑ min(x_ix_j, y_iy_j) ≤ ∑ min(x_iy_j, x_jy_i), where each sum is taken over all n² 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) + 2ⁿb 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 = 90^o, ∠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 = 90^o - (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 tan²B/2 + 5 tan²C/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)² = 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)² = 9 tan²B/2 - 6 tan B/2 + 1, (3 tan C/2 - 1)² = 9 tan²C/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)² + 5 (3 tan C/2 - 1)² + 8(3 tan B/2 - 1)(3 tan C/2 - 1) = 0. But 8² < 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.

---

Problem 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?

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.

---

Problem 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?

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.

---

Problem B2

ABC is a triangle. C₁ is a circle through A and B. We can find circle C₂ through B and C touching C₁, circle C₃ through C and A touching C₂, circle C₄ through A and B touching C₃ and so on. Show that C₇ is the same as C₁.

Solution

Let O_i be the center of C_i. Evidently O_i lies on the perpendicular bisector of the relevant side. Since C₁ and C₂ touch, O₁, B and O₂ must be collinear. Let M be the midpoint of AB. Let ∠MO₁A = x₁. Define x_i similarly. Since O₁, B and O₂ are collinear, we have (90^o - x₁) + B + (90^o - x₂) = 180^o. So B = x₁ + x₂. Similarly, x₂ + x₃ = C, x₃ + x₄ + A, x₄ + x₅ = B, x₅ + x₆ = C, x₆ + x₇ = A. Hence (x₁ + x₂) + (x₃ + x₄) + (x₅ + x₆) = A + B + C = (x₂ + x₃) + (x₄ + x₅) + (x₆ + x₇). So x₁ = x₇. Hence O₁ = O₇.

---

Problem B3

x₁, x₂, ... , x_n, and y₁, y₂, ... , y_n are non-negative reals. Show that ∑ min(x_ix_j, y_iy_j) ≤ ∑ min(x_iy_j, x_jy_i), where each sum is taken over all n² pairs (i, j).

Solution

Let f(x₁, y₁, x₂, y₂, ... , x_n, y_n) = S ( min(x_iy_j, x_jy_i) - min(x_ix_j, y_iy_j) ). So we have to show that f(x₁, y₁, ... , x_n, y_n) ≥ 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 x_i or y_i is zero, or if any x_i = y_i, then the result follows immediately from that for n-1. Suppose x₁/y₁ = x₂/y₂. We claim that f(x₁, ... , y_n) = f(x₁+x₂, y₁+y₂, x₃, y₃, ... , x_n, y_n). Note that the rhs has one less pair of terms. For convenience we write x₁ = k y₁, so x₂ = k y₂. The sum of the (1, i) and (2, i) terms on the lhs is min( x₁y_i, y₁x_i) + min( x₂y_i, y₂x_i) - min( x₁x_i, y₁y_i) - min( x₂x_i, y₂y_i) = (y₁ + y₂) min(ky_i, x_i) - (y₁ + y₂) min(kx_i, y_i). The corresponding (1+2, i) term on the rhs is min( (x₁+x₂)y_i, (y₁+y₂)x_i) - min( (x₁+x₂)x_i, (y₁+y₂)y_i) = (y₁+y₂) min(ky_i, x_i) - (y₁+y₂) min(kx_i, y_i), 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 x₁y₁ - min(x₁², y₁²) + x₂y₂ - min(x₂², y₂²) + 2min(x₁y₂, x₂y₁) - 2min(x₁x₂, y₁y₂) = ky₁² - y₁²min(k², 1) + ky₂² - y₂²min(k², 1) + 2ky₁y₂ - 2y₁y₂min(1,k²) = (y₁+y₂)²(k - min(1,k²) ). On the rhs there is just the one term (x₁+x₂)(y₁+y₂) - min( (x₁+x₂)², (y₁+y₂)²) = k(y₁+y₂)² - (y₁+y₂)²min(k², 1), which is the same. So we have established the claim. Thus if we have any distinct i, j such that x_i/y_i = x_j/y_j, then the result for n follows from that for n-1.

We now show that the same is true if we have x_i/y_i = y_j/x_j. Assume for convenience that x₁/y₁ = y₂/x₂. We can also assume without loss of generality that x₁ ≤ y₂. So we can take x₂ = ky₁, y₂ = k x₁ with k ≥ 1. Then we claim that f(x₁, ... , y_n) = f(x₂ - y₁, y₂ - x₁, x₃, y₃, ... , x_n, y_n). 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( x₁y_i, y₁x_i) + min( x₂y_i, y₂x_i) - min( x₁x_i, y₁y_i) - min( x₂x_i, y₂y_i) = (k-1) min(x₁x_i, y₁y_i) - (k-1) min(x₁y_i, y₁x_i) . The corresponding (1+2, i) term on the rhs is min( (x₂-y₁)y_i, (y₂-x₁)x_i) - min( (x₂-y₁)x_i, (y₂-x₁)y_i) = (k-1) min(y₁y_i, x₁x_i) - (k-1) min(y₁x_i, x₁y_i), which is the same. Similarly, the 1, 2 terms on the lhs are x₁y₁ - min(x₁², y₁²) + x₂y₂ - min(x₂², y₂²) + 2min(x₁y₂, x₂y₁) - 2min(x₁x₂, y₁y₂) = x₁y₁ - min(x₁², y₁²) + k²x₁y₁ - k²min(x₁², y₁²) + 2k min(x₁², y₁²) - 2kx₁y₁ = (1 - k)²x₁y₁ - (1 - k)²min(x₁², y₁²). On the rhs we have (x₂ - y₁)(y₂ - x₁) - min( (x₂ - y₁)², (y₂ - x₁)²) = (k - 1)²x₁y₁ - (k - 1)²min(y₁², x₁²), 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 x_i/y_i = y_j/x_j then the result for n follows from that for n-1.

Put r_i = max(x_i/y_i, y_i/x_i). Reordering the pairs, if necessary, we can take 1 ≤ r₁ ≤ r₂ ≤ ... ≤ r_n. Now let us consider all the x_i, y_i as fixed except y₁. For convenience, let us write t = y₁. We have 1 ≤ r₁ ≤ r₂, so t can take any value in the interval [x₁, x₁r₂] or any value in the interval [x₁/r₂, x₁]. 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) = x₁t - min(x₁², t²) + 2 ∑ min(x₁y_i, t x_i) - 2 ∑ min(x₁x_i, t y_i). Now if x_i ≥ y_i, then x_i/y_i = r_i ≥ r₂ ≥ t/x₁, so x₁x_i ≥ t y_i. Also t x_i ≥ x₁x_i ≥ x₁y_i, so min(x₁y_i, t x_i) = x₁y_i, and min(x₁x_i, t y_i) = t y_i. So if we put z_i = - y_i, then these two terms in g(t) give 2(t - x₁) z_i. Similarly, if x_i < y_i, then x₁y_i ≥ t x_i and t y_i ≥ x₁x_i, so if we put z_i = x_i, then the two terms in g(t) still give 2(t - x₁) z_i. Thus g(t) = x₁t - x₁² + 2(t - x₁) ∑ z_i, 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 = x₁ or x₁r₂. But then we have r₁ = 1 or r₂ 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 [x₁/r₂, x₁]. Again, we put g(t) equal to the sum of the variable terms. So g(t) = x₁t - min(x₁², t²) + 2 ∑ min(x₁y_i, t x_i) - 2 ∑ min(x₁x_i, t y_i). Again, we consider separately the case x_i ≥ y_i which gives a pair of terms with sum 2(x₁ - t)z_i if we put z_i = y_i, whilst if x_i < y_i, then the pair of terms has the sum 2(x₁ - t)z_i if we put z_i = -x_i. So we get g(t) = x₁t - t₂ + 2(x₁ - t) ∑ z_i. This time we have a quadratic. But the leading term - t² 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 [x₁/r₂, x₁] must occur at one of the endpoints. So again the minimum value of f as t varies over the allowed range is at r₁ = r₂ 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.

[Read More...]

28th USA Mathematical Olympiad 1999 Problems

28th USA Mathematical Olympiad 1999 Problems

A1.  Certain squares of an n x n board are colored black and the rest white. Every white square shares a side with a black square. Every pair of black squares can be joined by chain of black squares, so that consecutive members of the chain share a side. Show that there are at least (n² - 2)/3 black squares.

A2.  For each pair of opposite sides of a cyclic quadrilateral take the larger length less the smaller length. Show that the sum of the two resulting differences is at least twice the difference in length of the diagonals.

A3.  p is an odd prime. The integers a, b, c, d are not multiples of p and for any integer n not a multiple of p, we have {na/p} + {nb/p} + {nc/p} + {nd/p} = 2, where { } denotes the fractional part. Show that we can find at least two pairs from a, b, c, d whose sum is divisible by p.

B1.  A set of n > 3 real numbers has sum at least n and the sum of the squares of the numbers is at least n². Show that the largest positive number is at least 2.

B2.  Two players play a game on a line of 2000 squares. Each player in turn puts either S or O into an empty square. The game stops when three adjacent squares contain S, O, S in that order and the last player wins. If all the squares are filled without getting S, O, S, then the game is drawn. Show that the second player can always win.

B3.  I is the incenter of the triangle ABC. The point D outside the triangle is such DA is parallel to BC and DB = AC, but ABCD is not a parallelogram. The angle bisector of BDC meets the line through I perpendicular to BC at X. The circumcircle of CDX meets the line BC again at Y. Show that DXY is isosceles.

Solution

28th USA Mathematical Olympiad 1999

Problem A1

Certain squares of an n x n board are colored black and the rest white. Every white square shares a side with a black square. Every pair of black squares can be joined by chain of black squares, so that consecutive members of the chain share a side. Show that there are at least (n² - 2)/3 black squares.

Solution

Concentrate on the chain condition. We show by induction that if k squares are black and satisfy the chain condition, then at most 3k + 2 squares are black or share a side with a black square. This is obvious for k = 1. Suppose it is true for k and that we have k+1 black squares satisfying the chain condition. It must be possible to pick a black square so that the remaining k black squares still satisfy the chain condition. The remaining k black squares give at most 3k+2 black or sharing a side with a black square, and the picked square adds at most 3. That completes the induction. The result follows immediately, since we must have n² ≤ 3k + 2, where k is the number of black squares.

Actually, it is not trivial to show that it must be possible to pick a black square so that the remaining k black squares still satisfy the chain condition. It is equivalent to showing that in any connected graph you can find a point such that if you remove the point the graph is still connected. The trick is to take two points A and B which are the maximum distance apart (distance is the minimum number of edges you must traverse to get from one to the other). The claim is that removal of either of these points leaves the graph connected. For suppose removing A left a disconnected graph, then there must be a point C such that B and C are not joined by a path when A is removed. Since they are joined when A is present, all paths joining them must pass through A and hence exceed the length of all paths from A to B. Contradiction. Problem A2

For each pair of opposite sides of a cyclic quadrilateral take the larger length less the smaller length. Show that the sum of the two resulting differences is at least twice the difference in length of the diagonals.

Solution

We prove the slightly stronger result that the difference between two opposite sides is at least the difference between the diagonals. Suppose the diagonals meet at X. Then AXB, DXC are similar. Suppose AB = kCD with k ≥ 1. Then BE = kCE and AE = kDE. Suppose CE ≥ DE. Then CD + DE > CE, so CD > CE - DE, so (k-1) CD > (k-1)(CE - DE) or AB - CD > BE - CE - AE + DE = BD - AC.

---

Problem A3

p is an odd prime. The integers a, b, c, d are not multiples of p and for any integer n not a multiple of p, we have {na/p} + {nb/p} + {nc/p} + {nd/p} = 2, where { } denotes the fractional part. Show that we can find two of a, b, c, d whose sum is divisible by p.

Solution

Solution by Michael J Doré

n denote the residue of n mod p, so n = 0, 1, 2, ... , or p-1. Thus {na/p} = na/p, and we have that na + nb + nc + nd = 2p for n not a multiple of p.

Let ω be a complex pth root of 1. We show first that ω + 2ω² + 3ω³ + ... + (p-1)ω^p-1 = p/(ω - 1). Suppose the sum is S. Then (1 - 2ω + ω²)S = ω - pω^p + (p-1)ω^p+1 (we need only look at the two lowest and two highest powers - the others all cancel because k - 2(k-1) + (k-2) = 0) = p(ω - 1). Hence S = p/(ω - 1).

Take residues a', b', c', d', so that aa' = bb' = cc' = dd' = 1 mod p. Then for any integers m, n we have mnaa' = mn mod p. Hence -ma' na = -mn mod p. Hence ω^{-ma' na} = ω^-mn. So na ω^{-ma' na} = na ω^-mn. Similarly for b, c, d. Take n not a multiple of p and add the four equations to get: na ω^{-ma' na} + nb ω^{-mb' nb} + nc ω^{-mc' nc} + nd ω^{-md' nd} = 2p ω^-mn.

As n runs through 1, 2, ... , p-1, each of na, nb, nc, nd runs through a complete set of non-zero residues. If we take m to be not a multiple of p, then so does -mn, so adding the equations for n = 1, 2, ... , p-1, we get na ∑ kω^-a'mk + ∑ k ω^-b'mk + ∑ kω^-c'mk + ∑ kω^-d'mk = 2p(ω + ω² + ... + ω^p-1) = -2p.

Since ω^-a'm is also a complex pth root of 1, we have ∑ kω^-a'mk = p/(ω^-a'm - 1) and similarly for the other terms. So the equation becomes: 1/(ω^-a'm - 1) + 1/(ω^-b'm - 1) + 1/(ω^-c'm - 1) + 1/(ω^-d'm - 1) = -2.

Multiplying through by (ω^-a'm - 1)(ω^-b'm - 1)(ω^-c'm - 1)(ω^-d'm - 1), expanding and simplifying, we get 2 + ω^-a'm-b'm-c'm + ω^-a'm-b'm-d'm + ω^-a'm-c'm-d'm + ω^-b'm-c'm-d'm = ω^-a'm + ω^-b'm + ω^-c'm + ω^-d'm + 2ω^{-a'm-b'm-c'm-d'm} (*). Note that this equation is also true for m = 0 (when it is just 5 = 5). Now sum the equations for m = 0, 1, 2, ... , p-1. We have ∑ ω^k = p if k is a multiple of p, and 0 otherwise. Obviously the first term ∑ 2 gives 2p and the other terms on the lhs give non-negative sums, so ∑ lhs is at least 2p. The first four terms on the rhs all have zero sum, so the last term must have sum 2p, so a' + b' + c' + d' must be a multiple of p. Thus (*) becomes ω^a'm + ω^b'm + ω^c'm + ω^d'm = ω^-a'm + ω^-b'm + ω^-c'm + ω^-d'm. Multiply through by ω^-a'm and sum for m = 0, 1, 2, ... , p-1. The first term on the lhs has sum p and the others have non-negative sum. The first term on the rhs has zero sum, so one of the others must have positive sum. Hence p divides at least one of (a'+b'), (a'+c'), (a'+d'). Without loss of generality it divides a' + b'. In other words a' + b' = 0 mod p. Multiplying by ab, we get a + b = 0 mod p.

---

Problem B1

A set of n > 3 real numbers has sum at least n and the sum of the squares of the numbers is at least n². Show that the largest positive number is at least 2.

Solution

Let the numbers be x₁, x₂, ... , x_n. Notice first that x₁ = x₂ = ... = x_n-1 = 2, x_n = 2 - n, gives ∑ x_i = (n - 1)2 + (2 - n) = n, ∑ x_i² = (n - 1)4 + (4 - 4n + n²) = n², so the inequality is best possible.

Suppose the result is false. So we have a set of numbers with S x_i ≥ n, ∑ x_i² ≥ n² and max x_i < 2. At least one of the numbers must be negative, since otherwise we have n ≥ 4, so n² ≥ 4n > ∑ x_i². Contradiction. This allows us to assume that ∑ x_i = n, for if it is greater, we may just decrease a negative x_i until it becomes true (∑ x_i² will be increased, so it will remain at least n²).

Now suppose two of the x_i, namely x and y, are less than 2. Then if we replace them by 2 and x + y - 2, the sum is unaffected and the sum of squares is increased by 2(2 - x)(2 - y). Since we start with all the x_i less than 2, we may do this repeatedly until we reach a set with all the numbers 2 except one. Since the sum is unchanged, the other number must be 2 - n, and, as shown above, that makes the sum of the squares n². But we have increased the sum of the squares at each step. Contradiction.

---

Problem B2

Two players play a game on a line of 2000 squares. Each player in turn puts either S or O into an empty square. The game stops when three adjacent squares contain S, O, S in that order and the last player wins. If all the squares are filled without getting S, O, S, then the game is drawn. Show that the second player can always win.

Solution

Suppose a square is such that if you play there then that allows your opponent to win on the following move. If you play an O, then your opponent must win by playing an adjacent S. So we must have S 1 2 3, where 1 and 2 are empty and you play O on square 1. But you also lose if you play S, so your opponent must then win by playing O on 2, which means that 3 must already contain an S. But now the situation is symmetrical, so that 2 is also a losing square. Thus, until someone plays on one of them, losing squares always occur in pairs.

The board has an even number of squares, so the first player always faces a board with an even number of squares not yet occupied, whereas the second player always faces a board with an odd number of squares not yet occupied. Thus provided (1) there is at least one pair of losing squares, (2) he never plays on a losing square, and (3) he makes the obvious winning move if the first player ever creates the opportunity, then the second player is sure to win, because the first player will eventually face a board with only losing squares available for play.

To make sure there is at least one pair of losing squares the second player must create it. He can always do this by placing an S on his first move well away from the first player's move and from the edges of the board. Then on his second move (assuming the first player has not been stupid enough to allow him an immediate win) he can always play another S three away from it, creating a pair of losing squares. Thereafter, he must simply take care to win if there is a winning move and otherwise to avoid losing plays.

---

Problem B3

I is the incenter of the triangle ABC. The point D outside the triangle is such DA is parallel to BC and DB = AC, but ABCD is not a parallelogram. The angle bisector of BDC meets the line through I perpendicular to BC at X. The circumcircle of CDX meets the line BC again at Y. Show that DXY is isosceles.

Solution

Let IX meet BC at Z. Then using equal tangents, (BC - CZ) + (AC - CZ) = AB, so CZ = (AC + BC - AB)/2. Suppose the excircle opposite D of DBC touches BC at Z'. Then, again considering equal tangents, DB + (BC - CZ') = DC + CZ', so CZ' = (BD + BC - DC)/2 = (AC + BC - AB)/2 = CZ, so Z' and Z coincide. Since X lies on the perpendicular to BC at Z and on the bisector of ∠BDC, it must also be the center of the excircle. Hence XC is the exterior bisector of ∠BCD. So ∠XCB = 90 - ∠BCD/2.

By construction, YDCX is cyclic, so ∠YDX = ∠YCX = ∠XCB. Also ∠BCD = ∠YCD = ∠YXD. Hence ∠YDX = 90 - ∠YXD/2. Hence YX = DX.

[Read More...]

27th USA Mathematical Olympiad 1998 Problems

27th USA Mathematical Olympiad 1998 Problems

A1.  The sets {a₁, a₂, ... , a₉₉₉} and {b₁, b₂, ... , b₉₉₉} together contain all the integers from 1 to 1998. For each i, |a_i - b_i| = 1 or 6. For example, we might have a₁ = 18, a₂ = 1, b₁ = 17, b₂ = 7. Show that ∑₁⁹⁹⁹ |a_i - b_i| = 9 mod 10.

A2.  Two circles are concentric. A chord AC of the outer circle touches the inner circle at Q. P is the midpoint of AQ. A line through A intersects the inner circle at R and S. The perpendicular bisectors of PR and CS meet at T on the line AC. What is the ratio AT/TC?

A3.  The reals x₁, x₂, ... , x_n+1 satisfy 0 < x_i < π/2 and ∑₁ⁿ⁺¹ tan(x_i - π/4) ≥ n-1. Show that ∏₁ⁿ⁺¹ tan x_i ≥ nⁿ⁺¹.

B1.  A 98 x 98 chess board has the squares colored alternately black and white in the usual way. A move consists of selecting a rectangular subset of the squares (with boundary parallel to the sides of the board) and changing their color. What is the smallest number of moves required to make all the squares black?

B2.  Show that one can find a finite set of integers of any size such that for any two members the square of their difference divides their product.

B3.  What is the largest number of the quadrilaterals formed by four adjacent vertices of an convex n-gon that can have an inscribed circle?

Solution

27th USA Mathematical Olympiad 1998

Problem A1

The sets {a₁, a₂, ... , a₉₉₉} and {b₁, b₂, ... , b₉₉₉} together contain all the integers from 1 to 1998. For each i, |a_i - b_i| = 1 or 6. For example, we might have a₁ = 18, a₂ = 1, b₁ = 17, b₂ = 7. Show that ∑₁⁹⁹⁹ |a_i - b_i| = 9 mod 10.

Solution

If |a_i - b_i| = 6, then a_i and b_i have the same parity, so the set of such a_i and b_i contains an even number of odd numbers. But if |a_i - b_i| = 1, then a_i and b_i have opposite parity, so each such pair includes just one odd number. Hence if the number of such pairs is even, then the set of all such a_i and b_i also has an even number of odd numbers. But the total number of a_i and b_i which are odd is 999 which is odd. Hence the number of pairs with |a_i - b_i| = 1 must be odd, and hence the number of pairs with |a_i - b_i| = 6 must be even. Suppose it is 2k. Then ∑ |a_i - b_i| = (999 - 2k) 1 + 2k 6 = 999 + 10k = 9 mod 10. Problem A2

Two circles are concentric. A chord AC of the outer circle touches the inner circle at Q. P is the midpoint of AQ. A line through A intersects the inner circle at R and S. The perpendicular bisectors of PR and CS meet at T on the line AC. What is the ratio AT/TC?

Solution

We have AR·AS = AQ² = AQ/2 2AQ = AP·AC, so ARP and ACS are similar, so ∠ACS = ∠ARP, so PRSC is cyclic. Hence T must be the center of its circumcircle and must also lie on the perpendicular bisector of CP. Hence it must be the midpoint of CP. So CT = 3/8 CA and hence AT/TC = 5/3.

However, that is not quite all. If CS is parallel to PR, then their perpendicular bisectors coincide and both pass through A. So one could also regard A as a possible position for T.

---

Problem A3

The reals x₁, x₂, ... , x_n+1 satisfy 0 < x_i < π/2 and ∑₁ⁿ⁺¹ tan(x_i - π/4) ≥ n-1. Show that ∏₁ⁿ⁺¹ tan x_i ≥ nⁿ⁺¹.

Solution

Put t_i = tan(x_i - π/4). Then (1 + t_i)/(1 - t_i) = tan(π/4 + x_i - π/4) = tan x_i. So we wish to show that ∏(1 + t_i)/(1 - t_i) ≥ nⁿ⁺¹.

The given inequality is equivalent to 1 + t_i ≥ ∑_j≠i (1 - t_j). Using the AM/GM inequality, this implies that (1 + t_i)/n >= ∏_j≠i (1 - t_j)^1/n. Hence ∏ (1 + t_i)/nⁿ⁺¹ ≥ ∏_i ∏_j≠i (1 - t_j)^1/n = ∏ (1 - t_i).

---

Problem 4

A 98 x 98 chess board has the squares colored alternately black and white in the usual way. A move consists of selecting a rectangular subset of the squares (with boundary parallel to the sides of the board) and changing their color. What is the smallest number of moves required to make all the squares black?

Solution

Answer: 98.

There are 4·97 adjacent pairs of squares in the border and each pair has one black and one white square. Each move can fix at most 4 pairs, so we need at least 97 moves. However, we start with two corners one color and two another, so at least one rectangle must include a corner square. But such a rectangle can only fix two pairs, so at least 98 moves are needed.

It is easy to see that 98 suffice: take 49 1x98 rectangles (alternate rows), and 49 98x1 rectangles (alternate columns).

---

Problem B2

Show that one can find a finite set of integers of any size such that for any two members the square of their difference divides their product.

Solution

We find inductively a set with n elements satisfying the slightly stronger condition that if a and b are any two elements, then a - b divides both a and b. For n = 2, we may take {1, 2}. Suppose we have a set S for n. Let m be the lowest common multiple (or any multiple) of all the members of S. Now take the set {m + a: a ∈ S} ∪ {m} for n+1. A difference (m + a) - (m + b) = a - b divides a and b, hence also m, and hence m + a and m + b. A difference (m + a) - m = a divides a and m and hence also m + a.

---

Problem B3

What is the largest number of the quadrilaterals formed by four adjacent vertices of an convex n-gon that can have an inscribed circle?

Solution

Answer: [n/2].

Take a regular n-gon and slice off alternate corners (until [n/2] corners have been cut). Specifically, if the vertices are A₁, A₂, ... , A_n, then we slice off the corners at A₁, A₃, A₅, ... A_m, where m = n-1 if n is even, or n-2 if n is odd. At each corner A_i which we slice, we take the inscribed circle to the triangle A_i-1A_iA_i+1, draw a tangent to it parallel to A_i-1A_i+1 and cut along the tangent. This procedure shows that [n/2] can be achieved.

To show that it is optimal it is sufficient to show that if A, B, C, D, E are adjacent vertices of any polygon and ABCD has an inscribed polygon, then BCDE does not. Since ABCD has an inscribed polygon, AD + BC = AB + CD (if the inscribed circle touches at X on AB and Y on AD, then AX = AY. That and the three similar equations give the result). So if BCDE also has an inscribed polygon, then BE + CD = BC + DE. Hence (adding) AD + BE = AB + DE. But the diagonals AD and BE must meet at some point X. Then AD + BE = AX + XD + BX + XE = (AX + XB) + (DX + XE) > AB + DE. Contradiction.

[Read More...]

26th USA Mathematical Olympiad 1997 Problems

26th USA Mathematical Olympiad 1997 Problems

A1.  Let p_n be the nth prime. Let 0 < a < 1 be a real. Define the sequence x_n by x₀ = a, x_n = the fractional part of p_n/x_n-1 if x_n ≠ 0, or 0 if x_n-1 = 0. Find all a for which the sequence is eventually zero.

A2.  ABC is a triangle. Take points D, E, F on the perpendicular bisectors of BC, CA, AB respectively. Show that the lines through A, B, C perpendicular to EF, FD, DE respectively are concurrent.

A3.  Show that there is a unique polynomial whose coefficients are all single decimal digits which takes the value n at -2 and at -5.

B1.  A sequence of polygons is derived as follows. The first polygon is a regular hexagon of area 1. Thereafter each polygon is derived from its predecessor by joining two adjacent edge midpoints and cutting off the corner. Show that all the polygons have area greater than 1/3.

B2.  Show that xyz/(x³ + y³ + xyz) + xyz/(y³ + z³ + xyz) + xyz/(z³ + x³ + xyz) ≤ 1 for all positive real x, y, z.

B3.  The sequence of non-negative integers c₁, c₂, ... , c₁₉₉₇ satisfies c₁ ≥ 0 and c_m + c_n ≤ c_m+n <= c_m + c_n + 1 for all m, n > 0 with m + n < 1998. Show that there is a real k such that c_n = [nk] for 1 ≤ n ≤ 1997.

Solution

26th USA Mathematical Olympiad 1997

Problem A1

Let p_n be the nth prime. Let 0 < a < 1 be a real. Define the sequence x_n by x₀ = a, x_n = the fractional part of p_n/x_n-1 if x_n ≠ 0, or 0 if x_n-1 = 0. Find all a for which the sequence is eventually zero.

Solution

Let {x} denote the fractional part of x. {x} = x minus some integer, so {x} is rational iff x is rational. Hence if x_n is irrational, then p_n+1/x_n is irrational and hence x_n+1 is irrational. So if a is irrational, then the sequence is never zero.

Suppose x_n = r/s with 0 < r < s relatively prime integers. Then x_n+1 = u/r, where u is the remainder on dividing sp_n+1 by r. So, when expressed as a fraction in lowest terms, the denominator of x_n+1 is less than that for x_n. So if a is rational and has denominator b, then after at most b iterations we get zero.

Comment: the fact that the p_n are primes is a red herring. Problem A2

ABC is a triangle. Take points D, E, F on the perpendicular bisectors of BC, CA, AB respectively. Show that the lines through A, B, C perpendicular to EF, FD, DE respectively are concurrent.

Solution

Suppose that the feet of the perpendiculars from A and P to EF are H and K respectively. Then AF² - AE² = (AH² + FH²) - (AH² + EH²) = FH² - EH² = (FH + EH)(FH - EH) = FE(FH - EH). Similarly, PF² - PE² = FE(FK - EK). So H and K coincide iff AF² - AE² = PF² - PE². In other words, P lies on the line through A perpendicular to EF iff PF² - PE² = AF² - AE².

Thus if P is the intersection of the line through A perpendicular to EF and the line through B perpendicular to FD, then PF² - PE² = AF² - AE² and PD² - PF² = BD² - BF². Hence PD² - PE² = AF² - BF² + BD² - AE². But F is equidistant from A and B, so AF² = BF². Similarly, BD² = CD² and AE² = CE². Hence PD² - PE² = CD² - CE², so P also lies on the perpendicular to DE through C.

---

Problem A3

Show that there is a unique polynomial whose coefficients are all single decimal digits which takes the value n at -2 and at -5.

Solution

Call the polynomial p(x) = p₀ + p₁x + p₂x² + ... + p_mx^m. Since p(x) - n = 0 has -2 and -5 as roots, it must have the factor (x + 2)(x + 5) = x² + 7x + 10. So for some a₀, a₁, a₂, ... we have:

10a0              +n = p0 ∈ {0,1,2,3,4,5,6,7,8,9}

10a1 + 7a0           = p1 ∈ {0,1,2,3,4,5,6,7,8,9}

10a2 + 7a1 + a0      = p2 ∈ {0,1,2,3,4,5,6,7,8,9}

10a3 + 7a2 + a1      = p3 ∈ {0,1,2,3,4,5,6,7,8,9}

...

10ar+1 + 7ar + ar-1  = pr+1 ∈ {0,1,2,3,4,5,6,7,8,9}

...

Now these equations uniquely determine a_i and p_i. For p₀ must be chosen so that p₀ - n is a multiple of 10, which fixes p₀ and a₀ uniquely. Similarly, given p_i and a_i for 0 ≤ i ≤ r, we have p_r+1 = 10a_r+1 + 7a_r + a_r-1 = 7a_r + a_r-1 mod 10, so p_r+1 is uniquely determined and hence also a_r+1. Thus any solution is certainly unique, but it is not clear that the process terminates, so that p_i and a_i are zero from some point on. Evidently the sequence a_i is bounded. For if a_i, a_i+1 ≤ B ≥ 9, then |a_i+2| ≤ 0.7B + 0.1B + 0.1B ≤ B. So if we take B = max(9,|a₀|,|a₁|), then |a_i| ≤ B for all i.

So we can define L_k = min(a_k, a_k+1, a_k+2, ...), U_k = max(a_k, a_k+1, a_k+2, ... ). Obviously, we have L₀ ≤ L₁ ≤ ... ≤ L_k ≤ L_k+1 ≤ ... ≤ U_k+1 ≤ U_k ≤ ... ≤ U₁ ≤ U₀. So L_i is an increasing integer sequence which is bounded above, so we must have L_i = L for all sufficiently large i. Similarly, U_i = U for all sufficiently large i, and L ≤ U (1).

But if a_i, a_i+1 ≥ L, then a_i+2 ≤ -0.7L - 0.1L + 0.9 ≤ -0.8L + 0.9. So U ≤ -0.8L + 0.9 (2). Similarly, if a_i, a_i+1 ≤ U, then a_i+2 ≥ -0.8U, so L ≥ -0.8U (3).

But as the diagram shows the only lattice point satisfying (1), (2), (3) is (0,0), so a_i = 0 for all sufficiently large i, which establishes existence.  

---

Problem B1

A sequence of polygons is derived as follows. The first polygon is a regular hexagon of area 1. Thereafter each polygon is derived from its predecessor by joining to adjacent edge midpoints and cutting off the corner. Show that all the polygons have area greater than 1/3.

Solution

The first point to observe is that each polygon in the sequence is convex. The next point is that we can never completely eliminate the sides of the hexagon, in other words every polygon in the sequence has a vertex on each of the sides of the hexagon.

Let the hexagon be ABCDEF. The diagonals AC, BD, CE, DF, EA, FB meet at the six vertices of a smaller hexagon. Call it UVWXYZ. To be specific, let U be the intersection of FB and AC, V the intersection of AC and BD, W the intersection of BD and CE and so on. Now take any polygon in the sequence. It has a vertex on AB and a vertex on BC. Since it is convex, it must also include the segment joining these points. But any such segment intersects BU and BV. So it has a point on BU and on BV. Similarly for each of the other segments: CV, CW, DW, DX, ... . But the convex hull of these 12 points includes the hexagon UVWXYZ. Hence the area of any polygon in the sequence is at least that of UVWXYZ.

The triangle ABF is isosceles with angle ABF = 30 deg, so if AB = k, then BF = k√3. But BU = FZ = k/√3. Hence UZ = k√3 - 2k/√3 = k/√3. So the area of UVWXYZ is 1/3 the area of ABCDEF.

---

Problem B2

Show that xyz/(x³ + y³ + xyz) + xyz/(y³ + z³ + xyz) + xyz/(z³ + x³ + xyz) ≤ 1 for all real positive x, y, z.

Solution

For positive x, y, x ≥ y iff x² ≥ y², so (x - y)(x² - y²) ≥ 0, or x³ + y³ ≥ xy(x + y). Hence x³ + y³ + xyz ≥ xy(x + y + z) and so xyz/(x³ + y³ + xyz) ≤ z/(x + y + z). Adding the two similar equations gives the required inequality.

---

Problem B3

The sequence of non-negative integers c₁, c₂, ... , c₁₉₉₇ satisfies c₁ ≥ 0 and c_m + c_n ≤ c_m+n ≤ c_m + c_n + 1 for all m, n > 0 with m + n < 1998. Show that there is a real k such that c_n = [nk] for 1 ≤ n ≤ 1997.

Solution

Any such k must satisfy c_n/n ≤ k < c_n/n + 1/n for all n. Hence we must have c_m/m < c_n/n + 1/n or n c_m < m c_n + m for all m, n. Conversely, if this inequality holds, then such k exist. For example, we could take k = max c_n/n.

It is tempting to argue that n c_m < (n-1) c_m + c_2m < (n-2) c_m + c_3m < ... < c_mn ≤ c_mn-n + c_n + 1 ≤ ... ≤ m c_n + m. But this does only works for small m, n, because otherwise mn may be out of range. Instead we use induction on m+n. It is obviously true for m = n = 1 and indeed any m = n. Now suppose m < n (and it is true for smaller m + n). Then by induction (n - m) c_m < m c_n-m + m. But c_m ≤ c_n - c_n-m, so m c_m ≤ m c_n - m c_n-m. Adding, we get n c_m < m c_n + m as required. Similarly, if m > n (and the result is true for smaller m + n), then by induction, n c_m-n < (m - n) c_n + (m - n). But n c_m <= n c_n + n c_m-n + n, so adding n c_m < m c_n + m, as required.

[Read More...]

25th USA Mathematical Olympiad 1996 Problems

25th USA Mathematical Olympiad 1996 Problems

A1.  Let k = 1^o. Show that 2 sin 2k + 4 sin 4k + 6 sin 6k + ... + 180 sin 180k = 90 cot k.

A2.  Let S be a set of n positive integers. Let P be the set of all integers which are the sum of one or more distinct elements of S. Show that we can find n subsets of P whose union is P such that if a, b belong to the same subset, then a ≤ 2b.

A3.  Given a triangle, show that we can reflect it in some line so that the area of the intersection of the triangle and its reflection has area greater than 2/3 the area of the triangle.

B1.  A type 1 sequence is a sequence with each term 0 or 1 which does not have 0, 1, 0 as consecutive terms. A type 2 sequence is a sequence with each term 0 or 1 which does not have 0, 0, 1, 1 or 1, 1, 0, 0 as consecutive terms. Show that there are twice as many type 2 sequences of length n+1 as type 1 sequences of length n.

B2.  D lies inside the triangle ABC. ∠BAC = 50^o. ∠DAB = 10^o, ∠DCA = 30^o, ∠DBA = 20^o. Show that ∠DBC = 60^o.

B3.  Does there exist a subset S of the integers such that, given any integer n, the equation n = 2s + s' has exactly one solution in S? For example, if T = {-3, 0, 1, 4), then there are unique solutions -3 = 2·0 - 3, -1 = 2·1 - 3, 0 = 2·0 + 0, 1 = 2·0 + 1, 2 = 0 + 2·1, 3 = 2·1 + 1, 4 = 2·0 + 4, 5 = 2·-3 + 1, but not for 6 = 2·1 + 4 = 2·-3 + 0, so T cannot be a subset of S.

Solution

25th USA Mathematical Olympiad 1996

Problem A1

Let k = 1^o. Show that 2 sin 2k + 4 sin 4k + 6 sin 6k + ... + 180 sin 180k = 90 cot k.

Solution

Multiply the expression by sin k. We have 2 sin 2nk sin k = cos(2n-1)k - cos(2n+1)k. So 2n sin 2nk sin k = n cos(2n-1)k - n cos(2n+1)k. Adding these equations for n = 1, 2, ... , 90 gives: 2 sin 2k + 4 sin 4k + 6 sin 6k + ... + 180 sin 180k = cos k + (2 - 1) cos 3k + (3 - 2) cos 5k + ... + (90 - 89) cos 179k - 90 cos 181k. Now cos 181k = - cos k, so the last term is + 90 cos k. The other terms sum to zero in pairs: cos k + cos 179k = 0, cos 3k + cos 177k = 0, ... , cos 89k + cos 91k = 0. Hence result. Problem A2

Let S be a set of n positive integers. Let P be the set of all integers which are the sum of one or more distinct elements of S. Show that we can find n subsets of P whose union is P such that if a, b belong to the same subset, then a ≤ 2b.

Solution

Let the members of S be a₁ < a₂ < ... < a_n. Let s_m = a₁ + a₂ + ... + a_m and put s₀ = 0. Let P_m = { s ∈ P : s_m-1 < s ≤ s_m } for m = 1, 2, ... , n. We claim that this partition works. It is sufficient to show that if b ∈ P_m then 2b > s_m (for then if a also belongs to P_m we have a ≤ s_m <= 2b).

Now since b > s_m-1, b must be a sum which includes some a_i with i ≥ m. So certainly b ≥ a_i ≥ a_m = s_m - s_m-1 > s_m - b. Hence 2b > s_m as required.

---

Problem A3

Given a triangle, show that we can reflect it in some line so that the area of the intersection of the triangle and its reflection has area greater than 2/3 the area of the triangle.

Solution

Let the triangle be ABC. Assume A is the largest angle. Let AD be the altitude. Assume AB ≤ AC, so that BD ≤ BC/2. If BD > BC/3, then reflect in AD. If B' is the reflection of B', then B'D = BD and the intersection of the two triangles is just ABB'. But BB' = 2BD > 2/3 BC, so ABB' has more than 2/3 the area of ABC.

If BD < BC/3, then reflect in the angle bisector of C. The reflection of A' is a point on the segment BD and not D. (It lies on the line BC because we are reflecting in the angle bisector. A'C > DC because ∠CAD < ∠CDA = 90^o. Finally, A'C ≤ BC because we assumed ∠B does not exceed ∠A). The intersection is just AA'C. But area AA'C/area ABC = CA'/CB > CD/CB ≥ 2/3.

---

Problem B1

A type 1 sequence is a sequence with each term 0 or 1 which does not have 0, 1, 0 as consecutive terms. A type 2 sequence is a sequence with each term 0 or 1 which does not have 0, 0, 1, 1 or 1, 1, 0, 0 as consecutive terms. Show that there are twice as many type 2 sequences of length n+1 as type 1 sequences of length n.

Solution

Let S be the set of sequences length n and T the set of sequences length n+1 beginning with 0. Define f: S → T as follows. Let the m+1th term of f(s) be the same as the mth term if the mth term of s is 0 and different if the mth term of s is 1. It is clear that f is a bijection. [Define its inverse g by g(t) has 0 as its mth term iff the mth and m+1th terms of t are the same.] Also f(s) includes 0, 0, 1, 1 or 1, 1, 0, 0 iff s includes 0, 1, 0. Hence the number of type 1 sequences in S is the same as the number of type 2 sequences in T. The same result holds if we take T to be sequences which begin with 1.

---

Problem B2

D lies inside the triangle ABC. ∠BAC = 50^o. ∠DAB = 10^o, ∠DCA = 30^o, ∠DBA = 20^o. Show that ∠DBC = 60^o.

Solution

Reflect A in the line BD to get A'. Let Z be the intersection of BD and AA'. Let BA' meet AC at X. Since ∠ABX = 2 ∠ABD = 40^o, and ∠BAX = 50^o, we have ∠BXA = 90^o. Now ∠DAA' = ∠BAA' - ∠DAB = ∠BAA' - 10^o. But ∠BAA' = 90^o - ∠DBA = 70^o, so ∠DAA' = 60^o.

Let BX meet CD at Y. ∠DYX = ∠YXC + ∠DCX = 90^o + 30^o = 120^o = 180^o - angle DAA', so DAA'Y is cyclic, so ∠A'YA = ∠A'DA = 2 ∠ZDA = 2(∠DBA + ∠DAB) = 60^o.

But ∠XYC = 90 - ∠DCA = 60^o, so C is the reflection of A in BX. Hence BC = BA, so ∠ACB = ∠BAC = 50^o. Hence ∠ABC = 80^o and ∠DBC = 80^o - ∠DBA = 60^o.

---

Problem B3

Does there exist a subset S of the integers such that, given any integer n, the equation n = 2s + s' has exactly one solution in S? For example, if T = {-3, 0, 1, 4), then there are unique solutions -3 = 2·0 - 3, -1 = 2·1 - 3, 0 = 2·0 + 0, 1 = 2·0 + 1, 2 = 0 + 2·1, 3 = 2·1 + 1, 4 = 2·0 + 4, 5 = 2·-3 + 1, but not for 6 = 2·1 + 4 = 2·-3 + 0, so T cannot be a subset of S.

Solution

Answer: yes.

We show how to choose S inductively. Suppose we have already chosen a₁, a₂, ... , a_n, but we do not yet have a solution for m ≥ 0. Take N so that all |a_i| < N. Now take a_n+1 = 5N + m, a_n+2 = -10N - m. This gives a solution for m: m = 2a_n+1 + a_n+2, but it does not duplicate any existing solutions, since |2a_n+2 + a_n+1|, |2a_n+1 + a_i|, |2a_n+2 + a_i|, |a_n+1 + 2a_i|, |a_n+2 + 2a_i| are all ≥ 3N, whereas all existing sums have absolute value < 3N. Similarly for m < 0, we may take a_n+1 = - 5N + m, a_n+2 = 10N - m.

Comment. The problem (and the opportunity) is that since positive and negative numbers are allowed |s| and |s'| can be arbitrarily large and still give n = 2s + s'. Compare the similar problem where S must be a subset of the non-negative integers and we require a unique solution n = 2s + s' for all non-negative n. In this case we can give S explicitly as all numbers with just the digits 0 and 1 in base 4. In fact, the same idea works for the case of all the integers, but it requires a little more work to show that -4 works as a number base.

[Read More...]