1998-1999 Olympiad Correspondence Problems

Set 5

25.

Let c be a positive integer and let f₀ = 1, f₁ = c and f_n = 2f_n-1 - f_n-2 + 2 for n ³ 1. Prove that for each k ³ 0, there exists m ³ 0 for which f_k f_k+1 = f_m.

View solution

26.

Let p(x) be a polynomial with integer coefficients for which p(0) = p(1) = 1. Let a₀ be any nonzero integer and define a_n+1 = p(a_n) for n ³ 0. Prove that, for distinct nonnegative integers i and j, the greatest common divisor of a_i and a_j is equal to 1.

View solution

27.

(a) Let n be a positive integer and let f(x) be a quadratic polynomial with real coefficients and real roots that differ by at least n. Prove that the polynomial g(x) = f(x) + f(x + 1) + f(x + 2) + ¼+ f(x + n) also has real roots.

(b) Suppose that the hypothesis in (a) is replaced by positing that f(x) is any polynomial for which the difference between any pair of roots is at least n. Does the result still hold?

View solution

28.

Find the locus of points P lying inside an equilateral triangle for which ÐPAB + ÐPBC + ÐPCA = 90^°.

View solution

29.

(a) Prove that for an arbitrary plane convex quadrilateral, the ratio of the largest to smallest distance between pairs of points is at least Ö2.

(b) Prove that for any six distinct points in the plane, the ratio of the largest to smallest distances between pairs of them is at least Ö3.

View solution

30.

Let a, b, c be positive real numbers. Prove that

(a) 4(a³ + b³) ³ (a + b)³;

(b) 9(a³ + b³ + c³) ³ (a + b + c)³,

(c) More generally, establish that for each integer n and n nonnegative reals that

n2 (a13 + a23 + ¼+ an3) ³ (a1 + a2 + ¼+ an)3  .

View solution

---

Problem 25.

25.

First solution. A straightforward induction argument establishes that f_n = nc + (n-1)², and it can be checked algebraically that

fk fk+1 = fm

where m = kc + (k² - k + 1) = f_k + k.

25.

Comment. This is basically a problem in experimentation and pattern recognition. Once the result is conjectured, the algebraic manipulations required are straightforward. One way to approach the problem is to consider f_k f_k+1 = m² + (c - 2)m + 1 as a quadratic equation to be solved for m. Note that when c = 4, it turns out that f_n = (n+1)². If we let f(c, n) = nc + (n-1)², then m = f(c+1, k). More generally, we have for every monic quadratic polynomial p with integer coefficients, p(k)p(k+1) = p(m) for some integer m.

---

Problem 26.

26.

First solution. By the factor theorem, we have that p(x) - 1 = x(x - 1)q(x) for some polynomial q(x) with integer coefficients. Hence

an+1 - 1 = an (an - 1)q(an) = ¼ = an an-1 ¼a1 (a1 - 1) n Õ k = 1  q(ak)

for each positive integer n. (Note that a_n+1 cannot be zero, as this would force the impossible a_n (a_n - 1)q(a_n) = -1.) It follows that a_m º 1 (mod a_r) whenever m > r and the result follows.

26.

Second solution. Let p(x) = c_d x^d + ¼+ c₁ x + c₀. The conditions imply that c₀ = c_d + ¼+ c₁ + c₀ = 1. Let a be any nonzero integer. Then

p(a) = cd ad + ¼+ c1 a + c0 º c0 = 1   (mod  a) .

Suppose as an induction hypothesis that the ith iterate pⁱ (a) º 1 (mod a). Then

pi+1 (a) = cd pi (a)d + ¼+ c1 pi (a) + c0 º cd + ¼+ c1 + c0 = 1     (mod  a) .

In particular, we find that a_n+r º 1 (mod a_n) for each pair of positive integers n and r from which the result follows.

---

Problem 27.

27.

(a) First solution. By making a substitution of the form x¢ = x - k, we can dispose of the linear term in the quadratic. Thus we may assume that f(x) = x² - r² where 2r ³ n. Then

g(x) = (n+1) [x2 - nx + n(2n+1) 6 - r2] = (n+1) é ê ë æ ç è x + n 2 ö ÷ ø 2   + æ ç è n2 + 2n 12 - r2 ö ÷ ø ù ú û  .

Since

r2 - n2 + 2n 12 ³ n2 4 - n2 + 2n 12 = n(n-1) 6   ,

