43rd International Mathematical Olympiad 2002 Problems & Solutions

A1.  S is the set of all (h, k) with h, k non-negative integers such that h + k < n. Each element of S is colored red or blue, so that if (h, k) is red and h' ≤ h, k' ≤ k, then (h', k') is also red. A type 1 subset of S has n blue elements with different first member and a type 2 subset of S has n blue elements with different second member. Show that there are the same number of type 1 and type 2 subsets.

A2.  BC is a diameter of a circle center O. A is any point on the circle with angle AOC > 60^o. EF is the chord which is the perpendicular bisector of AO. D is the midpoint of the minor arc AB. The line through O parallel to AD meets AC at J. Show that J is the incenter of triangle CEF.

A3.  Find all pairs of integers m > 2, n > 2 such that there are infinitely many positive integers k for which (kⁿ + k² - 1) divides (k^m + k - 1).

B1.  The positive divisors of the integer n > 1 are d₁ < d₂ < ... < d_k, so that d₁ = 1, d_k = n. Let d = d₁d₂ + d₂d₃ + ... + d_k-1d_k. Show that d < n² and find all n for which d divides n².

B2.  Find all real-valued functions f on the reals such that (f(x) + f(y)) (f(u) + f(v)) = f(xu - yv) + f(xv + yu) for all x, y, u, v.

B3.  n > 2 circles of radius 1 are drawn in the plane so that no line meets more than two of the circles. Their centers are O₁, O₂, ... , O_n. Show that ∑_i<j 1/O_iO_j ≤ (n-1)π/4. 

Solutions

Problem A1

S is the set of all (h, k) with h, k non-negative integers such that h + k < n. Each element of S is colored red or blue, so that if (h, k) is red and h' ≤ h, k' ≤ k, then (h', k') is also red. A type 1 subset of S has n blue elements with different first member and a type 2 subset of S has n blue elements with different second member. Show that there are the same number of type 1 and type 2 subsets.

Solution

Let a_i be the number of blue members (h, k) in S with h = i, and let b_i be the number of blue members (h, k) with k = i. It is sufficient to show that b₀, b₁, ... , b_n-1 is a rearrangement of a₀, a₁, ... , a_n-1 (because the number of type 1 subsets is the product of the a_i and the number of type 2 subsets is the product of the b_i).

Let c_i be the largest k such that (i, k) is red. If (i, k) is blue for all k then we put c_i = -1. Note that if i < j, then c_i ≥ c_j, since if (j, c_i ) is red, then so is (i, c_i ). Note also that (i, k) is red for k ≤ c_i, so the sequence c₀, c₁, ... , c_n-1 completely defines the coloring of S.

Let S_i be the set with the sequence c₀, c₁, ... , c_i, -1, ... , -1, so that S_n-1 = S. We also take S_-1 as the set with the sequence -1, -1, ... , -1, so that all its members are blue. We show that the rearrangement result is true for S_-1 and that if it is true for S_i then it is true for S_i+1. It is obvious for S_-1, because both a_i and b_i are n, n-1, ... , 2, 1. So suppose it is true for S_i (where i < n-1). The only difference between the a_j for S_i and for S_i+1 is that a_i+1 = n-i-1 for S_i and (n-i-1)-(c_i+1+1) for S_i+1. In other words, the number n-i-1 is replaced by the number n-i-c-2, where c = c_i+1. The difference in the b_j is that 1 is deducted from each of b₀, b₁, ... , b_c. But these numbers are just n-i-1, n-i-1, n-i-2, ... , n-i-c-1. So the effect of deducting 1 from each is to replace n-i-1 by n-i-c-2, which is the same change as was made to the a_j. So the rearrangement result also holds for S_i+1. Hence it holds for S. 

Problem A2

BC is a diameter of a circle center O. A is any point on the circle with angle AOC > 60^o. EF is the chord which is the perpendicular bisector of AO. D is the midpoint of the minor arc AB. The line through O parallel to AD meets AC at J. Show that J is the incenter of triangle CEF.

Solution

F is equidistant from A and O. But OF = OA, so OFA is equilateral and hence angle AOF = 60^o. Since angle AOC > 60^o, F lies between A and C. Hence the ray CJ lies between CE and CF.

D is the midpoint of the arc AB, so angle DOB = ½ angle AOB = angle ACB. Hence DO is parallel to AC. But OJ is parallel to AD, so AJOD is a parallelogram. Hence AJ = OD. So AJ = AE = AF, so J lies on the opposite side of EF to A and hence on the same side as C. So J must lie inside the triangle CEF.

Also, since EF is the perpendicular bisector of AO, we have AE = AF = OE, so A is the center of the circle through E, F and J. Hence angle EFJ = ½ angle EAJ. But angle EAJ = angle EAC (same angle) = angle EFC. Hence J lies on the bisector of angle EFC.

Since EF is perpendicular to AO, A is the midpoint of the arc EF. Hence angle ACE = angle ACF, so J lies on the bisector of angle ECF. Hence J is the incenter.

