26th International Mathematical Olympiad 1985 Problems & Solutions

A1.  A circle has center on the side AB of the cyclic quadrilateral ABCD. The other three sides are tangent to the circle. Prove that AD + BC = AB.

A2.  Let n and k be relatively prime positive integers with k < n. Each number in the set M = {1, 2, 3, ... , n-1} is colored either blue or white. For each i in M, both i and n-i have the same color. For each i in M not equal to k, both i and |i-k| have the same color. Prove that all numbers in M must have the same color.

A3.  For any polynomial P(x) = a₀ + a₁x + ... + a_kx^k with integer coefficients, the number of odd coefficients is denoted by o(P). For i = 0, 1, 2, ... let Q_i(x) = (1 + x)ⁱ. Prove that if i₁, i₂, ... , i_n are integers satisfying 0 ≤ i₁ < i₂ < ... < i_n, then:     o(Q_i1 + Q_i2 + ... + Q_in) ≥ o(Q_i1).

B1.  Given a set M of 1985 distinct positive integers, none of which has a prime divisor greater than 23, prove that M contains a subset of 4 elements whose product is the 4th power of an integer.

B2.  A circle center O passes through the vertices A and C of the triangle ABC and intersects the segments AB and BC again at distinct points K and N respectively. The circumcircles of ABC and KBN intersect at exactly two distinct points B and M. Prove that ∠OMB is a right angle.

B3.  For every real number x₁, construct the sequence x₁, x₂, ... by setting:         x_n+1 = x_n(x_n + 1/n).

Prove that there exists exactly one value of x₁ which gives 0 < x_n < x_n+1 < 1 for all n. 

Solutions

Problem A1

A circle has center on the side AB of the cyclic quadrilateral ABCD. The other three sides are tangent to the circle. Prove that AD + BC = AB.

 

Solution

Let the circle touch AD, CD, BC at L, M, N respectively. Take X on the line AD on the same side of A as D, so that AX = AO, where O is the center of the circle. Now the triangles OLX and OMC are congruent: OL = OM = radius of circle, ∠OLX = ∠OMC = 90^o, and ∠OXL = 90^o - A/2 = (180^o - A)/2 = C/2 (since ABCD is cyclic) = ∠OCM. Hence LX = MC. So OA = AL + MC. Similarly, OB = BN + MD. But MC = CN and MD = DL (tangents have equal length), so AB = OA + OB = AL + LD + CN + NB = AD + BC. 

Problem A2

Let n and k be relatively prime positive integers with k < n. Each number in the set M = {1, 2, 3, ... , n-1} is colored either blue or white. For each i in M, both i and n-i have the same color. For each i in M not equal to k, both i and |i-k| have the same color. Prove that all numbers in M must have the same color.

 

Solution

n and k are relatively prime, so 0, k, 2k, ... , (n-1)k form a complete set of residues mod n. So k, 2k, ... , (n-1)k are congruent to the numbers 1, 2, ... , n-1 in some order. Suppose ik is congruent to r and (i+1)k is congruent to s. Then either s = r + k, or s = r + k - n. If s = r + k, then we have immediately that r = s - k and s have the same color. If s = r + k - n, then r = n - (k - s), so r has the same color as k - s, and k - s has the same color as s. So in any case r and s have the same color. By giving i values from 1 to n-2 this establishes that all the numbers have the same color. 

Problem A3

For any polynomial P(x) = a₀ + a₁x + ... + a_kx^k with integer coefficients, the number of odd coefficients is denoted by o(P). For i = 0, 1, 2, ... let Q_i(x) = (1 + x)ⁱ. Prove that if i₁, i₂, ... , i_n are integers satisfying 0 ≤ i₁ < i₂ < ... < i_n, then:

    o(Q_i1 + Q_i2 + ... + Q_in) ≥ o(Q_i1).

 

Solution

If i is a power of 2, then all coefficients of Q_i are even except the first and last. [There are various ways to prove this. Let iCr denote the rth coefficient, so iCr = i!/(r!(i-r)!). Suppose 0 < r < i. Then iCr = i-1Cr-1 i/r, but i-1Cr-1 is an integer and i is divisible by a higher power of 2 than r, hence iCr is even.]

Let Q = Q_i1 + ... + Q_in. We use induction on i_n. If i_n = 1, then we must have n = 2, i₁ = 0, and i₂ = 1, so Q = 2 + x, which has the same number of odd coefficients as Q_i1 = 1. So suppose it is true for smaller values of i_n. Take m a power of 2 so that m ≤ i_n < 2m. We consider two cases i₁ ≥ m and i₁ < m.