g(x) £ 0 when x = -n/2 and so has real roots. These roots are coincident if and only if n = 1 and r = 1/2, i.e., when f(x) = x² - ¹/₄.

27.

(a) Second solution. [Z. Amir-Khosravi] Let u and v be the two roots of f(x) with u + n £ v, with strict inequality when n = 1. Wolog, suppose that f(x) < 0 for x < u and x > v, while f(x) < 0 for u < x < v. Then g(x) is a quadratic polynomial for which

g(u - n) = f(u - n) + ¼+ f(u) > 0 g(u) = f(u) + ¼+ f(u + n) < 0 g(v) = g(v) + ¼+ g(v + n) > 0  .

By the Intermediate Value Theorem, g(x) has two roots.

When n = 1 and v = u + 1, then g(u) = 0. Since g(x) is a real quadratic with at least one real root, both roots are real.

27.

(b) First solution. Suppose that f(x), and hence g(x), has degree d, and let the roots of f(x) be a₁, a₂, ¼, a_d where a_i+1 ³ a_i + n. Since f(x) has no multiple roots, it alternates in sign as x passes through the roots a_i.

To begin with, let n ³ 2, and let a_i be one of the roots. Suppose, wolog, that f(x) < 0 for a_i - n < x < a_i and f(x) > 0 for a_i < x < a_i + n. Then

g(ai - n) = f(ai - n) + ¼+ f(ai -1) + f(ai) < 0

and

g(ai) = f(ai) + f(ai + 1) + ¼+ f(ai + n) > 0 .

By the Intermediate Value Theorem, g(x) has a root b_i between a_i - n and a_i. Since the open intervals (a_i - n) are disjoint, the b_i are distinct. Since we have identified d (the degree of g(x)) roots of g(x), all of the roots of g(x) are real.

Now suppose that n = 1. If the intervals [a_i - 1, a_i] are all disjoint, then we can use the foregoing argument since g(a_i - 1) = f(a_i - 1) and g(a_i) = f(a_i + 1) are nonzero with opposite signs. Suppose, on the other hand, there are s roots of f(x), namely a_r, a_r+1, ¼, a_r+s-1 spaced unit distance apart (a_r+i = a_r+i-1 + 1 for 1 £ i £ s-1) such that a_r - 1 and a_r+s-1 + 1 are not roots of f(x). We will discuss the case that f(x) < 0 for a_r-1 £ x < a_r and f(x) > 0 for a_r+s-1 < x £ a_r+s-1 + 1; the other three cases can be handled analogously.

In this case, all the roots of f(x) are simple, s is odd, and

g(ar - 1) = f(ar - 1) + f(ar) = f(ar - 1) < 0

g(ar+i) = f(ar+i) + f(ar+i+1) = 0      for  0 £ i £ s-2

and

g(ar+s-1) = f(ar+s-1) + f(ar+s-1 + 1) = f(ar+s-1 + 1) > 0 .

Thus, g(x) must have an odd number of roots in the interval (a_r - 1, a_r+s-1) counting multiplicity. We can account for s - 1 of them, { a_r, a_r+1, ¼, a_r+s-2 }, so, since s-1 is even, there must be at least s roots in this interval.

We can apply this analysis to the other ``blocks'' of s roots of f(x) spaced at unit distance to obtain disjoint intervals with at least s roots of g(x). From this, we can deduce that all the roots of g(x) must be real.

---

Problem 28.

28.

First solution. Let ÐPAB = a, ÐPAC = a¢, ÐPBC = b, ÐPBA = b¢, ÐPCA = g and ÐPCB = g¢, so that a+ a¢ = b+ b¢ = g+ g¢ = 60^°. Let |AP | = u, |BP | = v and |CP | = w. By the Law of Sines,

sina sinb¢ · sinb sing¢ · sing sina¢ = v u · w v · u w = 1

whence

sinasinbsing = sina¢sinb¢sing¢ .

Now

sinasinbsing = 1 2 [ cos(a- b) - cos(a+ b)]sing = 1 4 [sin(g+ a- b) +sin(b+ g- a) + sin(a+ b- g) - sin(a+ b+ g)]  .

Suppose that a+ b+ g = 90^°. Then

sinasinbsing = 1 4 [sin(90° - 2 a) + sin(90°- 2 b) + sin(90° - 2g) - 1] = 1 4 [cos2a+ cos2b+ cos2g- 1] .

