31st International Mathematical Olympiad 1990 Problems & Solutions

A1. Chords AB and CD of a circle intersect at a point E inside the circle. Let M be an interior point of the segment EB. The tangent at E to the circle through D, E and M intersects the lines BC and AC at F and G respectively. Find EF/EG in terms of t = AM/AB.

A2. Take n ≥ 3 and consider a set E of 2n-1 distinct points on a circle. Suppose that exactly k of these points are to be colored black. Such a coloring is "good" if there is at least one pair of black points such that the interior of one of the arcs between them contains exactly n points from E. Find the smallest value of k so that every such coloring of k points of E is good.

A3. Determine all integers greater than 1 such that (2ⁿ + 1)/n² is an integer.

B1. Construct a function from the set of positive rational numbers into itself such that f(x f(y)) = f(x)/y for all x, y.

B2. Given an initial integer n₀ > 1, two players A and B choose integers n₁, n₂, n₃, ... alternately according to the following rules:

Knowing n_2k, A chooses any integer n_2k+1 such that n_2k ≤ n_2k+1 ≤ n_2k².

Knowing n_2k+1, B chooses any integer n_2k+2 such that n_2k+1/n_2k+2 = p^r for some prime p and integer r ≥ 1. Player A wins the game by choosing the number 1990; player B wins by choosing the number 1. For which n₀ does

(a) A have a winning strategy?

(b) B have a winning strategy?

B3. Prove that there exists a convex 1990-gon such that all its angles are equal and the lengths of the sides are the numbers 1², 2², ... , 1990² in some order.

Solutions

Problem A1

Chords AB and CD of a circle intersect at a point E inside the circle. Let M be an interior point of the segment EB. The tangent at E to the circle through D, E and M intersects the lines BC and AC at F and G respectively. Find EF/EG in terms of t = AM/AB.

Solution

By Theo Koupelis, University of Wisconsin, Marathon

∠ECF = ∠DCB (same angle) = ∠DAB (ACBD is cyclic) = ∠MAD (same angle). Also ∠CEF = ∠EMD (GE tangent to circle EMD) = ∠AMD (same angle). So triangles CEF and AMD are similar.

∠CEG = 180^o - ∠CEF = 180^o - ∠EMD = ∠BMD. Also ∠ECG = ∠ACD (same angle) = ∠ABD (BCAD is cyclic) = ∠MBD (same angle). So triangles CEG and BMD are similar.

Hence EF/CE = MD/AM, EG/CE = MD/BM, and so dividing, EF/EG = BM/AM = (1- t)/t.

Problem A2

Take n ≥ 3 and consider a set E of 2n-1 distinct points on a circle. Suppose that exactly k of these points are to be colored black. Such a coloring is "good" if there is at least one pair of black points such that the interior of one of the arcs between them contains exactly n points from E. Find the smallest value of k so that every such coloring of k points of E is good.

Solution

Answer: n for n = 0 or 1 (mod 3), n - 1 for n = 2 (mod 3).

Label the points 1 to 2n - 1. Two points have exactly n points between them if their difference (mod 2n - 1) is n - 2 or n + 1. We consider separately the three cases n = 3m, 3m + 1 and 3m + 2.

Let n = 3m. First, we exhibit a bad coloring with n - 1 black points. Take the black points to be 1, 4, 7, ... , 6m - 2 (2m points) and 2, 5, 8, ... , 3m - 4 (m - 1 points). It is easy to check that this is bad. The two points which could pair with r to give n points between are r + 3m - 2 and r + 3m + 1. Considering the first of these, 1, 4, 7, ... , 6m - 2 would pair with 3m - 1, 3m + 2, 3m + 5, ... , 6m - 1, 3, 6, ... , 3m - 6, none of which are black. Considering the second, they would pair with 3m + 2, 3m + 5, ... , 6m - 1, 3, ... , 3m - 3, none of which are black. Similarly, 2, 5, 8, ... , 3m - 4 would pair with 3m, 3m + 3, ... , 6m - 3, none of which are black. So the set is bad.