Consider first i₁ ≥ m. Then Q_i1 = (1 + x)^mA, Q = (1 + x)^mB, where A and B have degree less than m. Moreover, A and B are of the same form as Q_i1 and Q, (all the i_js are reduced by m, so we have o(A) ≤ o(B) by induction. Also o(Q_i1) = o((1 + x)^mA) = o(A + x^mA) = 2o(A) ≤ 2o(B) = o(B + x^mB) = o((1 + x)^mB) = o(Q), which establishes the result for i_n.

It remains to consider the case i₁ < m. Take r so that i_r < m, i_r+1 > m. Set A = Q_i1 + ... + Q_ir, (1 + x)^mB = Q_ir+1 + ... + Q_in, so that A and B have degree < m. Then o(Q) = o(A + (1 + x)^mB) = o(A + B + x^mB) = o(A + B) + o(B). Now o(A - B) + o(B) >= o(A - B + B) = o(A), because a coefficient of A is only odd if just one of the corresponding coefficients of A - B and B is odd. But o(A - B) = o(A + B), because corresponding coefficients of A - B and A + B are either equal or of the same parity. Hence o(A + B) + o(B) ≥ o(A). But o(A) ≥ o(Q_ii) by induction. So we have established the result for i_n.  

Problem B1

Given a set M of 1985 distinct positive integers, none of which has a prime divisor greater than 23, prove that M contains a subset of 4 elements whose product is the 4th power of an integer.

 

Solution

Suppose we have a set of at least 3.2ⁿ+1 numbers whose prime divisors are all taken from a set of n. So each number can be written as p₁^r₁...p_n^r_n for some non-negative integers r_i, where p_i is the set of prime factors common to all the numbers. We classify each r_i as even or odd. That gives 2ⁿ possibilities. But there are more than 2ⁿ + 1 numbers, so two numbers have the same classification and hence their product is a square. Remove those two and look at the remaining numbers. There are still more than 2ⁿ + 1, so we can find another pair. We may repeat to find 2ⁿ + 1 pairs with a square product. [After removing 2ⁿ pairs, there are still 2ⁿ + 1 numbers left, which is just enough to find the final pair.] But we may now classify these pairs according to whether each exponent in the square root of their product is odd or even. We must find two pairs with the same classification. The product of these four numbers is now a fourth power.

Applying this to the case given, there are 9 primes less than or equal to 23 (2, 3, 5, 7, 11, 13, 17, 19, 23), so we need at least 3.512 + 1 = 1537 numbers for the argument to work (and we have 1985).

The key is to find the 4th power in two stages, by first finding lots of squares. If we try to go directly to a 4th power, this type of argument does not work (we certainly need more than 5 numbers to be sure of finding four which sum to 0 mod 4, and 5⁹ is far too big). 

Problem B2

A circle center O passes through the vertices A and C of the triangle ABC and intersects the segments AB and BC again at distinct points K and N respectively. The circumcircles of ABC and KBN intersect at exactly two distinct points B and M. Prove that angle OMB is a right angle.

 

Solution

The three radical axes of the three circles taken in pairs, BM, NK and AC are concurrent. Let X be the point of intersection. [They cannot all be parallel or B and M would coincide.] The first step is to show that XMNC is cyclic. The argument depends slightly on how the points are arranged. We may have: ∠XMN = 180^o - ∠BMN = ∠BKN = 180^o - ∠AKN = ∠ACN = 180^o - ∠XCN, or we may have ∠XMN = 180^o - ∠BMN = 180^o - ∠BKN = ∠AKN = 180^o - ∠ACN = 180^o - ∠XCN.

Now XM.XB = XK.XN = XO² - ON². BM·BX = BN·BC = BO² - ON², so XM·XB - BM·BX = XO² - BO². But XM·XB - BM·BX = XB(XM - BM) = (XM + BM)(XM - BM) = XM² - BM². So XO² - BO² = XM² - BM². Hence OM is perpendicular to XB, or ∠OMB = 90^o. 

Problem B3

For every real number x₁, construct the sequence x₁, x₂, ... by setting:

        x_n+1 = x_n(x_n + 1/n).

Prove that there exists exactly one value of x₁ which gives 0 < x_n < x_n+1 < 1 for all n.

 

Solution

Define S₀(x) = x, S_n(x) = S_n-1(x) (S_n-1(x) + 1/n). The motivation for this is that x_n = S_n-1(x₁).

S_n(0) = 0 and S_n(1) > 1 for all n > 1. Also S_n(x) has non-negative coefficients, so it is strictly increasing in the range [0,1]. Hence we can find (unique) solutions a_n, b_n to S_n(a_n) = 1 - 1/n, S_n(b_n) = 1.

S_n+1(a_n) = S_n(a_n) (S_n(a_n) + 1/n) = 1 - 1/n > 1 - 1/(n+1), so a_n < a_n+1. Similarly, S_n+1(b_n) = S_n(b_n) (S_n(b_n) + 1/n) = 1 + 1/n > 1, so b_n > b_n+1. Thus a_n is an increasing sequence and b_n is a decreasing sequence with all a_n less than all b_n. So we can certainly find at least one point x₁ which is greater than all the a_n and less than all the b_n. Hence 1 - 1/n < S_n(x₁) < 1 for all n. But S_n(x₁) = x_n+1. So x_n+1 < 1 for all n. Also x_n > 1 - 1/n implies that x_n+1 = x_n(x_n + 1/n) > x_n. Finally, we obviously have x_n > 0. So the resulting series x_n satisfies all the required conditions.

It remains to consider uniqueness. Suppose that there is an x₁ satisfying the conditions given. Then we must have S_n(x₁) lying in the range 1 - 1/n, 1 for all n. [The lower limit follows from x_n+1 = x_n(x_n + 1/n).] Hence we must have a_n < x₁ < b_n for all n. We show uniqueness by showing that b_n - a_n tends to zero as n tends to infinity. Since all the coefficients of S_n(x) are non-negative, it is has increasing derivative. S_n(0) = 0 and S_n(b_n) = 1, so for any x in the range 0, b_n we have S_n(x) ≤ x/b_n. In particular, 1 - 1/n < a_n/b_n. Hence b_n - a_n ≤ b_n - b_n(1 - 1/n) = b_n/n < 1/n, which tends to zero.

Read more

 

Solutions are also available in     Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

[more...]

25th International Mathematical Olympiad 1984 Problems & Solutions

A1.  Prove that 0 ≤ yz + zx + xy - 2xyz ≤ 7/27, where x, y and z are non-negative real numbers satisfying x + y + z = 1.

A2.  Find one pair of positive integers a, b such that ab(a+b) is not divisible by 7, but (a+b)⁷ - a⁷ - b⁷ is divisible by 7⁷.

A3.  Given points O and A in the plane. Every point in the plane is colored with one of a finite number of colors. Given a point X in the plane, the circle C(X) has center O and radius OX + ∠AOX/OX, where ∠AOX is measured in radians in the range [0, 2π). Prove that we can find a point X, not on OA, such that its color appears on the circumference of the circle C(X).

B1.  Let ABCD be a convex quadrilateral with the line CD tangent to the circle on diameter AB. Prove that the line AB is tangent to the circle on diameter CD if and only if BC and AD are parallel.

B2.  Let d be the sum of the lengths of all the diagonals of a plane convex polygon with n > 3 vertices. Let p be its perimeter. Prove that:     n - 3 < 2d/p < [n/2] [(n+1)/2] - 2, where [x] denotes the greatest integer not exceeding x.

B3.  Let a, b, c, d be odd integers such that 0 < a < b < c < d and ad = bc. Prove that if a + d = 2^k and b + c = 2^m for some integers k and m, then a = 1. 

Solutions

Problem A1

Prove that 0 ≤ yz + zx + xy - 2xyz ≤ 7/27, where x, y and z are non-negative real numbers satisfying x + y + z = 1.

Solution

(1 - 2x)(1 - 2y)(1 - 2z) = 1 - 2(x + y + z) + 4(yz + zx + xy) - 8xyz = 4(yz + zx + xy) - 8xyz - 1. Hence yz + zx + xy - 2xyz = 1/4 (1 - 2x)(1 - 2y)(1 - 2z) + 1/4. By the arithmetic/geometric mean theorem (1 - 2x)(1 - 2y)(1 - 2z) ≤ ((1 - 2x + 1 - 2y + 1 - 2z)/3)³ = 1/27. So yz + zx + xy - 2xyz ≤ 1/4 28/27 = 7/27. 

Problem A2

Find one pair of positive integers a, b such that ab(a+b) is not divisible by 7, but (a+b)⁷ - a⁷ - b⁷ is divisible by 7⁷.

Solution

We find that (a + b)⁷ - a⁷ - b⁷ = 7ab(a + b)(a² + ab + b²)². So we must find a, b such that a² + ab + b² is divisible by 7³.

At this point I found a = 18, b = 1 by trial and error.

A more systematic argument turns on noticing that a² + ab + b² = (a³ - b³)/(a - b), so we are looking for a, b with a³ = b³ (mod 7³). We now remember that a^φ(m) = 1 (mod m). But φ(7³) = 2·3·49, so a³ = 1 (mod 343) if a = n⁹⁸. We find 2⁹⁸ = 18 (343), which gives the solution 18, 1.

This approach does not give a flood of solutions. n⁹⁸ = 0, 1, 18, or 324. So the only solutions we get are 1, 18; 18, 324; 1, 324. 

Problem A3

Given points O and A in the plane. Every point in the plane is colored with one of a finite number of colors. Given a point X in the plane, the circle C(X) has center O and radius OX + (∠AOX)/OX, where ∠AOX is measured in radians in the range [0, 2π). Prove that we can find a point X, not on OA, such that its color appears on the circumference of the circle C(X).

Solution

Suppose the result is false. Let C¹ be any circle center O. Then the locus of points X such that C(X) = C₁ is a spiral from O to the point of intersection of OA and C₁. Every point of this spiral must be a different color from all points of the circle C₁. Hence every circle center O with radius smaller than C₁ must include a point of different color to those on C₁. Suppose there are n colors. Then by taking successively smaller circles C₂, C₃, ... , C_n+1 we reach a contradiction, since each circle includes a point of different color to those on any of the larger circles. 

Problem B1

Let ABCD be a convex quadrilateral with the line CD tangent to the circle on diameter AB. Prove that the line AB is tangent to the circle on diameter CD if and only if BC and AD are parallel.

Solution

If AB and CD are parallel, then AB is tangent to the circle on diameter CD if and only if AB = CD and hence if and only if ABCD is a parallelogram. So the result is true.

Suppose then that AB and DC meet at O. Let M be the midpoint of AB and N the midpoint of CD. Let S be the foot of the perpendicular from N to AB, and T the foot of the perpendicular fromM to CD. We are given that MT = MA. OMT, ONS are similar, so OM/MT = ON/NS and hence OB/OA = (ON - NS)/(ON + NS). So AB is tangent to the circle on diameter CD if and only if OB/OA = OC/OD which is the condition for BC to be parallel to AD. 

Problem B2

Let d be the sum of the lengths of all the diagonals of a plane convex polygon with n > 3 vertices. Let p be its perimeter. Prove that:

    n - 3 < 2d/p < [n/2] [(n+1)/2] - 2, where [x] denotes the greatest integer not exceeding x.

Solution

Given any diagonal AX, let B be the next vertex counterclockwise from A, and Y the next vertex counterclockwise from X. Then the diagonals AX and BY intersect at K. AK + KB > AB and XK + KY > XY, so AX + BY > AB + XY. Keeping A fixed and summing over X gives n - 3 cases. So if we then sum over A we get every diagonal appearing four times on the lhs and every side appearing 2(n-3) times on the rhs, giving 4d > 2(n-3)p.

Denote the vertices as A₀, ... , A_n-1 and take subscripts mod n. The ends of a diagonal AX are connected by r sides and n-r sides. The idea of the upper limit is that its length is less than the sum of the shorter number of sides. Evaluating it is slightly awkward.

We consider n odd and n even separately. Let n = 2m+1. For the diagonal A_iA_i+r with r ≤ m, we have A_iA_i+r ≤ A_iA_i+2 + ... + A_iA_i+r. Summing from r = 2 to m gives for the rhs (m-1)A_iA_i+1 + (m-1)A_i+1A_i+2 + (m-2)A_i+2A_i+3 + (m-3)A_i+3A_i+4 + ... + 1.A_i+m-1A_i+m. Now summing over i gives d for the lhs and p( (m-1) + (1 + 2 + ... + m-1) ) = p( (m² + m - 2)/2 ) for the rhs. So we get 2d/p ≤ m² + m - 2 = [n/2] [(n+1)/2] - 2.

Let n = 2m. As before we have A_iA_i+r <= A_iA_i+2 + ... + A_iA_i+r for 2 ≤ r ≤ m-1. We may also take A_iA_i+m ≤ p/2. Summing as in the even case we get 2d/p = m² - 2 = [n/2] [(n+1)/2] - 2. 

Problem B3

Let a, b, c, d be odd integers such that 0 < a < b < c < d and ad = bc. Prove that if a + d = 2^k and b + c = 2^m for some integers k and m, then a = 1.

Solution

a < c, so a(d - c) < c (d - c) and hence bc - ac < c(d - c). So b - a < d - c, or a + d > b + c, so k > m.

bc = ad, so b(2^m - b) = a(2^k - a). Hence b² - a² = 2^m(b - 2^k-ma). But b² - a² = (b + a)(b - a), and (b + a) and (b - a) cannot both be divisible by 4 (since a and b are odd), so 2^m-1 must divide b + a or b - a. But if it divides b - a, then b - a ≥ 2^m-1, so b and c > 2^m-1 and b + c > 2^m. Contradiction. Hence 2^m-1 divides b + a. If b + a ≥ 2^m = b + c, then a ≥ c. Contradiction. Hence b + a = 2^m-1.

So we have b = 2^m-1 - a, c = 2^m-1 + a, d = 2^k - a. Now using bc = ad gives: 2^ka = 2^2m-2. But a is odd, so a = 1.

Read more

Solutions are also available in     Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

[more...]

24th International Mathematical Olympiad 1983 Problems & Solutions

A1.  Find all functions f defined on the set of positive reals which take positive real values and satisfy:   f(x(f(y)) = yf(x) for all x, y; and f(x) → 0 as x → ∞.

A2.  Let A be one of the two distinct points of intersection of two unequal coplanar circles C₁ and C₂ with centers O₁ and O₂ respectively. One of the common tangents to the circles touches C₁ at P₁ and C₂ at P₂, while the other touches C₁ at Q₁ and C₂ at Q₂. Let M₁ be the midpoint of P₁Q₁ and M₂ the midpoint of P₂Q₂. Prove that ∠O₁AO₂ = ∠M₁AM₂.

A3.  Let a , b and c be positive integers, no two of which have a common divisor greater than 1. Show that 2abc - ab - bc - ca is the largest integer which cannot be expressed in the form xbc + yca + zab, where x, y, z are non-negative integers.

B1.  Let ABC be an equilateral triangle and E the set of all points contained in the three segments AB, BC and CA (including A, B and C). Determine whether, for every partition of E into two disjoint subsets, at least one of the two subsets contains the vertices of a right-angled triangle.

B2.  Is it possible to choose 1983 distinct positive integers, all less than or equal to 10⁵, no three of which are consecutive terms of an arithmetic progression?

B3.  Let a, b and c be the lengths of the sides of a triangle. Prove that     a²b(a - b) + b²c(b - c) + c²a(c - a) ≥ 0.

Determine when equality occurs. 

Solutions

Problem A1

Find all functions f defined on the set of positive reals which take positive real values and satisfy:

  f(x(f(y)) = yf(x) for all x, y; and f(x) → 0 as x → ∞.

 

Solution

If f(k) = 1, then f(x) = f(xf(k)) = kf(x), so k =1. Let y = 1/f(x) and set k = xf(y), then f(k) = f(xf(y)) = yf(x) = 1. Hence f(1) = 1 and f(1/f(x)) = 1/x. Also f(f(y)) = f(1f(y)) = y. Hence f(1/x) = 1/f(x). Finally, let z = f(y), so that f(z) = y. Then f(xy) = f(xf(z)) = zf(x) = f(x)f(y).

Now notice that f(xf(x)) = xf(x). Let k = xf(x). We show that k = 1. f(k²) = f(k)f(k) = k² and by a simple induction f(kⁿ) = kⁿ, so we cannot have k > 1, or f(x) would not tend to 0 as x tends to infinity. But f(1/k) = 1/k and the same argument shows that we cannot have 1/k > 1. Hence k = 1.

So the only such function f is f(x) = 1/x. 

Problem A2

Let A be one of the two distinct points of intersection of two unequal coplanar circles C₁ and C₂ with centers O₁ and O₂ respectively. One of the common tangents to the circles touches C₁ at P₁ and C₂ at P₂, while the other touches C₁ at Q₁ and C₂ at Q₂. Let M₁ be the midpoint of P₁Q₁ and M₂ the midpoint of P₂Q₂. Prove that ∠O₁AO₂ = ∠M₁AM₂.

 

Solution

Let P₁P₂ and O₁O₂ meet at O. Let OA meet C₂ again at A₂. O is the center of similitude for C₁ and C₂ so ∠M₁AO₁ = ∠M₂A₂O₂. Hence if we can show that ∠M₂AO₂ = ∠M₂A₂O₂, then we are home.

Let X be the other point of intersection of the two circles. The key is to show that A₂, M₂ and X are collinear, for then ∠M₂AO₂ = ∠M₂XO₂ (by reflection) and O₂A₂X is isosceles.

But since O is the center of similitude, M₂A₂ is parallel to M₁A, and by reflection ∠XM₂O = ∠AM₂O, so we need to show that triangle AM₁M₂ is isosceles. Extend XA to meet P₁P₂ at Y. Then YP₁² = YA.YX = YP₂², so YX is the perpendicular bisector of M₁M₂, and hence AM₁ = AM₂ as required. 

Problem A3

Let a , b and c be positive integers, no two of which have a common divisor greater than 1. Show that 2abc - ab - bc - ca is the largest integer which cannot be expressed in the form xbc + yca + zab, where x, y, z are non-negative integers.

 

Solution

We start with the lemma that bc - b - c is the largest number which cannot be written as mb + nc with m and n non-negative. [Proof: 0, c, 2c, ... , (b-1)c is a complete set of residues mod b. If r > (b-1)c - b, then r = nc (mod b) for some 0 ≤ n ≤ b-1. But r > nc - b, so r = nc + mb for some m ≥ 0. That proves that every number larger than bc - b - c can be written as mb + nc with m and n non-negative. Now consider bc - b - c. It is (b-1)c (mod b), and not congruent to any nc with 0 ≤ n < b-1. So if bc - b - c = mb + nc, then n ≥ b-1. Hence mb + nc ≥ nc ≥ (b-1)c > bc - b - c. Contradiction.]

0, bc, 2bc, ... , (a-1)bc is a complete set of residues mod a. So given N > 2abc - ab - bc - ca we may take xbc = N (mod a) with 0 <= x < a. But N - xbc > 2abc - ab - bc - ca - (a-1)bc = abc - ab - ca = a(bc - b - c). So N - xbc = ka, with k > bc - b - c. Hence we can find non-negative y, z so that k = zb + yc. Hence N = xbc + yca + zab.

Finally, we show that for N = 2abc - ab - bc - ca we cannot find non-negative x, y, z so that N = xbc + yca + zab. N = -bc (mod a), so we must have x = -1 (mod a) and hence x ≥ a-1. Similarly, y ≥ b-1, and z ≥ c-1. Hence xbc + yca + zab ≥ 3abc - ab - bc - ca > N. Contradiction. 

Problem B1

Let ABC be an equilateral triangle and E the set of all points contained in the three segments AB, BC and CA (including A, B and C). Determine whether, for every partition of E into two disjoint subsets, at least one of the two subsets contains the vertices of a right-angled triangle.

 

Solution

It does.

Suppose otherwise, that E is the disjoint union of e and e' with no right-angled triangles in either set. Take points X, Y, Z two-thirds of the way along BC, CA, AB respectively (so that BX/BC = 2/3 etc). Then two of X, Y, Z must be in the same set. Suppose X and Y are in e. Now YX is perpendicular to BC, so all points of BC apart from X must be in e'. Take W to be the foot of the perpendicular from Z to BC. Then B and W are in e', so Z must be in e. ZY is perpendicular to AC, so all points of AC apart from Y must be in e'. e' is now far too big. For example let M be the midpoint of BC, then AMC is in e' and right-angled. 

Problem B2

Is it possible to choose 1983 distinct positive integers, all less than or equal to 10⁵, no three of which are consecutive terms of an arithmetic progression?

 

Solution

We may notice that an efficient way to build up a set with no APs length 3 is as follows. Having found 2ⁿ numbers in {1, 2, ... , u_n} we add the same pattern starting at 2u_n, thus giving 2ⁿ⁺¹ numbers in {1, 2, ... , 3u_n-1}. If x is in the first part and y, z in the second part, then 2y is at least 4u_n, whereas x + z is less than 4u_n, so x, y, z cannot be an AP length 3. If x and y are in the first part, and z in the second part, then 2y is at most 2u_n, but x + z is more than 2u_n, so x, y, z cannot be an AP length 3. To start the process off, we have the 4 numbers 1, 2, 4, 5 in {1, 2, 3, 4, 5}. So u₂ = 5. This gives u₁₁ = 88574, in other words we can find 2048 numbers in the first 88574 with no AP length 3.

If we are lucky, we may notice that if we reduce each number in the set we have constructed by 1 we get the numbers which have no 2 when written base 3. This provides a neater approach. Take x, y, z with no 2 when written in base 3. Then 2y has only 0s and 2s when written base 3. But x + z only has no 1s if x = z. So x, y, z cannot form an AP length 3. Also there are 2¹¹ = 2048 numbers of this type with 11 digits or less and hence ≤ 11111111111₃ = 88573. 

Problem B3

Let a, b and c be the lengths of the sides of a triangle. Prove that

    a²b(a - b) + b²c(b - c) + c²a(c - a) ≥ 0.

Determine when equality occurs.

 

Solution

Put a = y + z, b = z + x, c = x + y. Then the triangle condition becomes simply x, y, z > 0. The inequality becomes (after some manipulation):

    xy³ + yz³ + zx³ ≥ xyz(x + y + z).

Applying Cauchy's inequality we get (xy³ + yz³ + zx³)(z + x + y) ≥ xyz(y + z + x)² with equality iff xy³/z = yz³/x = zx³/y. So the inequality holds with equality iff x = y = z. Thus the original inequality holds with equality iff the triangle is equilateral.

Read more

 

Solutions are also available in     Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

[more...]

23rd International Mathematical Olympiad 1982 Problems & Solutions

A1.  The function f(n) is defined on the positive integers and takes non-negative integer values. f(2) = 0, f(3) > 0, f(9999) = 3333 and for all m, n:       f(m+n) - f(m) - f(n) = 0 or 1.

Determine f(1982).

A2.  A non-isosceles triangle A₁A₂A₃ has sides a₁, a₂, a₃ with a_i opposite A_i. M_i is the midpoint of side a_i and T_i is the point where the incircle touches side a_i. Denote by S_i the reflection of T_i in the interior bisector of angle A_i. Prove that the lines M₁S₁, M₂S₂ and M₃S₃ are concurrent.

A3.  Consider infinite sequences {x_n} of positive reals such that x₀ = 1 and x₀ ≥ x₁ ≥ x₂ ≥ ... . (a)  Prove that for every such sequence there is an n ≥ 1 such that:

      x₀²/x₁ + x₁²/x₂ + ... + x_n-1²/x_n ≥ 3.999.

(b)  Find such a sequence for which:

      x₀²/x₁ + x₁²/x₂ + ... + x_n-1²/x_n < 4   for all n.

B1.  Prove that if n is a positive integer such that the equation       x³ - 3xy² + y³ = n

has a solution in integers x, y, then it has at least three such solutions. Show that the equation has no solutions in integers for n = 2891.

B2.  The diagonals AC and CE of the regular hexagon ABCDEF are divided by inner points M and N respectively, so that:       AM/AC = CN/CE = r.

Determine r if B, M and N are collinear.

B3.  Let S be a square with sides length 100. Let L be a path within S which does not meet itself and which is composed of line segments A₀A₁, A₁A₂, A₂A₃, ... , A_n-1A_n with A₀ = A_n. Suppose that for every point P on the boundary of S there is a point of L at a distance from P no greater than 1/2. Prove that there are two points X and Y of L such that the distance between X and Y is not greater than 1 and the length of the part of L which lies between X and Y is not smaller than 198. 

Solutions

Problem A1

The function f(n) is defined on the positive integers and takes non-negative integer values. f(2) = 0, f(3) > 0, f(9999) = 3333 and for all m, n:

      f(m+n) - f(m) - f(n) = 0 or 1.

Determine f(1982).

 

Solution

We show that f(n) = [n/3] for n <= 9999, where [ ] denotes the integral part.

We show first that f(3) = 1. f(1) must be 0, otherwise f(2) - f(1) - f(1) would be negative. Hence f(3) = f(2) + f(1) + 0 or 1 = 0 or 1. But we are told f(3) > 0, so f(3) = 1. It follows by induction that f(3n) ≥ n. For f(3n+3) = f(3) + f(3n) + 0 or 1 = f(3n) + 1 or 2. Moreover if we ever get f(3n) > n, then the same argument shows that f(3m) > m for all m > n. But f(3.3333) = 3333, so f(3n) = n for all n <= 3333.

Now f(3n+1) = f(3n) + f(1) + 0 or 1 = n or n + 1. But 3n+1 = f(9n+3) ≥ f(6n+2) + f(3n+1) ≥ 3f(3n+1), so f(3n+1) < n+1. Hence f(3n+1) = n. Similarly, f(3n+2) = n. In particular f(1982) = 660. 

Problem A2

A non-isosceles triangle A₁A₂A₃ has sides a₁, a₂, a₃ with a_i opposite A_i. M_i is the midpoint of side a_i and T_i is the point where the incircle touches side a_i. Denote by S_i the reflection of T_i in the interior bisector of ∠A_i. Prove that the lines M₁S₁, M₂S₂ and M₃S₃ are concurrent.

 

Solution

Let B_i be the point of intersection of the interior angle bisector of the angle at A_i with the opposite side. The first step is to figure out which side of B_i T_i lies. Let A₁ be the largest angle, followed by A₂. Then T₂ lies between A₁ and B₂, T₃ lies between A₁ and B₃, and T₁ lies between A₂ and B₁. For ∠OB₂A₁ = 180^o - A₁ - A₂/2 = A₃ + A₂/2. But A₃ + A₂/2 < A₁ + A₂/2 and their sum is 180^o, so A₃ + A₂/2 < 90^o. Hence T₂ lies between A₁ and B₂. Similarly for the others.

Let O be the center of the incircle. Then ∠T₁OS₂ = ∠T₁OT₂ - 2 ∠T₂OB₂ = 180^o - A₃ - 2(90^o - ∠OB₂T₂) = 2(A₃ + A₂/2) - A₃ = A₂ + A₃. A similar argument shows ∠T₁OS₃ = A₂ + A₃. Hence S₂S₃ is parallel to A₂A₃.

Now ∠T₃OS₂ = 360^o - ∠T₃OT₁ - ∠T₁OS₂ = 360^o - (180^o - A₂) - (A₂ + A₃) = 180^o - A₃ = A₁ + A₂. ∠T₃OS₁ = ∠T₃OT₁ + 2 ∠T₁OB₁ = (180^o - A₂) + 2(90^o - ∠OB₁T₁) = 360^o - A₂ - 2(A₃ + A₁/2) = 2(A₁ + A₂ + A₃) - A₂ - 2A₃ - A₁ = A₁ + A₂ = ∠T₃OS₂. So S₁S₂ is parallel to A₁A₂. Similarly we can show that S₁S₃ is parallel to A₁A₃.

So S₁S₂S₃ is similar to A₁A₂A₃ and turned through 180^o. But M₁M₂M₃ is also similar to A₁A₂A₃ and turned through 180^o. So S₁S₂S₃ and M₁M₂M₃ are similar and similarly oriented. Hence the lines through corresponding vertices are concurrent. 

Problem A3

Consider infinite sequences {x_n} of positive reals such that x₀ = 1 and x₀ ≥= x₁ ≥ x₂ ≥ ... .

(a)  Prove that for every such sequence there is an n ≥ 1 such that:

      x₀²/x₁ + x₁²/x₂ + ... + x_n-1²/x_n ≥ 3.999.

(b)  Find such a sequence for which:

      x₀²/x₁ + x₁²/x₂ + ... + x_n-1²/x_n < 4   for all n.

 

Solution

(a)  It is sufficient to show that the sum of the (infinite) sequence is at least 4. Let k be the greatest lower bound of the limits of all such sequences. Clearly k ≥ 1. Given any ε > 0, we can find a sequence {x_n} with sum less than k + ε. But we may write the sum as:

x₀²/x₁ + x₁( (x₁/x₁)²/(x₂/x₁) + (x₂/x₁)²/(x₃/x₁) + ... + (x_n/x₁)²/(x_n+1/x₁) + ... ).

The term in brackets is another sum of the same type, so it is at least k. Hence k + ε > 1/x₁ + x₁k. This holds for all ε > 0, and so k ≥ 1/x₁ + x₁k. But 1/x₁ + x₁k ≥ 2√k, so k ≥ 4.

(b)  Let x_n = 1/2ⁿ. Then x₀²/x₁ + x₁²/x₂ + ... + x_n-1²/x_n = 2 + 1 + 1/2 + ... + 1/2^n-2 = 4 - 1/2^n-2 < 4. 

Problem B1

Prove that if n is a positive integer such that the equation

      x³ - 3xy² + y³ = n

has a solution in integers x, y, then it has at least three such solutions. Show that the equation has no solutions in integers for n = 2891.

 

Solution

If x, y is a solution then so is y-x, -x. Hence also -y, x-y. If the first two are the same, then y = -x, and x = y-x = -2x, so x = y = 0, which is impossible, since n > 0. Similarly, if any other pair are the same.

2891 = 2 (mod 9) and there is no solution to x³ - 3xy² + y³ = 2 (mod 9). The two cubes are each -1, 0 or 1, and the other term is 0, 3 or 6, so the only solution is to have the cubes congruent to 1 and -1 and the other term congruent to 0. But the other term cannot be congruent to 0, unless one of x, y is a multiple of 3, in which case its cube is congruent to 0, not 1 or -1. 

Problem B2

The diagonals AC and CE of the regular hexagon ABCDEF are divided by inner points M and N respectively, so that:

      AM/AC = CN/CE = r.

Determine r if B, M and N are collinear.

 

Solution

For an inelegant solution one can use coordinates. The advantage of this type of approach is that it is quick and guaranteed to work! Take A as (0,√3), B as (1,√3), C as (3/2,√3/2, D as (1,0). Take the point X, coordinates (x,0), on ED. We find where the line BX cuts AC and CE. The general point on BX is (k + (1-k)x,k√3). If this is also the point M with AM/AC = r then we have: k + (1-k)x = 3r/2, k√3 = (1-r)√3 + r√3/2. Hence k = 1 - r/2, r = 2/(4-x). Similarly, if it is the point N with CN/CE = r, then k + (1-k)x = 3(1-r)/2, k√3 = (1-r)√3/2. Hence k = (1-r)/2 and r = (2-x)/(2+x). Hence for the ratios to be equal we require 2/(4-x) = (2-x)/(2+x), so x² - 8x + 4 = 0. We also have x < 1, so x = 4 - √12. This gives r = 1/√3.

A more elegant solution uses the ratio theorem for the triangle EBC. We have CM/MX XB/BE EN/NC = -1. Hence (1-r)/(r - 1/2) (-1/4) (1-r)/r = -1. So r = 1/√3. 

Problem B3

Let S be a square with sides length 100. Let L be a path within S which does not meet itself and which is composed of line segments A₀A₁, A₁A₂, A₂A₃, ... , A_n-1A_n with A₀ = A_n. Suppose that for every point P on the boundary of S there is a point of L at a distance from P no greater than 1/2. Prove that there are two points X and Y of L such that the distance between X and Y is not greater than 1 and the length of the part of L which lies between X and Y is not smaller than 198.

 

Solution

Let the square be A'B'C'D'. The idea is to find points of L close to a particular point of A'D' but either side of an excursion to B'.

We say L approaches a point P' on the boundary of the square if there is a point P on L with PP' ≤ 1/2. We say L approaches P' before Q' if there is a point P on L which is nearer to A₀ (the starting point of L) than any point Q with QQ' ≤ 1/2.

Let A' be the first vertex of the square approached by L. L must subsequently approach both B' and D'. Suppose it approaches B' first. Let B be the first point on L with BB' ≤ 1/2. We can now divide L into two parts L₁, the path from A₀ to B, and L₂, the path from B to A_n.

Take X' to be the point on A'D' closest to D' which is approached by L₁. Let X be the corresponding point on L₁. Now every point on X'D' must be approached by L₂ (and X'D' is non-empty, because we know that D' is approached by L but not by L₁). So by compactness X' itself must be approached by L₂. Take Y to be the corresponding point on L₂. XY ≤ XX' + X'Y ≤ 1/2 + 1/2 = 1. Also BB' ≤ 1/2, so XB ≥ X'B' - XX' - BB' ≥ X'B' - 1 ≥ A'B' - 1 = 99. Similarly YB ≥ 99, so the path XY ≥ 198.

Read more

 

Solutions are also available in     Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

[more...]

22nd International Mathematical Olympiad 1981 Problems & Solutions

A1.  P is a point inside the triangle ABC. D, E, F are the feet of the perpendiculars from P to the lines BC, CA, AB respectively. Find all P which minimise:         BC/PD + CA/PE + AB/PF.

A2.  Take r such that 1 ≤ r ≤ n, and consider all subsets of r elements of the set {1, 2, ... , n}. Each subset has a smallest element. Let F(n,r) be the arithmetic mean of these smallest elements. Prove that:         F(n,r) = (n+1)/(r+1).

A3.  Determine the maximum value of m² + n², where m and n are integers in the range 1, 2, ... , 1981 satisfying (n² - mn - m²)² = 1.

B1. (a)  For which n > 2 is there a set of n consecutive positive integers such that the largest number in the set is a divisor of the least common multiple of the remaining n - 1 numbers? (b)  For which n > 2 is there exactly one set having this property?

B2.  Three circles of equal radius have a common point O and lie inside a given triangle. Each circle touches a pair of sides of the triangle. Prove that the incenter and the circumcenter of the triangle are collinear with the point O.

B3.  The function f(x,y) satisfies: f(0,y) = y + 1, f(x+1,0) = f(x,1), f(x+1,y+1) = f(x,f(x+1,y)) for all non-negative integers x, y. Find f(4, 1981). 

Solutions

Problem A1

P is a point inside the triangle ABC. D, E, F are the feet of the perpendiculars from P to the lines BC, CA, AB respectively. Find all P which minimise:

        BC/PD + CA/PE + AB/PF.

 

Solution

We have PD.BC + PE.CA + PF.AB = 2 area of triangle. Now use Cauchy's inequality with x₁ = √(PD·BC), x₂ = √(PE·CA), x₃ = √(PF·AB), and y₁ = √(BC/PD), y₂ = √(CA/PE), y₃ = √(AB/PF). We get that (BC + CA + AB)² < 2 x area of triangle x (BC/PD + CA/PE + AB/PF) with equality only if x_i/y_i = const, ie PD = PE = PF. So the unique minimum position for P is the incenter. 

Problem A2

Take r such that 1 ≤ r ≤ n, and consider all subsets of r elements of the set {1, 2, ... , n}. Each subset has a smallest element. Let F(n,r) be the arithmetic mean of these smallest elements. Prove that:

        F(n,r) = (n+1)/(r+1).

 

Solution

Denote the binomial coefficient n!/(r!(n-r)!) by nCr.

Evidently nCr F(n,r) = 1 (n-1)C(r-1) + 2 (n-2)C(r-1) + ... + (n-r+1) (r-1)C(r-1). [The first term denotes the contribution from subsets with smallest element 1, the second term smallest element 2 and so on.]

Let the rhs be g(n,r). Then, using the relation (n-i)C(r-1) - (n-i-1)C(r-2) = (n-i-1)C(r-1), we find that g(n,r) - g(n-1,r-1) = g(n-1,r), and we can extend this relation to r=1 by taking g(n,0) = n+1 = (n+1)C1. But g(n,1) = 1 + 2 + ... + n = n(n+1)/2 = (n+1)C2. So it now follows by an easy induction that g(n,r) = (n+1)C(r+1) = nCr (n+1)/(r+1). Hence F(n,r) = (n+1)/(r+1).

A more elegant solution by Oliver Nash is as follows

Let k be the smallest element. We want to evaluate g(n, r) = ∑_{k=1 to n-r+1} k   (n-k)C(r-1). Consider the subsets with r+1 elements taken from 1, 2, 3, ... , n+1. Suppose k+1 is the second smallest element. Then there are k   (n-k)C(r-1) possible subsets. So g(n, r) = (n+1)C(r+1). Hence F(n, r) = (n+1)C(r+1) / nCr = (n+1)/(r+1), as required. 

Problem A3

Determine the maximum value of m² + n², where m and n are integers in the range 1, 2, ... , 1981 satisfying (n² - mn - m²)² = 1.

 

Solution

Experimenting with small values suggests that the solutions of n² - mn - m² = 1 or -1 are successive Fibonacci numbers. So suppose n > m is a solution. This suggests trying m+n, n: (m+n)² - (m+n)n - n² = m² + mn - n² = -(n² - mn - m²) = 1 or -1. So if n > m is a solution, then m+n, n is another solution. Running this forward from 2,1 gives 3,2; 5,3; 8,5; 13,8; 21,13; 34,21; 55,34; 89,55; 144,89; 233,144; 377,233; 610,377; 987,610; 1597,987; 2584,1597.

But how do we know that there are no other solutions? The trick is to run the recurrence the other way. For suppose n > m is a solution, then try m, n-m: m² - m(n-m) - (n-m)² = m² + mn - n² = -(n² - mn - m²) = 1 or -1, so that also satisfies the equation. Also if m > 1, then m > n-m (for if not, then n >= 2m, so n(n - m) >= 2m², so n² - nm - m² >= m² > 1). So given a solution n > m with m > 1, we have a smaller solution m > n-m. This process must eventually terminate, so it must finish at a solution n, 1 with n > 1. But the only such solution is 2, 1. Hence the starting solution must have been in the forward sequence from 2, 1.

Hence the solution to the problem stated is 1597² + 987². 

Problem B1

(a)  For which n > 2 is there a set of n consecutive positive integers such that the largest number in the set is a divisor of the least common multiple of the remaining n - 1 numbers?

(b)  For which n > 2 is there exactly one set having this property?

 

Solution

(a)  n = 3 is not possible. For suppose x was the largest number in the set. Then x cannot be divisible by 3 or any larger prime, so it must be a power of 2. But it cannot be a power of 2, because 2^m - 1 is odd and 2^m - 2 is not a positive integer divisible by 2^m.

For k ≥ 2, the set 2k-1, 2k , ... , 4k-2 gives n = 2k. For k ≥ 3, so does the set 2k-5, 2k-4, ... , 4k-6. For k ≥ 2, the set 2k-2, 2k-3, ... , 4k-2 gives n = 2k+1. For k ≥ 4 so does the set 2k-6,2k-5, ... , 4k-6. So we have at least one set for every n ≥ 4, which answers (a).

(b)  We also have at least two sets for every n ≥ 4 except possibly n = 4, 5, 7. For 5 we may take as a second set: 8, 9, 10, 11, 12, and for 7 we may take 6, 7, 8, 9 ,10, 11, 12. That leaves n = 4. Suppose x is the largest number in a set with n =4. x cannot be divisible by 5 or any larger prime, because x-1, x-2, x-3 will not be. Moreover, x cannot be divisible by 4, because then x-1 and x-3 will be odd, and x-2 only divisible by 2 (not 4). Similarly, it cannot be divisible by 9. So the only possibilities are 1, 2, 3, 6. But we also require x ≥ 4, which eliminates the first three. So the only solution for n = 4 is the one we have already found: 3, 4, 5, 6. 

Problem B2

Three circles of equal radius have a common point O and lie inside a given triangle. Each circle touches a pair of sides of the triangle. Prove that the incenter and the circumcenter of the triangle are collinear with the point O.

 

Solution

Let the triangle be ABC. Let the center of the circle touching AB and AC be D, the center of the circle touching AB and BC be E, and the center of the circle touching AC and BC be F. Because the circles center D and E have the same radius the perpendiculars from D and E to AB have the same length, so DE is parallel to AB. Similarly EF is parallel to BC and FD is parallel to CA. Hence DEF is similar and similarly oriented to ABC. Moreover D must lie on the angle bisector of A since the circle center D touches AB and AC. Similarly E lies on the angle bisector of B and F lies on the angle bisector of C. Hence the incenter I of ABC is also the incenter of DEF and acts as a center of symmetry so that corresponding points P of ABC and P' of DEF lie on a line through I with PI/P'I having a fixed ratio. But OD = OE = OF since the three circles have equal radii, so O is the circumcenter of DEF. Hence it lies on a line with I and the circumcenter of ABC. 

Problem B3

The function f(x,y) satisfies: f(0,y) = y + 1, f(x+1,0) = f(x,1), f(x+1,y+1) = f(x,f(x+1,y)) for all non-negative integers x, y. Find f(4, 1981).

 

Solution

f(1,n) = f(0,f(1,n-1)) = 1 + f(1,n-1). So f(1,n) = n + f(1,0) = n + f(0,1) = n + 2.

f(2,n) = f(1,f(2,n-1)) = f(2,n-1) + 2. So f(2,n) = 2n + f(2,0) = 2n + f(1,1) = 2n + 3.

f(3,n) = f(2,f(3,n-1)) = 2f(3,n-1) + 3. Let u_n = f(3,n) + 3, then u_n = 2u_n-1. Also u₀ = f(3,0) + 3 = f(2,1) + 3 = 8. So u_n = 2ⁿ⁺³, and f(3,n) = 2ⁿ⁺³ - 3.

f(4,n) = f(3,f(4,n-1)) = 2^f(4,n-1)+3 - 3. f(4,0) = f(3,1) = 2⁴ - 3 = 13. We calculate two more terms to see the pattern: f(4,1) = 2²⁴ - 3, f(4,2) = 2²²⁴ - 3. In fact it looks neater if we replace 4 by 2², so that f(4,n) is a tower of n+3 2s less 3.

Read more

Solutions are also available in     Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

[more...]

21st International Mathematical Olympiad 1979 Problems & Solutions

A1.  Let m and n be positive integers such that:       m/n = 1 - 1/2 + 1/3 - 1/4 + ... - 1/1318 + 1/1319.

Prove that m is divisible by 1979.

A2.  A prism with pentagons A₁A₂A₃A₄A₅ and B₁B₂B₃B₄B₅ as the top and bottom faces is given. Each side of the two pentagons and each of the 25 segments A_iB_j is colored red or green. Every triangle whose vertices are vertices of the prism and whose sides have all been colored has two sides of a different color. Prove that all 10 sides of the top and bottom faces have the same color.

A3.  Two circles in a plane intersect. A is one of the points of intersection. Starting simultaneously from A two points move with constant speed, each traveling along its own circle in the same sense. The two points return to A simultaneously after one revolution. Prove that there is a fixed point P in the plane such that the two points are always equidistant from P.

B1.  Given a plane k, a point P in the plane and a point Q not in the plane, find all points R in k such that the ratio (QP + PR)/QR is a maximum.

B2.  Find all real numbers a for which there exist non-negative real numbers x₁, x₂, x₃, x₄, x₅ satisfying:   x₁ + 2x₂ + 3x₃ + 4x₄ + 5x₅ = a,

  x₁ + 2³x₂ + 3³x₃ + 4³x₄ + 5³x₅ = a²,

  x₁ + 2⁵x₂ + 3⁵x₃ + 4⁵x₄ + 5⁵x₅ = a³.

B3.  Let A and E be opposite vertices of an octagon. A frog starts at vertex A. From any vertex except E it jumps to one of the two adjacent vertices. When it reaches E it stops. Let a_n be the number of distinct paths of exactly n jumps ending at E. Prove that:       a_2n-1 = 0

      a_2n = (2 + √2)^n-1/√2 - (2 - √2)^n-1/√2. 

Solutions

Problem A1

Let m and n be positive integers such that:

      m/m = 1 - 1/2 + 1/3 - 1/4 + ... - 1/1318 + 1/1319.

Prove that m is divisible by 1979.

 

Solution

This is difficult.

The obvious step of combining adjacent terms to give 1/(n(n+1) is unhelpful. The trick is to separate out the negative terms:

    1 - 1/2 + 1/3 - 1/4 + ... - 1/1318 + 1/1319 = 1 + 1/2 + 1/3 + ... + 1/1319 - 2(1/2 + 1/4 + ... + 1/1318) = 1/660 + 1/661 + ... + 1/1319.

and to notice that 660 + 1319 = 1979. Combine terms in pairs from the outside:

    1/660 + 1/1319 = 1979/(660.1319); 1/661 + 1/1318 = 1979/(661.1318) etc.

There are an even number of terms, so this gives us a sum of terms 1979/m with m not divisible by 1979 (since 1979 is prime and so does not divide any product of smaller numbers). Hence the sum of the 1/m gives a rational number with denominator not divisible by 1979 and we are done. 

Problem A2

A prism with pentagons A₁A₂A₃A₄A₅ and B₁B₂B₃B₄B₅ as the top and bottom faces is given. Each side of the two pentagons and each of the 25 segments A_iB_j is colored red or green. Every triangle whose vertices are vertices of the prism and whose sides have all been colored has two sides of a different color. Prove that all 10 sides of the top and bottom faces have the same color.

 

Solution

We show first that the A_i are all the same color. If not then, there is a vertex, call it A₁, with edges A₁A₂, A₁A₅ of opposite color. Now consider the five edges A₁B_i. At least three of them must be the same color. Suppose it is green and that A₁A₂ is also green. Take the three edges to be A₁B_i, A₁B_j, A₁B_k. Then considering the triangles A₁A₂B_i, A₁A₂B_j, A₁A₂B_k, the three edges A₂B_i, A₂B_j, A₂B_k must all be red. Two of B_i, B_j, B_k must be adjacent, but if the resulting edge is red then we have an all red triangle with A₂, whilst if it is green we have an all green triangle with A₁. Contradiction. So the A_i are all the same color. Similarly, the B_i are all the same color. It remains to show that they are the same color. Suppose otherwise, so that the A_i are green and the B_i are red.

Now we argue as before that 3 of the 5 edges A₁B_i must be the same color. If it is red, then as before 2 of the 3 B_i must be adjacent and that gives an all red triangle with A₁. So 3 of the 5 edges A₁B_i must be green. Similarly, 3 of the 5 edges A₂B_i must be green. But there must be a B_i featuring in both sets and it forms an all green triangle with A₁ and A₂. Contradiction. So the A_i and the B_i are all the same color. 

Problem A3

Two circles in a plane intersect. A is one of the points of intersection. Starting simultaneously from A two points move with constant speed, each traveling along its own circle in the same sense. The two points return to A simultaneously after one revolution. Prove that there is a fixed point P in the plane such that the two points are always equidistant from P.

 

Solution

Let the circles have centers O, O' and let the moving points by X, X. Let P be the reflection of A in the perpendicular bisector of OO'. We show that triangles POX, X'O'P are congruent. We have OX = OA (pts on circle) = O'P (reflection). Also OP = O'A (reflection) = O'X' (pts on circle). Also ∠AOX = ∠AO'X' (X and X' circle at same rate), and ∠AOP = ∠AO'P (reflection), so ∠POX = ∠PO'X'. So the triangles are congruent. Hence PX = PX'.

Another approach is to show that XX' passes through the other point of intersection of the two circles, but that involves looking at many different cases depending on the relative positions of the moving points.

Problem B1

Given a plane k, a point P in the plane and a point Q not in the plane, find all points R in k such that the ratio (QP + PR)/QR is a maximum.

 

Solution

Consider the points R on a circle center P. Let X be the foot of the perpendicular from Q to k. Assume P is distinct from X, then we minimise QR (and hence maximise (QP + PR)/QR) for points R on the circle by taking R on the line PX. Moreover, R must lie on the same side of P as X. Hence if we allow R to vary over k, the points maximising (QP + PR)/QR must lie on the ray PX. Take S on the line PX on the opposite side of P from X so that PS = PQ. Then for points R on the ray PX we have (QP + PR)/QR = SR/QR = sin RQS/sin QSR. But sin QSR is fixed for points on the ray, so we maximise the ratio by taking ∠RQS = 90^o. Thus there is a single point maximising the ratio.

If P = X, then we still require ∠RQS = 90^o, but R is no longer restricted to a line, so it can be anywhere on a circle center P. 

Problem B2

Find all real numbers a for which there exist non-negative real numbers x₁, x₂, x₃, x₄, x₅ satisfying:

  x₁ + 2x₂ + 3x₃ + 4x₄ + 5x₅ = a,
  x₁ + 2³x₂ + 3³x₃ + 4³x₄ + 5³x₅ = a²,
  x₁ + 2⁵x₂ + 3⁵x₃ + 4⁵x₄ + 5⁵x₅ = a³.

 

Solution

Take a² x 1st equ - 2a x 2nd equ + 3rd equ. The rhs is 0. On the lhs the coefficient of x_n is a²n - 2an³ + n⁵ = n(a - n²)². So the lhs is a sum of non-negative terms. Hence each term must be zero separately, so for each n either x_n = 0 or a = n². So there are just 5 solutions, corresponding to a = 1, 4, 9, 16, 25. We can check that each of these gives a solution. [For a = n², x_n = n and the other x_i are zero.] 

Problem B3

Let A and E be opposite vertices of an octagon. A frog starts at vertex A. From any vertex except E it jumps to one of the two adjacent vertices. When it reaches E it stops. Let a_n be the number of distinct paths of exactly n jumps ending at E. Prove that:

      a_2n-1 = 0
      a_2n = (2 + √2)^n-1/√2 - (2 - √2)^n-1/√2.

 

Solution

Each jump changes the parity of the shortest distance to E. The parity is initially even, so an odd number of jumps cannot end at E. Hence a_2n-1 = 0.

We derive a recurrence relation for a_2n. This is not easy to do directly, so we introduce b_n which is the number of paths length n from C to E. Then we have immediately:

    a_2n = 2a_2n-2 + 2b_2n-2 for n > 1
    b_2n = 2b_2n-2 + a_2n-2 for n > 1

Hence, using the first equation: a_2n - 2a_2n-2 = 2a_2n-2 - 4a_2n-4 + 2b_2n-2 - 4b_2n-4 for n > 2. Using the second equation, this leads to: a_2n = 4a_2n-2 - 2a_2n-4 for n > 2. This is a linear recurrence relation with the general solution: a_2n = a(2 + √2)^n-1 + b(2 - √2)^n-1. But we easily see directly that a₄ = 2, a₆ = 8 and we can now solve for the coefficients to get the solution given. 

Read more

Solutions are also available in     Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

[more...]

20th International Mathematical Olympiad 1978 Problems & Solutions

A1.  m and n are positive integers with m < n. The last three decimal digits of 1978^m are the same as the last three decimal digits of 1978ⁿ. Find m and n such that m + n has the least possible value.

A2.  P is a point inside a sphere. Three mutually perpendicular rays from P intersect the sphere at points U, V and W. Q denotes the vertex diagonally opposite P in the parallelepiped determined by PU, PV, PW. Find the locus of Q for all possible sets of such rays from P.

A3.  The set of all positive integers is the union of two disjoint subsets {f(1), f(2), f(3), ... }, {g(1), g(2), g(3), ... }, where f(1) < f(2) < f(3) < ..., and g(1) < g(2) < g(3) < ... , and g(n) = f(f(n)) + 1 for n = 1, 2, 3, ... . Determine f(240).

B1.  In the triangle ABC, AB = AC. A circle is tangent internally to the circumcircle of the triangle and also to AB, AC at P, Q respectively. Prove that the midpoint of PQ is the center of the incircle of the triangle.

B2.  {a_k} is a sequence of distinct positive integers. Prove that for all positive integers n, ∑_1≤k≤n a_k/k² ≥ ∑_1≤k≤n 1/k.

B3.  An international society has its members from six different countries. The list of members has 1978 names, numbered 1, 2, ... , 1978. Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice the number of a member from his own country. 

Solutions 

Problem A1

m and n are positive integers with m < n. The last three decimal digits of 1978^m are the same as the last three decimal digits of 1978ⁿ. Find m and n such that m + n has the least possible value.

 

Solution

We require 1978^m(1978^n-m - 1) to be a multiple of 1000=8·125. So we must have 8 divides 1978^m, and hence m ≥ 3, and 125 divides 1978^n-m - 1.

By Euler's theorem, 1978^φ(125) = 1 (mod 125). φ(125) = 125 - 25 = 100, so 1978¹⁰⁰ = 1 (mod 125). Hence the smallest r such that 1978^r = 1 (mod 125) must be a divisor of 100 (because if it was not, then the remainder on dividing it into 100 would give a smaller r). That leaves 9 possibilities to check: 1, 2, 4, 5, 10, 20, 25, 50, 100. To reduce the work we quickly find that the smallest s such that 1978^s = 1 (mod 5) is 4 and hence r must be a multiple of 4. That leaves 4, 20, 100 to examine.

We find 978² = 109 (mod 125), and hence 978⁴ = 6 (mod 125). Hence 978²⁰ = 6⁵ = 36·91 = 26 (mod 125). So the smallest r is 100 and hence the solution to the problem is 3, 103. 

Problem A2

P is a point inside a sphere. Three mutually perpendicular rays from P intersect the sphere at points U, V and W. Q denotes the vertex diagonally opposite P in the parallelepiped determined by PU, PV, PW. Find the locus of Q for all possible sets of such rays from P.

 

Solution

Suppose ABCD is a rectangle and X any point inside, then XA² + XC² = XB² + XD². This is most easily proved using coordinates. Take the origin O as the center of the rectangle and take OA to be the vector a, and OB to be b. Since it is a rectangle, |a| = |b|. Then OC is -a and OD is -b. Let OX be c. Then XA² + XC² = (a - c)² + (a + c)² = 2a² + 2c² = 2b² + 2c² = XB² + XD².

Let us fix U. Then the plane k perpendicular to PU through P cuts the sphere in a circle center C. V and W must lie on this circle. Take R so that PVRW is a rectangle. By the result just proved CR² = 2CV² - CP². OC is also perpendicular to the plane k. Extend it to X, so that CX = PU. Then extend XU to Y so that YR is perpendicular to k. Now OY² = OX² + XY² = OX² + CR² = OX² + 2CV² - CP² = OU² - UX² + 2CV² - CP² = OU² - CP² + 2(OV² - OC²) - CP² = 3OU² - 2OP². Thus the locus of Y is a sphere. 

Problem A3

The set of all positive integers is the union of two disjoint subsets {f(1), f(2), f(3), ... }, {g(1), g(2), g(3), ... }, where f(1) < f(2) < f(3) < ..., and g(1) < g(2) < g(3) < ... , and g(n) = f(f(n)) + 1 for n = 1, 2, 3, ... . Determine f(240).

 

Solution

Let F = {f(1), f(2), f(3), ... }, G = {g(1), g(2), g(3), ... }, N_n = {1, 2, 3, ... , n}. f(1) ≥ 1, so f(f(1)) ≥ 1 and hence g(1) ≥ 2. So 1 is not in G, and hence must be in F. It must be the smallest element of F and so f(1) = 1. Hence g(1) = 2. We can never have two successive integers n and n+1 in G, because if g(m) = n+1, then f(something) = n and so n is in F and G. Contradiction. In particular, 3 must be in F, and so f(2) = 3.

Suppose f(n) = k. Then g(n) = f(k) + 1. So |N_f(k)+1 ∩ G| = n. But |N_f(k)+1 ∩ F| = k, so n + k = f(k) + 1, or f(k) = n + k - 1. Hence g(n) = n + k. So n + k + 1 must be in F and hence f(k+1) = n + k + 1. This so given the value of f for n we can find it for k and k+1.

Using k+1 each time, we get, successively, f(2) = 3, f(4) = 6, f(7) = 11, f(12) = 19, f(20) = 32, f(33) = 53, f(54) = 87, f(88) = 142, f(143) = 231, f(232) = 375, which is not much help. Trying again with k, we get: f(3) = 4, f(4) = 6, f(6) = 9, f(9) = 14, f(14) = 22, f(22) = 35, f(35) = 56, f(56) = 90, f(90) = 145, f(145) = 234. Still not right, but we can try backing up slightly and using k+1: f(146) = 236. Still not right, we need to back up further: f(91) = 147, f(148) = 239, f(240) = 388. 

Problem B1

In the triangle ABC, AB = AC. A circle is tangent internally to the circumcircle of the triangle and also to AB, AC at P, Q respectively. Prove that the midpoint of PQ is the center of the incircle of the triangle.

 

Solution

It is not a good idea to get bogged down in complicated formulae for the various radii. The solution is actually simple.

By symmetry the midpoint, M, is already on the angle bisector of A, so it is sufficient to show it is on the angle bisector of B. Let the angle bisector of A meet the circumcircle again at R. AP is a tangent to the circle touching AB at P, so ∠PRQ = ∠APQ = ∠ABC. Now the quadrilateral PBRM is cyclic because the angles PBR, PMR are both 90^o. Hence ∠PBM = ∠PRM = (∠PRQ)/2, so BM does indeed bisect angle B as claimed. 

Problem B2

{a_k} is a sequence of distinct positive integers. Prove that for all positive integers n, ∑₁ⁿ a_k/k² ≥ ∑₁ⁿ 1/k.

 

Solution

We use the general rearrangement result: given b₁ ≥ b₂ ≥ ... ≥ b_n, and c₁ ≤ c₂ ≤ ... ≤ c_n, if {a_i} is a permutation of {c_i}, then ∑ a_ib_i ≥ ∑ c_ib_i. To prove it, suppose that i < j, but a_i > a_j. Then interchanging a_i and a_j does not increase the sum, because (a_i - a_j)(b_i - b_j) ≥ 0, and hence a_ib_i + a_jb_j ≥ a_jb_i + a_ib_j. By a series of such interchanges we transform {a_i} into {c_i} (for example, first swap c₁ into first place, then c₂ into second place and so on).

Hence we do not increase the sum by permuting {a_i} so that it is in increasing order. But now we have a_i > i, so we do not increase the sum by replacing a_i by i and that gives the sum from 1 to n of 1/k. 

Problem B3

An international society has its members from six different countries. The list of members has 1978 names, numbered 1, 2, ... , 1978. Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice the number of a member from his own country.

 

Solution

The trick is to use differences.

At least 6.329 = 1974, so at least 330 members come from the same country, call it C1. Let their numbers be a₁ < a₂ < ... < a₃₃₀. Now take the 329 differences a₂ - a₁, a₃ - a₁, ... , a₃₃₀ - a₁. If any of them are in C1, then we are home, so suppose they are all in the other five countries.

At least 66 must come from the same country, call it C2. Write the 66 as b₁ < b₂ < ... < b₆₆. Now form the 65 differences b₂ - b₁, b₃ - b₁, ... , b₆₆ - b₁. If any of them are in C2, then we are home. But each difference equals the difference of two of the original a_is, so if it is in C1 we are also home.

So suppose they are all in the other four countries. At least 17 must come from the same country, call it C3. Write the 17 as c₁ < c₂ < ... < c₁₇. Now form the 16 differences c₂ - c₁, c₃ - c₁, ... , c₁₇ - c₁. If any of them are in C3, we are home. Each difference equals the difference of two b_is, so if any of them are in C2 we are home. [For example, consider c_i - c₁. Suppose c_i = b_n - b₁ and c₁ = b_m - b₁, then c_i - c₁ = b_n - b_m, as claimed.]. Each difference also equals the difference of two a_is, so if any of them are in C1, we are also home. [For example, consider c_i - c₁, as before. Suppose b_n = a_j - a₁, b_m = a_k - a₁, then c_i - c₁ = b_n - b_m = a_j - a_k, as claimed.]

So suppose they are all in the other three countries. At least 6 must come from the same country, call it C4. We look at the 5 differences and conclude in the same way that at least 3 must come from C5. Now the 2 differences must both be in C6 and their difference must be in one of the C1, ... , C6 giving us the required sum.

Read more

Solutions are also available in     Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

[more...]