Since also a¢+ b¢+ g¢ = 90^°, a similar identity holds for a¢, b¢ and g¢. Hence

0 = (cos2a- cos2a¢)+ (cos2b- cos2b¢) + (cos2g- cos2g¢) = 2sin60°[sinl+ sinm+ sinn]

where l = a- a¢, m = b- b¢ and n = g- g¢. Note that |l|,|m|, |n| < 60^° and that l+ m+ n = 0.

Now sinl+ sinm = 2sin¹/₂(l+m)cos¹/₂(l- m) = -2 sin[(n)/2]cos[(l-m)/2] and sinn = 2 sin[(n)/2]cos[(n)/2], whence 0 = 2 sin[(n)/2] [ cos[(n)/2] - cos[(l- m)/2]]. Hence n = 0, n = l-m or n = m- l. If n = 0, then g = g¢ and P lies on the bisector of angle C. If l = m+ n, then l = 0 and P lies on the bisector of angle A. If m = l+ n, then m = 0 and P must lie on the angle bisector of the triangle ABC.

Conversely, it is easily checked that any point P on these bisectors satisfies the given condition.

28.

Second solution. [Z. Amir-Khosravi] See Figure 28.2. Let the vertices of the triangle in the complex plane be 1, -1 and Ö3i, and let z be a point on the locus. Then, with the angles as indicated in the diagram and cis  q = cosq+ isinq, we have that

1 - Ö3i 2 = z - Ö3i |z - Ö3i | cis  a

1 = 1 - z |1 - z | cis b

and

Ö3i + 1 2 = z + 1 |z + 1 | cis  g .

Since cis a·cis b·cis g = cis [(p)/2] = i,

1 = i (z - Ö3i)(1 - z2) |z - Ö3i ||1 - z2 |  .

Hence the real part of (z - Ö3i)(1 - z²) is 0, which implies that the real part of z - z³ + Ö3iz² is 0. Setting z = x + yi, we find that

0 = x - x3 + 3xy2 - 2Ö3xy = x[(1 - Ö3y)2 - x2] = x(1 - Ö3y + x)(1 - Ö3y - x) .

Hence (x, y) lies on one of the lines x = 0, y = (1/Ö3)(1 + x), y = (1/Ö3)(1 - x), the three bisectors of the angles. Conversely, one can show that any point on the bisectors lies on the lines.

---

Problem 29.

29.

First solution. (a) One of the angles q of the quadrilateral must be between 90^° and 180^° inclusive so that cosq  £ 0. Let a and b be the lengths of the sides bounding this angle and let u be the length of the diagonal joining the endpoints of these sides (opposite q). Wolog, suppose that a £ b. Then

u2 = a2 + b2 - 2abcosq ³ a2 + b2 ³ 2a2

whence u²/a² ³ 2. Since the largest distance is at least u and the smallest at most a, the result follows.

(b) If ABC is a triangle for which a £ b £ c and C ³ 120^°, then -1 £ cosC £ -1/2 and

c2 = a2 + b2 - 2ab cos120° ³ a2 + b2 + ab ³ 3a2

so that c ³ Ö3a. Thus to prove the result, we need to show that among the six given points, we can find three that are vertices of a (possibly degenerate with three vertices in a line) triangle with one angle at least 120^°, or in other words, a point rays from which to two other points make an angle of at least 120^°.

Consider the smallest closed convex set containing the six points. If all six points are on the boundary, then they are the vertices of a (possibly degenerate) convex hexagon. Since the average interior angle of such a hexagon is 120^°, one of the angles is at least 120^° and we get the desired result.

If the convex set has fewer than six points on the boundary, the remaining point(s) lie in its interior. Triangulate the convex set using only the boundary points; one of the interior points lies inside one of the triangles (possibly on a side), and one of the sides of the triangle must subtend at this point an angle of at least 120^°. Again, the desired result holds.

29.

Second solution. [L. Lessard] Suppose ABC is a triangle with a £ b £ c and 90^° £ C £ 180^°. Then 2A £ A + B = 180^° - C, so that by the Law of Sines,

c a = sinC sinA ³ sinC sin(90° - C/2) = 2sin(C/2)cos(C/2) cos(C/2) = 2sin(C/2) .

If C = 90^°, then c ³ Ö2a and if C ³ 120^°, then c ³ Ö3a. The solution can be completed as before.

---

Problem 30