Now if we start with 1 and keep adding 3m - 2, reducing by 6m - 1 when necessary to keep the result in the range 1, ... , 6m - 1, we eventually get back to 1: 1, 3m - 1, 6m - 3, 3m - 4, 6m - 6, ... , 2, 3m, 6m - 2, 3m - 3, 6m - 5, ... , 3, 3m + 1, 6m - 1, ... , 4, 3m + 2, 1. The sequence includes all 6m - 1 numbers. Moreover a bad coloring cannot have any two consecutive numbers colored black. But this means that at most n - 1 out of the 2n - 1 numbers in the sequence can be black. This establishes the result for n = 3m.

Take n = 3m + 1. A bad coloring with n - 1 black points has the following black points: 1, 4, 7, ... , 3m - 2 (m points) and 2, 5, 8, ... , 6m - 1 (2m points). As before we add n - 2 repeatedly starting with 1 to get: 1, 3m, 6m - 1, 3m - 3, 6m - 4, ... , 3, 3m + 2, 6m + 1, 3m - 1, ... , 2, 3m + 1, 6m, 3m - 2, ... , 1. No two consecutive numbers can be black in a bad set, so a bad set can have at most n - 1 points.

Finally, take n = 3m + 2. A bad coloring with n - 2 points is 1, 2, ... , n - 2. This time when we add n - 2 = 3m repeatedly starting with 1, we get back to 1 after including only one-third of the numbers: 1, 3m + 1, 6m + 1, 3m - 2, ... , 4, 3m + 4, 1. The usual argument shows that at most m of these 2m + 1 numbers can be colored black in a bad set. Similarly, we may add 3m repeatedly starting with 2 to get another 2m + 1 numbers: 2, 3m + 2, 6m + 2, 3m - 1, ... , 3m + 5, 2. At most m of these can be black in a bad set. Similarly at most m of the 2m + 1 numbers: 3, 3m + 3, 6m + 3, 3m, ... , 3m + 6, 3 can be black. So in total at most 3m = n - 2 can be black in a bad set.

Problem A3

Determine all integers greater than 1 such that (2ⁿ + 1)/n² is an integer.

Solution

by Gerhard Wöginger, Technical University, Graz

Answer: n = 3.

Since 2ⁿ + 1 is odd, n must also be odd. Let p be its smallest prime divisor. Let x be the smallest positive integer such that 2^x = -1 (mod p), and let y be the smallest positive integer such that 2^y = 1 (mod p). y certainly exists and indeed y < p, since 2^p-1 = 1 (mod p). x exists since 2ⁿ = -1 (mod p). Write n = ys + r, with 0 ≤ r < y. Then - 1 = 2ⁿ = (2^y)^s2^r = 2^r (mod p), so x ≤ r < y (r cannot be 0, since - 1 is not 1 (mod p) ).

Now write n = hx + k, with 0 ≤ k < x. Then -1 = 2ⁿ = (-1)^h2^k (mod p). Suppose k > 0. Then if h is odd we contradict the minimality of y, and if h is even we contradict the minimality of x. So k = 0 and x divides n. But x < p and p is the smallest prime dividing n, so x = 1. Hence 2 = -1 (mod p) and so p = 3.

Now suppose that 3^m is the largest power of 3 dividing n. We show that m must be 1. Expand (3 - 1)ⁿ + 1 by the binomial theorem, to get (since n is odd): 1 - 1 + n.3 - 1/2 n(n - 1) 3² + ... = 3n - (n - 1)/2 n 3² + ... . Evidently 3n is divisible by 3^m+1, but not 3^m+2. We show that the remaining terms are all divisible by 3^m+2. It follows that 3^m+1 is the highest power 3 dividing 2ⁿ + 1. But 2ⁿ + 1 is divisible by n² and hence by 3^2m, so m must be 1.