Many thanks to Dirk Laurie for pointing out that the original version of this solution failed to show the relevance of angle AOC > 60^o. According to the official marking scheme, one apparently lost a mark for failing to show J lies inside CEF.

Problem A3

Find all pairs of integers m > 2, n > 2 such that there are infinitely many positive integers k for which (kⁿ + k² - 1) divides (k^m + k - 1).

Solution

Answer: m = 5, n = 3.

Obviously m > n. Take polynomials q(x), r(x) with integer coefficients and with degree r(x) < n such that x^m + x - 1 = q(x) (xⁿ + x² - 1) + r(x). Then xⁿ + x² - 1 divides r(x) for infinitely many positive integers x. But for sufficiently large x, xⁿ + x² - 1 > r(x) since r(x) has smaller degree. So r(x) must be zero. So x^m + x - 1 factorises as q(x) (xⁿ + x² - 1), where q(x) = x^m-n + a_m-n-1x^m-n-1 + ... + a₀.

At this point I use an elegant approach provided by Jean-Pierre Ehrmann

We have (x^m + x - 1) = x^m-n(xⁿ + x² - 1) + (1 - x)(x^m-n+1 + x^m-n - 1), so (xⁿ + x² - 1) must divide (x^m-n+1 + x^m-n - 1). So, in particular, m ≥ 2n-1. Also (xⁿ + x² - 1) must divide (x^m-n+1 + x^m-n - 1) - x^m-2n+1(xⁿ + x² - 1) = x^m-n - x^m-2n+3 + x^m-2n+1 - 1 (*).

At this point there are several ways to go. The neatest is Bill Dubuque's:

(*) can be written as x^m-2n+3(x^n-3 - 1) + (x^m-(2n-1) - 1) which is < 0 for all x in (0, 1) unless n - 3 = 0 and m - (2n - 1) = 0. So unless n = 3, m = 5, it is has no roots in (0, 1). But xⁿ + x² - 1 (which divides it) has at least one becaause it is -1 at x = 0 and +1 at x = 1. So we must have n = 3, m = 5. It is easy to check that in this case we have an identity.

Two alternatives follow. Jean-Pierre Ehrmann continued:

If m = 2n-1, (*) is x^n-1 - x². If n = 3, this is 0 and indeed we find m = 5, n = 3 gives an identity. If n > 3, then it is x²(x^n-3 - 1). But this has no roots in the interval (0, 1), whereas xⁿ + x² - 1 has at least one (because it is -1 at x = 0 and +1 at x = 1), so xⁿ + x² - 1 cannot be a factor.

If m > 2n-1, then (*) has four terms and factorises as (x - 1)(x^m-n-1 + x^m-n-2 + ... + x^m-2n+3 + x^m-2n + x^m-2n-1 + ... + 1). Again, this has no roots in the interval (0, 1), whereas xⁿ + x² - 1 has at least one, so xⁿ + x² - 1 cannot be a factor.

François Lo Jacomo, having got to xⁿ + x² - 1 divides x^m-n+1 + x^m-n - 1 and looking at the case m -n + 1 > n, continues:

xⁿ + x² - 1 has a root r such that 0 < r < 1 (because it is -1 at x = 0 and +1 at x = 1). So rⁿ = 1 - r². It must also be a root of x^m + x - 1, so 1 - r = r^m ≤ r²ⁿ = (1 - r²)². Hence (1 - r²)² - (1 - r) = (1 - r) r (1 - r - r²) ≥ 0, so 1 - r - r² ≥ 0. Hence rⁿ = 1 - r² ≥ r, which is impossible.

Many thanks to Carlos Gustavo Moreira for patiently explaining why the brute force approach of calculating the coefficients of q(x), starting at the low end, is full of pitfalls. After several failed attempts, I have given up on it!

Problem B1

The positive divisors of the integer n > 1 are d₁ < d₂ < ... < d_k, so that d₁ = 1, d_k = n. Let d = d₁d₂ + d₂d₃ + ... + d_k-1d_k. Show that d < n² and find all n for which d divides n².

Solution

d_k+1-m <= n/m. So d < n²(1/(1.2) + 1/(2.3) + 1/(3.4) + ... ). The inequality is certainly strict because d has only finitely many terms. But 1/(1.2) + 1/(2.3) + 1/(3.4) + ... = (1/1 - 1/2) + (1/2 - 1/3) + (1/3 - 1/4) + ... = 1. So d < n².

Obviously d divides n² for n prime. Suppose n is composite. Let p be the smallest prime dividing n. Then d > n²/p. But the smallest divisor of n² apart from 1 is p, so if d divides n², then d ≤ n²/p. So d cannot divide n² for n composite. 

Problem B2

Find all real-valued functions f on the reals such that (f(x) + f(y)) (f(u) + f(v)) = f(xu - yv) + f(xv + yu) for all x, y, u, v.

Solution

Answer: there are three possible functions: (1) f(x) = 0 for all x; (2) f(x) = 1/2 for all x; or (3) f(x) = x².