The specific results

30.

First solution. (a) Taking the difference of the two sides of the inequality yields 3 times

a3 - a2 b - ab2 + b3 = (a2 - b2)(a + b) = (a + b)(a - b)2 ³ 0 .

(b) Using the result in (a), we obtain that

9 (a3 + b3 + c3) = 4(a3 + b3) +4(a3 + c3) + 4(b3 + c3) + (a3 + b3 + c3) ³ (a + b)3 + (a + c)3 + (b + c)3 + (a3 + b3 + c3) = (a + b + c)3 + 2(a3 + b3 + c3) - 6abc ³ (a + b + c)3 + 2(a3 + b3 + c3) - 2(a3 + b3 + c3) = (a + b + c)3  ,

with the last inequality due to that of the arithmetic and geometric means.

30.

Second solution. (b) Since the desired inequality is completely symmetrical in the variables, wolog we may suppose that a ³ b ³ c. Then

a2 (a - b) + b2 (b - c) + c2 (c - a) = (a2 - c2)(a - b) + (b2 - c2)(b - c) ³ 0

and

a2 (a - c) + b2 (b - a) + c2 (c - b) = (a2 - b2)(a - c) + (b2 - c2)(b - c) ³ 0 ,

so that

a3 + b3 + c3 ³ a2 b + b2 c + c2 a

and

a3 + b3 + c3 ³ ab2 + bc2 + ca2 .

Hence

(a + b + c)3 = a3 + b3 + c3+ 3(a2 b + b2 c + c2 a) + 3(ab2 + bc2 + ca2) + 6abc £ a3 + b3 + c3 + 3(a3 + b3 + c3) + 3(a3 + b3 + c3)+ 2(a3 + b3 + c3)

from which the result follows.

The general result

30.

First solution. The Chebyshev Inequality asserts that if x₁ ³ x₂ ³ ¼ ³ x_n ³ 0 and y₁ ³ y₂ ³ ¼ ³ y_n ³ 0, then

n(x1 y1 + x2 y2 + ¼+ xn yn ) ³ (x1 + ¼+ xn)(y1 + ¼+ yn) ,

This can be seen by taking the difference of the two sides which turns out to be the sum of all nonnegative products of the form (x_i - x_j)(y_i - y_j) with i < j.

Using this twice yields

n2 (a13 + ¼+ an3) ³ n (a12 + ¼+ an2)(a1 + ¼+ an) ³ (a1 + ¼+ an)2 (a1 + ¼+ an) = (a1 + ¼+ an)3 ,

30.

Second solution. The power mean inequality asserts that, for k > 1,

a1 + ¼+ an n £ æ ç è a1k + ¼+ ank n ö ÷ ø 1/n    .

Applying this to k = 3 yields the result.

30.

Third solution. By the Cauchy-Schwarz Inequality, we obtain

n2 æ ç è n å i = 1  ai3 ö ÷ ø æ ç è n å i = 0  ai ö ÷ ø ³ n2 æ ç è n å i = 0  ai2 ö ÷ ø 1/2   é ê ë æ ç è n å i = 0  1 ö ÷ ø · æ ç è n å i = 0  ai2 ö ÷ ø ù ú û 2   ³ é ê ë n å i = 1  ai ù ú û 4    .

The result follows.

30.

Comment. L. Lessard began his solution by in effect replacing the original set { a_i } be a set whose elemenets are a little closer to the mean of these numbers.The result holds for n = 1. We assume as an induction hypothesis that it holds for n = K, viz. that

k2 (a13 + a23 + ¼+ ak3) ³ (a1 + a2 + ¼+ ak)3

for all suitable a_i. Apply this to each k-tuple among { a₁, a₂, ¼, a_k+1 } and add the results to obtain

k3 (a13 + a23 + ¼+ ak+13) ³ (S - a1)3 + (S - a2)3 + ¼+ (S - ak+1)3

where S = a₁ + a₂ + ¼+ a_k+1. Let b_i = (S - a_i)/k. Then S = b₁ + b₂ + ¼+ b_k and so

a13 + a23 + ¼+ ak+13 ³ b13 + b23 + ¼+ bk+13 .

This process can be iterated. The idea is that the right side tends under the iterations to a (k+1)-fold sum each terms of which is S/(k+1). But this requires an additional step to show that the maximum of |S - a_i | does indeed decrease sufficiently as to tend to zero as we keep iterating.