The general term is (3^ma)Cb 3^b, for b ≥ 3. The binomial coefficients are integral, so the term is certainly divisible by 3^m+2 for b ≥ m+2. We may write the binomial coefficient as (3^ma/b) (3^m - 1)/1 (3^m - 2)/2 (3^m - 3)/3 ... (3^m - (b-1)) / (b - 1). For b not a multiple of 3, the first term has the form 3^m c/d, where 3 does not divide c or d, and the remaining terms have the form c/d, where 3 does not divide c or d. So if b is not a multiple of 3, then the binomial coefficient is divisible by 3^m, since b > 3, this means that the whole term is divisible by at least 3^m+3. Similarly, for b a multiple of 3, the whole term has the same maximum power of 3 dividing it as 3^m 3^b/b. But b is at least 3, so 3^b/b is divisible by at least 9, and hence the whole term is divisible by at least 3^m+2.

We may check that n = 3 is a solution. If n > 3, let n = 3 t and let q be the smallest prime divisor of t. Let w be the smallest positive integer for which 2^w = -1 (mod q), and v the smallest positive integer for which 2^v = 1 (mod q). v certainly exists and < q since 2^q-1 = 1 (mod q). 2ⁿ = -1 (mod q), so w exists and, as before, w < v. Also as before, we conclude that w divides n. But w < q, the smallest prime divisor of n, except 3. So w = 1 or 3. These do not work, because then 2 = -1 (mod q) and so q = 3, or 2³ = -1 (mod q) and again q =3, whereas we know that q > 3.

Problem B1

Construct a function from the set of positive rational numbers into itself such that f(x f(y)) = f(x)/y for all x, y.

Solution

We show first that f(1) = 1. Taking x = y = 1, we have f(f(1)) = f(1). Hence f(1) = f(f(1)) = f(1 f(f(1)) ) = f(1)/f(1) = 1.

Next we show that f(xy) = f(x)f(y). For any y we have 1 = f(1) = f(1/f(y) f(y)) = f(1/f(y))/y, so if z = 1/f(y) then f(z) = y. Hence f(xy) = f(xf(z)) = f(x)/z = f(x) f(y).

Finally, f(f(x)) = f(1 f(x)) = f(1)/x = 1/x.

We are not required to find all functions, just one. So divide the primes into two infinite sets S = {p₁, p₂, ... } and T= {q₁, q₂, ... }. Define f(p_n) = q_n, and f(q_n) = 1/p_n. We extend this definition to all rationals using f(xy) = f(x) f(y): f(p_i₁p_i₂...q_j₁q_j₂.../(p_k₁...q_m₁...)) = p_m₁...q_i₁.../(p_j₁...q_k₁...). It is now trivial to verify that f(x f(y)) = f(x)/y.

Problem B2

Given an initial integer n₀ > 1, two players A and B choose integers n₁, n₂, n₃, ... alternately according to the following rules:
Knowing n_2k, A chooses any integer n_2k+1 such that n_2k ≤ n_2k+1 ≤ n_2k².
Knowing n_2k+1, B chooses any integer n_2k+2 such that n_2k+1/n_2k+2 = p^r for some prime p and integer r ≥ 1.

Player A wins the game by choosing the number 1990; player B wins by choosing the number 1. For which n₀ does
(a) A have a winning strategy?
(b) B have a winning strategy?
(c) Neither player have a winning strategy?

Solution

Answer: if n₀ = 2, 3, 4 or 5 then A loses; if n₀ ≥ 8, then A wins; if n₀ = 6 or 7 , then it is a draw.

A's strategy given a number n is as follows:
(1) if n ∈ [8, 11], pick 60
(2) if n ∈ [12, 16], pick 140
(3) if n ∈ [17, 22], pick 280
(4) if n ∈ [23, 44], pick 504
(5) if n ∈ [45, 1990], pick 1990
(6) if n = 1991 = 11.181 (181 is prime), pick 1991
(7) if n ∈ [11^r181 + 1, 11^r+1181] for some r > 0, pick 11^r+1181.