Put x = y = 0, u = v, then 4 f(0) f(u) = 2 f(0). So either f(u) = 1/2 for all u, or f(0) = 0. f(u) = 1/2 for all u is certainly a solution. So assume f(0) = 0.

Putting y = v = 0, f(x) f(u) = f(xu) (*). In particular, taking x = u = 1, f(1)² = f(1). So f(1) = 0 or 1. Suppose f(1) = 0. Putting x = y = 1, v = 0, we get 0 = 2f(u), so f(x) = 0 or all x. That is certainly a solution. So assume f(1) = 1.

Putting x = 0, u = v = 1 we get 2 f(y) = f(y) + f(-y), so f(-y) = f(y). So we need only consider f(x) for x positive. We show next that f(r) = r² for r rational. The first step is to show that f(n) = n² for n an integer. We use induction on n. It is true for n = 0 and 1. Suppose it is true for n-1 and n. Then putting x = n, y = u = v = 1, we get 2f(n) + 2 = f(n-1) + f(n+1), so f(n+1) = 2n² + 2 - (n-1)² = (n+1)² and it is true for n+1. Now (*) implies that f(n) f(m/n) = f(m), so f(m/n) = m²/n² for integers m, n. So we have established f(r) = r² for all rational r.

From (*) above, we have f(x²) = f(x)² ≥ 0, so f(x) is always non-negative for positive x and hence for all x. Putting u = y, v = x, we get ( f(x) + f(y) )² = f(x² + y²), so f(x² + y²) = f(x)² + 2f(x)f(y) + f(y)² ≥ f(x)² = f(x²). For any u > v > 0, we may put u = x² + y², v = x² and hence f(u) ≥ f(v). In other words, f is an increasing function.

So for any x we may take a sequence of rationals r_n all less than x we converge to x and another sequence of rationals s_n all greater than x which converge to x. Then r_n² = f(r_n) ≤ f(x) ≤ f(s_n) = s_n² for all x and hence f(x) = x². 

Problem B3

2 circles of radius 1 are drawn in the plane so that no line meets more than two of the circles. Their centers are O₁, O₂, ... , O_n. Show that ∑_i<j 1/O_iO_j ≤ (n-1)π/4.

Solution

Denote the circle center O_i by C_i. The tangents from O₁ to C_i contain an angle 2x where sin x = 1/O₁O_i. So 2x > 2/O₁O_i. These double sectors cannot overlap, so ∑ 2/O₁O_i < π. Adding the equations derived from O₂, O₃, ... we get 4 ∑ O_iO_j < nπ, so ∑ O_iO_j < nπ/4, which is not quite good enough.

There are two key observations. The first is that it is better to consider the angle O_iO₁O_j than the angle between the tangents to a single circle. It is not hard to show that this angle must exceed both 2/O₁O_i and 2/O₁O_j. For consider the two common tangents to C₁ and C_i which intersect at the midpoint of O₁O_i. The angle between the center line and one of the tangents is at least 2/O₁O_i. No part of the circle C_j can cross this line, so its center O_j cannot cross the line parallel to the tangent through O₁. In other word, angle O_iO₁O_j is at least 2/O₁O_i. A similar argument establishes it is at least 2/O₁O_j.

Now consider the convex hull of the n points O_i. m ≤ n of these points form the convex hull and the angles in the convex m-gon sum to (m-2)π. That is the second key observation. That gains us not one but two amounts π/4. However, we lose one back. Suppose O₁ is a vertex of the convex hull and that its angle is θ₁. Suppose for convenience that the rays O₁O₂, O₁O₃, ... , O₁O_n occur in that order with O₂ and O_n adjacent vertices to O₁ in the convex hull. We have that the n-2 angles between adjacent rays sum to θ₁. So we have ∑ 2/O₁O_i < θ₁, where the sum is taken over only n-2 of the i, not all n-1. But we can choose which i to drop, because of our freedom to choose either distance for each angle. So we drop the longest distance O₁O_i. [If O₁O_k is the longest, then we work outwards from that ray. Angle O_k-1O₁O_k > 2/O₁O_k-1, and angle O_kO₁O_k+1 > 2/O₁O_k+1 and so on.]

We now sum over all the vertices in the convex hull. For any centers O_i inside the hull we use the ∑_j 2/O_iO_j < π which we established in the first paragraph, where the sum has all n-1 terms. Thus we get ∑_i,j 2/O_iO_j < (n-2)π, where for vertices i for which O_i is a vertex of the convex hull the sum is only over n-2 values of j and excludes 2/O_iO_{max i} where O_{max i}denotes the furthest center from O_i.

Now for O_i a vertex of the convex hull we have that the sum over all j, ∑ 2/O_iO_j, is the sum Σ' over all but j = max i plus at most 1/(n-2) Σ'. In other words we must increase the sum by at most a factor (n-1)/(n-2) to include the missing term. For O_i not a vertex of the hull, obviously no increase is needed. Thus the full sum ∑_i,j 2/O_iO_j < (n-1)π. Hence ∑_i<j 1/O_iO_j < (n-1)π/4 as required.