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.