Clearly (5) wins immediately for A. After (4) B has 7.8.9 so must pick 56, 63, 72 or 168, which gives A an immediate win by (5). After (3) B must pick 35, 40, 56, 70 or 140, so A wins by (4) and (5). After (2) B must pick 20, 28, 35 or 70, so A wins by (3) - (5). After (1) B must pick 12, 15, 20 or 30, so A wins by (2) - (5).

If B is given 11^r+1181, then B must pick 181, 11.181, ... , 11^r.181 or 11^r+1, all of which are ≤ 11^r.181. So if A is given a number n in (6) or (7) then after a turn each A is given a number < n (and >= 11), so after a finite number of turns A wins.

If B gets a number less than 6, then he can pick 1 and win. Hence if A is given 2, he loses, because he must pick a number less than 5. Now if B gets a number of 11 or less, he wins by picking 1 or 2. Hence if A is given 3, he loses, because he must pick a number less than 10. Now if B gets a number of 19 or less, he can win by picking 1, 2 or 3. So if A is given 4 he loses. Now if B is given 29 or less, he can pick 1, 2, 3 or 4 and win. So if A is given 5 he loses.

We now have to consider what happens if A gets 6 or 7. He must pick 30 or more, or B wins. If he picks 31, 32, 33, 34, 35 or 36, then B wins by picking (for example) 1, 1, 3, 2, 5, 4 respectively. So his only hope given 6 is to pick 30. B also wins given any of 37, 38, 39, 40, 41, 43, 44, 45, 46, 47, 48, 49 (winning moves, for example, 37, 1; 38, 2; 39, 3; 40, 5; 41, 1; 43, 1; 44, 4; 45, 5; 46, 3; 47, 1; 48, 3]. So A's only hope given 7 is to pick 30 or 42.

If B is faced with 30=2·3·5, then he has a choice of 6, 10, 15. We have already established that 10 and 15 will lose, so he must pick 6. Thus 6 is a draw: A must pick 30 or lose, and then B must pick 6 or lose.

If B is faced with 42=2·3·7, then he has a choice of 6, 14 or 21. We have already established that 14 and 21 lose, so he must pick 6. Thus 7 is also a draw: A must pick 30 or 42, and then B must pick 6.

Comment

I am grateful to Gerhard Wöginger and Jean-Pierre Ehrmann for finding errors in my original solution.

Problem B3

Prove that there exists a convex 1990-gon such that all its angles are equal and the lengths of the sides are the numbers 1², 2², ... , 1990² in some order.

Solution

By Robin Chapman, Dept of Maths, Macquarie University, Australia

In the complex plane we can represent the sides as p_n²wⁿ, where p_n is a permutation of (1, 2, ... , 1990) and w is a primitive 1990th root of unity.

The critical point is that 1990 is a product of more than 2 distinct primes: 1990 = 2·5·199. So we can write w = -1·a·b, where -1 is primitive 2nd root of unity, a is a primitive 5th root of unity, and b is a primitive 199th root of unity.

Now given one of the 1990th roots we may write it as (-1)ⁱa^jb^k, where 0 < i < 2, 0 < j < 5, 0 < k < 199 and hence associate it with the integer r(i,j,k) = 1 + 995i + 199j + k. This is a bijection onto (1, 2, ... , 1990). We have to show that the sum of r(i,j,k)² (-1)ⁱa^jb^k is zero.

We sum first over i. This gives -995² x sum of a^jb^k which is zero, and - 1990 x sum s(j,k) a^jb^k, where s(j,k) = 1 + 199j + k. So it is sufficient to show that the sum of s(j,k) a^jb^k is zero. We now sum over j. The 1 + k part of s(j,k) immediately gives zero. The 199j part gives a constant times b^k, which gives zero when summed over k.