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?

(c)  Neither player 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_i1p_i2...q_j1q_j2.../(p_k1...q_m1...)) = p_m1...q_i1.../(p_j1...q_k1...). 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. 

 A First Step to Mathematical Olympiad Problems (Mathematical Olympiad Series) 

OLYMPIA -The LENI RIEFENSTAHL Archival Collection 

15 000 problems from Mathematical Olympiads 

Read more

Solutions are also available in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X. 

[more...]

30th International Mathematical Olympiad 1989 Problems & Solutions

A1.  Prove that the set {1, 2, ... , 1989} can be expressed as the disjoint union of subsets A₁, A₂, ... , A₁₁₇ in such a way that each A_i contains 17 elements and the sum of the elements in each A_i is the same.

A2.  In an acute-angled triangle ABC, the internal bisector of angle A meets the circumcircle again at A₁. Points B₁ and C₁ are defined similarly. Let A₀ be the point of intersection of the line AA₁ with the external bisectors of angles B and C. Points B₀ and C₀ are defined similarly. Prove that the area of the triangle A₀B₀C₀ is twice the area of the hexagon AC₁BA₁CB₁ and at least four times the area of the triangle ABC.

A3.  Let n and k be positive integers, and let S be a set of n points in the plane such that no three points of S are collinear, and for any point P of S there are at least k points of S equidistant from P. Prove that k < 1/2 + √(2n).

B1.  Let ABCD be a convex quadrilateral such that the sides AB, AD, BC satisfy AB = AD + BC. There exists a point P inside the quadrilateral at a distance h from the line CD such that AP = h + AD and BP = h + BC. Show that:     1/√h ≥ 1/√AD + 1/√BC.

B2.  Prove that for each positive integer n there exist n consecutive positive integers none of which is a prime or a prime power.

B3.  A permutation {x₁, x₂, ... , x_m} of the set {1, 2, ... , 2n} where n is a positive integer is said to have property P if |x_i - x_i+1| = n for at least one i in {1, 2, ... , 2n-1}. Show that for each n there are more permutations with property P than without. 

Solutions

Problem A1

Prove that the set {1, 2, ... , 1989} can be expressed as the disjoint union of subsets A₁, A₂, ... , A₁₁₇ in such a way that each A_i contains 17 elements and the sum of the elements in each A_i is the same.

Solution

We construct 116 sets of three numbers. Each set sums to 3 x 995 = 2985. The 348 numbers involved form 174 pairs {r, 1990 - r}. At this point we are essentially done. We take a 117th set which has one {r, 1990 - r} pair and 995. The original 1989 numbers comprise 995 and 994 {r, 1990 - r} pairs. We have used up 995 and 175 pairs, leaving just 819 pairs. We now add 7 pairs to each of our 117 sets, bringing the total of each set up to 2985 + 7.1990 = 1990 x 17/2.

It remains to exhibit the 116 sets. There are many possibilities. We start with:
301, 801, 1883 and the "complementary" set 1990 - 301 = 1689, 1990 - 801 = 1189, 1990 - 1883 = 107. We then add one to each of the first two numbers to get:
302, 802, 1881 and 1688, 1188, 109, and so on:
303, 803, 1879 and 1687, 1187, 111,
...
358, 858, 1769 and 1632, 1132, 221.
We can immediately see that these triples are all disjoint. So the construction is complete. 

Problem A2

In an acute-angled triangle ABC, the internal bisector of angle A meets the circumcircle again at A₁. Points B₁ and C₁ are defined similarly. Let A₀ be the point of intersection of the line AA₁ with the external bisectors of angles B and C. Points B₀ and C₀ are defined similarly. Prove that the area of the triangle A₀B₀C₀ is twice the area of the hexagon AC₁BA₁CB₁ and at least four times the area of the triangle ABC.

Solution

By Marcin Mazur, University of Illinois at Urbana-Champaign

Let I be the point of intersection of AA₀, BB₀, CC₀ (the in-center). BIC = 180 - 1/2 ABC - 1/2 BCA = 180 - 1/2 (180 - CAB) = 90 + 1/2 CAB. Hence CA₁B = 180 - CAB [BA₁CA is cyclic] = 2(180 - BIC) = 2CA₀B. But A₁B = A₁C, so A₁ is the center of the circumcircle of BCA₀. But I lies on this circumcircle (IBA₀ = ICA₀ = 90), and hence A₁A₀ = A₁I.

Hence area IBA₁ = area A₀BA₁ and area ICA₁ = area A₀CA₁. Hence area IBA₀C = 2 area IBA₁C. Similarly, area ICB₀A = 2 area ICB₁A and area IAC₀B = 2 area IAC₁B. Hence area A₀B₀C₀ = 2 area hexagon AB₁CA₁BC₁.

A neat solution for the rest is as follows by Thomas Jäger

Let H be the orthocentre of ABC. Let H₁ be the reflection of H in BC, so H₁ lies on the circumcircle. So area BCH = area BCH₁ <= area BCA₁. Adding to the two similar inequalities gives area ABC <= area hexagon - area ABC.

Mazur's solution was as follows

CAB = 180^o - CA₁B and A₁B = A₁C, so A₁BC = 90^o - 1/2 CA₁B = 1/2 CAB. Hence the perpendicular from A₁ to BC has length 1/2 BC tan(CAB/2) and area CA₁B = 1/4 BC² tan(CAB/2).

Put r = radius of in-circle of ABC, x = cot(CAB/2), y = cot(ABC/2), z = cot(BCA/2). Then BC = r(y + z) and area CA₁B = r²(y + z)²/(4x). Also area BIC = 1/2 r BC. Similarly for the other triangles, so area ABC = area BIC + area CIA + area AIB = r²(x + y + z). We have to show that area ABC ≤ area CA₁B + area AB₁C + area BC₁A, or (x + y + z) ≤ (y + z)²/(4x) + (z + x)²/(4y) + (x + y)²/(4z).

Putting s = x + y + z, this is equivalent to: 4s ≤ (s - x)²/x + (s - y)²/y + (s - z)²/z, or 9s ≤ s²(1/x + 1/y + 1/z), but this is just the statement that the arithmetic mean of x, y, z is not less than the harmonic mean.

Note in passing that the requirement for ABC to be acute is unnecessary. 

Problem A3

Let n and k be positive integers, and let S be a set of n points in the plane such that no three points of S are collinear, and for any point P of S there are at least k points of S equidistant from P. Prove that k < 1/2 + √(2n).

Solution

Three variants on a theme, all kindly supplied by others (I spent 2 hours failing to solve it). My favorite first.

By Eli Bachmutsky

Consider the pairs P, {A, B}, where P, A, B are points of S, and P lies on the perpendicular bisector of AB. There are at least n k(k - 1)/2 such pairs, because for each point P, there are at least k points equidistant from P and hence at least k(k - 1)/2 pairs of points equidistant from P.

If k ≥ 1/2 + √(2n), then k(k - 1) ≥ 2n - 1/4 > 2(n - 1), and so there are more than n(n - 1) pairs P, {A, B}. But there are only n(n - 1)/2 possible pairs {A, B}, so for some {A₀, B₀} we must be able to find at least 3 points P on the perpendicular bisector of A₀B₀. But these points are collinear, contradicting the assumption in the question.

 
From an anonymous source

Let the points be P₁, P₂, ... , P_n. Let C_i be a circle center P_i containing at least k points of S. There are at least nk pairs (C_i,P_j), where P_j lies on C_i. Hence there must a point P lying on at least k circles. Take k such circles C_α. For each such circle C_α, take a subset S_α comprising exactly k points of S ∩ C_α.

We now count the points in ∪ S_α. Apart from P, there are k-1 points in each S_α. So we start with 1 + k(k-1). But this counts some points more than once. Each pair (S_α, S_β) (with α ≠ β) has at most one common point apart from P (because distinct circles have at most two common points). So we deduct 1 for each of the 1/2 k(k - 1) pairs (S_α, S_β), giving 1 + k(k - 1) - 1/2 k(k - 1) (*).

If Q (≠ P) is in exactly r sets S_α, then it is counted r times in the second term k(k - 1), and subtracted 1/2 r(r - 1) times in the third term. So it is counted 1/2 r(3 - r) times in all. That is correct for r = 0, 1 or 2 and too low for r > 2. So (*) is ≤ |∪ S_α|. Clearly |∪ S_α| ≤ n, so n ≥ 1 + k(k - 1)/2 = (k - 1/2)²/2 + 7/8 > (k - 1/2)²/2. Hence √(2n) + 1/2 > k.

By Thomas Jäger

Define P_i and S_i as above. Let g(i) be the number of S_a containing P_i, and let f(i, j) be |S_i ∩ S_j|. Let h(x) = x(x - 1)/2. We count the number N of pairs i, {a, b}, where point i is in S_a and S_b.

Point i is in g(i) sets S_j, from which we can choose S_a,S_b in h(g(i)) ways. Hence N = ∑ h(g(i)). But f(a, b) points are in S_a and S_b, so N = ∑ f(a, b). But, since distinct circles intersect in at most 2 points, f(a, b) ≤ 2, so ∑ f(a, b) ≤ h(n) 2. We conclude that 2 h(n) ≥ ∑ h(g(i)).

h is a convex function, so 1/n ∑ h(g(i)) ≥ h(1/n ∑ g(i)) = n h(1/n nk) = n h(k). Hence n - 1 ≥ h(k), which gives the result, as above. 

Problem B1

Let ABCD be a convex quadrilateral such that the sides AB, AD, BC satisfy AB = AD + BC. There exists a point P inside the quadrilateral at a distance h from the line CD such that AP = h + AD and BP = h + BC. Show that:

    1/√h ≥ 1/√AD + 1/√BC.

Solution

by Gerhard Wöginger, Technical University, Graz

Let C_A be the circle center A, radius AD, and C_B the circle center B, radius BC. The circles touch on AB. Let C_P the the circle center P, radius h. C_P touches C_A and C_B and CD. Let t be the common tangent to C_A and C_B whose two points of contact are on the same side of AB as C and D. Then C_P is confined inside the curvilinear triangle whose sides are segments of t, C_A and C_B. Evidently h attains its maximum value, for given lengths AB, AD, BC, when C_P touches t, in which case D must be the point at which t touches C_A, and C the point at which it touches C_B. Suppose E is the point at which t touches C_P.

Angles ADC and BCD are right angles, so CD² = AB² - (AD - BC)² = 4 AD BC. Similarly, DE² = 4 h AD, and CE² = 4 h BC. But CD = DE + CE, so 1/√h = 1/√AD + 1/√BC. This gives the maximum value of h, so in general we have the inequality stated. 

Problem B2

Prove that for each positive integer n there exist n consecutive positive integers none of which is a prime or a prime power.

Solution

Consider (N!)²+2, (N!)²+3, ... , (N!)²+N. (N!)²+r is divisible by r, but ((N!)²+r)/r = N! (N!/r) + 1, which is greater than one, but relatively prime to r since N! (N!/r) is divisible by r. For each r we may take a prime p_r dividing r, so (N!)²+r is divisible by p_r, but is not a power of p_r. Hence it is not a prime or a prime power. Taking N = n+1 gives n consecutive numbers as required. 

Problem B3

A permutation {x₁, x₂, ... , x_m} of the set {1, 2, ... , 2n} where n is a positive integer is said to have property P if |x_i - x_i+1| = n for at least one i in {1, 2, ... , 2n-1}. Show that for each n there are more permutations with property P than without.

Solution

from Arthur Engel, Problem-Solving Strategies, Springer 1998 [Problem books in mathematics series], ISBN 0387982191. A rather good training book.

Let A_k be the set of permutations with k and k+n in neighboring positions, and let A be the set of permutations with property P, so that A is the union of the A_k.

Then |A| = Sum_k |A_k| - Sum_k<l |A_k∩A_l| + Sum_k<l<m |A_k∩A_l∩A_m| - ... . But this is an alternating sequence of monotonically decreasing terms, hence |A| ≥ ∑_k |A_k| - Sum_k<l |A_k∩A_l|.

But |A_k| = 2 (2n - 1)! (two orders for k, k+n and then (2n - 1)! ways of arranging the 2n - 1 items, treating k, k+n as a single item). Similarly, |A_k∩A_l| = 4 (2n - 2)! So |A| ≥ (2n - 2)! [n.2(2n -1) - n(n - 1)/2 4] = 2n² (2n - 2)! > (2n)!/2.

Read more

Hard Problems: The Road to the World's Toughest Math Contest 

The USSR Olympiad Problem Book: Selected Problems and Theorems of Elementary MathematicsMath Olympiad Contest Problems Volume 2 

Solutions are also available in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

[more...]

29th International Mathematical Olympiad 1988 Problems & Solutions

A1.  Consider two coplanar circles of radii R > r with the same center. Let P be a fixed point on the smaller circle and B a variable point on the larger circle. The line BP meets the larger circle again at C. The perpendicular to BP at P meets the smaller circle again at A (if it is tangent to the circle at P, then A = P). (i)  Find the set of values of AB² + BC² + CA².

(ii)  Find the locus of the midpoint of BC.

A2.  Let n be a positive integer and let A₁, A₂, ... , A_2n+1 be subsets of a set B. Suppose that:

(i)  Each A_i has exactly 2n elements,

(ii)  The intersection of every two distinct A_i contains exactly one element, and

(iii)  Every element of B belongs to at least two of the A_i.

For which values of n can one assign to every element of B one of the numbers 0 and 1 in such a way that each A_i has 0 assigned to exactly n of its elements?

A3.  A function f is defined on the positive integers by: f(1) = 1; f(3) = 3; f(2n) = f(n), f(4n + 1) = 2f(2n + 1) - f(n), and f(4n + 3) = 3f(2n + 1) - 2f(n) for all positive integers n. Determine the number of positive integers n less than or equal to 1988 for which f(n) = n.

B1.  Show that the set of real numbers x which satisfy the inequality:   1/(x - 1) + 2/(x - 2) + 3/(x - 3) + ... + 70/(x - 70) ≥ 5/4

is a union of disjoint intervals, the sum of whose lengths is 1988.

B2.  ABC is a triangle, right-angled at A, and D is the foot of the altitude from A. The straight line joining the incenters of the triangles ABD and ACD intersects the sides AB, AC at K, L respectively. Show that the area of the triangle ABC is at least twice the area of the triangle AKL.

B3.  Let a and b be positive integers such that ab + 1 divides a² + b². Show that (a² + b²)/(ab + 1) is a perfect square. 

Solutions

Problem A1

Consider two coplanar circles of radii R > r with the same center. Let P be a fixed point on the smaller circle and B a variable point on the larger circle. The line BP meets the larger circle again at C. The perpendicular to BP at P meets the smaller circle again at A (if it is tangent to the circle at P, then A = P).

(i)  Find the set of values of AB² + BC² + CA².
(ii)  Find the locus of the midpoint of BC.

Solution

(i)  Let M be the midpoint of BC. Let PM = x. Let BC meet the small circle again at Q. Let O be the center of the circles. Since angle APQ = 90 degrees, AQ is a diameter of the small circle, so its length is 2r. Hence AP² = 4r² - 4x². BM² = R² - OM² = R² - (r² - x²). That is essentially all we need, because we now have: AB² + AC² + BC² = (AP² + (BM - x)²) + (AP² + (BM + x)²) + 4BM² = 2AP² + 6BM² + 2x² = 2(4r² - 4x²) + 6(R² - r² + x²) + 2x² = 6R² + 2r² , which is independent of x.

(ii)  M is the midpoint of BC and PQ since the circles have a common center. If we shrink the small circle by a factor 2 with P as center, then Q moves to M, and hence the locus of M is the circle diameter OP. 

Problem A2

Let n be a positive integer and let A₁, A₂, ... , A_2n+1 be subsets of a set B. Suppose that:
(i)  Each A_i has exactly 2n elements,
(ii)  The intersection of every two distinct A_i contains exactly one element, and
(iii)  Every element of B belongs to at least two of the A_i.
For which values of n can one assign to every element of B one of the numbers 0 and 1 in such a way that A_i has 0 assigned to exactly n of its elements?

Solution

Answer: n even.

Each of the 2n elements of A_i belongs to at least one other A_j because of (iii). But given another A_j it cannot contain more than one element of A_i because of (ii). There are just 2n other A_j available, so each must contain exactly one element of A_i. Hence we can strengthen (iii) to every element of B belongs to exactly two of the As.

This shows that the arrangement is essentially unique. We may call the element of B which belongs to A_i and A_j (i,j). Then A_i contains the 2n elements (i, j) with j not i.

|B| = 1/2 x no. of As x size of each A = n(2n+1). If the labeling with 0s and 1s is possible, then if we list all the elements in each A, n(2n+1) out of the 2n(2n+1) elements have value 0. But each element appears twice in this list, so n(2n+1) must be even. Hence n must be even.

Next part thanks to Stan Dolan

Label (i,j) 0 if j = i-n/2, i-(n/2 - 1), ... , i-1, i+1, i+2, ... , i+n/2 (working mod 2n+1 when necessary). This clearly has the required property.

My original solution was a pedestrian induction:

We show by induction that a labeling is always possible for n even. If n = 2, there is certainly a labeling. For example, we may assign 0 to (1,2), (1,3), (2,4), (3,5), (4,5). Now suppose we have a labeling for n. For n + 2, we label (i , j) 0 if it was labeled 0 for n or if it is:
    (i, 2n+2) or (i, 2n+3) for i = 1, 2, ... , n+1
    (i, 2n+4) or (i, 2n+5) for i = n+2, n+3, ... , 2n+1
    (2n+2, 2n+4), (2n+3, 2n+5), (2n+4,2n+5).
For i = 1, 2, ... n+1, A_i has n elements (i, j) labeled zero with j ≤ 2n+1 and also (i, 2n+2) and (i, 2n+3), giving n+2 in all. For i = n+2, n+3, ... , 2n+1, A_i has n elements (i, j) labeled zero with j ≤ 2n+1 and also (i, 2n+4) and (i, 2n+5), giving n+2 in all. A_2n+2 has the n+1 elements (i, 2n+2) with i <= n+1 and also (2n+2, 2n+4), giving n+2 in all. A_2n+3 has the n+1 elements (i, 2n+3) for i ≤ n+1 and also (2n+3, 2n+5), giving n+2 in all. A_2n+4 has the n elements (i, 2n+4) with n+2 ≤ i ≤ 2n+1 and also (2n+2, 2n+4) and (2n+4, 2n+5), giving n+2 in all. Finally A_2n+5 has the n elements (i, 2n+5) with n+2 ≤ i ≤ 2n+1 and also (2n+3, 2n+5) and (2n+4, 2n+5), giving n+2 in all. 

Problem A3

A function f is defined on the positive integers by: f(1) = 1; f(3) = 3; f(2n) = f(n), f(4n + 1) = 2f(2n + 1) - f(n), and f(4n + 3) = 3f(2n + 1) - 2f(n) for all positive integers n. Determine the number of positive integers n less than or equal to 1988 for which f(n) = n.

Solution

Answer: 92.

f(n) is always odd. If n = b_r+1b_r...b₂b₁b₀ in binary and n is odd, so that b_r+1 = b₀ = 1, then f(n) = b_r+1b₁b₂...b_rb₀. If n has r+2 binary digits with r > 0, then there are 2^[(r+1)/2] numbers with the central r digits symmetrical, so that f(n) = n (because we can choose the central digit and those lying before it arbitarily, the rest are then determined). Also there is one number with 1 digit (1) and one number with two digits (3) satisfying f(n) = 1. So we find a total of 1 + 1 + 2 + 2 + 4 + 4 + 8 + 8 + 16 + 16 = 62 numbers in the range 1 to 1023 with f(n) = n. 1988 = 11111000011. So we also have all 32 numbers in the range 1023 to 2047 except for 11111111111 and 11111011111, giving another 30, or 92 in total.

It remains to prove the assertions above. f(n) odd follows by an easy induction. Next we show that if 2^m < 2n+1 < 2^m+1, then f(2n+1) = f(n) + 2^m. Again we use induction. It is true for m = 1 (f(3) = f(1) + 2). So suppose it is true for 1, 2, ... , m. Take 4n+1 so that 2^m+1 < 4n+1 < 2^m+2, then f(4n+1) = 2f(2n+1) - f(n) = 2(f(n) + 2^m) - f(n) = f(n) + 2^m+1 = f(2n) + 2^m+1, so it is true for 4n+1. Similarly, if 4n+3 satisfies, 2^m+1 < 4n+3 < 2^m+2, then f(4n+3) = 3f(2n+1) - 2f(n) = f(2n+1) + 2(f(n) + 2^m) - 2f(n) = f(2n+1) + 2^m+1, so it is true for 4n+3 and hence for m+1.

Finally, we prove the formula for f(2n+1). Let 2n+1 = b_r+1b_r...b₂b₁b₀ with b₀ = b_r+1 = 1. We use induction on r. So assume it is true for smaller values. Say b₁ = ... = b_s = 0 and b_s+1 = 1 (we may have s = 0, so that we have simply b₁ = 1). Then n = b_r+1 ... b₁ and f(n) = b_r+1b_s+2b_s+3...b_rb_s+1 by induction. So f(n) + 2^r+1 = b_r+10...0b_r+1b_s+2...b_rb_s+1, where there are s zeros. But we may write this as b_r+1b₁...b_sb_s+1...b_rb_r+1, since b₁ = ... = b_s = 0, and b_s+1 = b_r+1 = 1. But that is the formula for f(2n+1), so we have completed the induction. 

Problem B1

Show that the set of real numbers x which satisfy the inequality:

  1/(x - 1) + 2/(x - 2) + 3/(x - 3) + ... + 70/(x - 70) ≥ 5/4

is a union of disjoint intervals, the sum of whose lengths is 1988.

Solution

Let f(x) = 1/(x - 1) + 2/(x - 2) + 3/(x - 3) + ... + 70/(x - 70). For any integer n, n/(x - n) is strictly monotonically decreasing except at x = n, where it is discontinuous. Hence f(x) is strictly monotonically decreasing except at x = 1, 2, ... , 70. For n = any of 1, 2, ... , 70, n/(x - n) tends to plus infinity as x tends to n from above, whilst the other terms m/(x - m) remain bounded. Hence f(x) tends to plus infinity as x tends to n from above. Similarly, f(x) tends to minus infinity as x tends to n from below. Thus in each of the intervals (n, n+1) for n = 1, ... , 69, f(x) decreases monotonically from plus infinity to minus infinity and hence f(x) = 5/4 has a single foot x_n. Also f(x) ≥ 5/4 for x in (n, x_n] and f(x) < 5/4 for x in (x_n, n+1). If x < 0, then every term is negative and hence f(x) < 0 < 5/4. Finally, as x tends to infinity, every term tends to zero, so f(x) tends to zero. Hence f(x) decreases monotonically from plus infinity to zero over the range [70, infinity]. Hence f(x) = 5/4 has a single root x₇₀ in this range and f(x) >= 5/4 for x in (70, x₇₀] and f(x) < 5/4 for x > x₇₀. Thus we have established that f(x) ≥ 5/4 for x in any of the disjoint intervals (1, x₁], (2, x₂], ... , (70, x₇₀] and f(x) < 5/4 elsewhere.

The total length of these intervals is (x₁ - 1) + ... + (x₇₀ - 70) = (x₁ + ... + x₇₀) - (1 + ... + 70). The x_i are the roots of the 70th order polynomial obtained from 1/(x - 1) + 2/(x - 2) + 3/(x - 3) + ... + 70/(x - 70) = 5/4 by multiplying both sides by (x - 1) ... (x - 70). The sum of the roots is minus the coefficient of x⁶⁹ divided by the coefficient of x⁷⁰. The coefficient of x⁷⁰ is simply k, and the coefficient of x⁶⁹ is - (1 + 2 + ... + 70)k - (1 + ... + 70). Hence the sum of the roots is (1 + ... + 70)(1 + k)/k and the total length of the intervals is (1 + ... + 70)/k = 1/2 70·71 4/5 = 28·71 = 1988. 

Problem 5

ABC is a triangle, right-angled at A, and D is the foot of the altitude from A. The straight line joining the incenters of the triangles ABD and ACD intersects the sides AB, AC at K, L respectively. Show that the area of the triangle ABC is at least twice the area of the triangle AKL.

Solution

The key is to show that AK = AL = AD. We do this indirectly. Take K' on AB and L' on AC so that AK' = AL' = AD. Let the perpendicular to AB at K' meet the line AD at X. Then the triangles AK'X and ADB are congruent. Let J be the incenter of ADB and let r be the in-radius of ADB. Then J lies on the angle bisector of angle BAD a distance r from the line AD. Hence it is also the incenter of AK'X. Hence JK' bisects the right angle AK'X, so ∠AK'J = 45^o and so J lies on K'L'. An exactly similar argument shows that I, the incenter of ADC, also lies on K'L'. Hence we can identify K and K', and L and L'.

The area of AKL is AK·AL/2 = AD²/2, and the area of ABC is BC·AD/2, so we wish to show that 2AD ≤ BC. Let M be the midpoint of BC. Then AM is the hypoteneuse of AMD, so AM ≥ AD with equality if and only if D = M. Hence 2AD ≤ 2AM = BC with equality if and only if AB = AC. 

Problem B3

Let a and b be positive integers such that ab + 1 divides a² + b². Show that (a² + b²)/(ab + 1) is a perfect square.

Solution

A little experimentation reveals the following solutions: a, a³ giving a²; a³, a⁵ - a giving a²; and the recursive a₁ = 2, b₁ = 8, a_n+1 = b_n, b_n+1 = 4b_n - a_n giving 4. The latter may lead us to: if a² + b² = k(ab + 1), then take A = b, B = kb - a, and then A² + B² = k(AB + 1). Finally, we may notice that this can be used to go down as well as up.

So starting again suppose that a, b, k is a solution in positive integers to a² + b² = k(ab + 1). If a = b, then 2a² = k(a² + 1). So a² must divide k. But that implies that a = b = k = 1. Let us assume we do not have this trivial solution, so we may take a < b. We also show that a³ > b. For (b/a - 1/a)(ab + 1) = b² + b/a - b - 1/a < b² < a² + b². So k > b/a - 1/a. But if a³ < b, then b/a (ab + 1) > b² + a², so k < b/a. But now b > ak and < ak + 1, which is impossible. It follows that k ≥ b/a.

Now define A = ka - b, B = a. Then we can easily verify that A, B, k also satisfies a² + b² = k(ab + 1), and B and k are positive integers. Also a < b implies a² + b² < ab + b² < ab + b² + 1 + b/a = (ab + 1)(1 + b/a), and hence k < 1 + b/a, so ka - b < a. Finally, since k > b/a, ka - b ≥ 0. If ka - b > 0, then we have another smaller solution, in which case we can repeat the process. But we cannot have an infinite sequence of decreasing numbers all greater than zero, so we must eventually get A = ka - b = 0. But now A² + B² = k(AB + 1), so k = B². k was unchanged during the descent, so k is a perfect square.

A slightly neater variation on this is due to Stan Dolan

As above take a² + b² = k(ab + 1), so a, b, and k are all positive integers. Now fixing k take positive integers A, B such that A² + B² = k(AB + 1) (*) and min(A,B) is as small as possible. Assume B ≤ A. Regarding (*) as a quadratic for A, we see that the other root C satisfies A + C = kB, AC = B² - k. The second equation implies that C = B²/A - k/A < B. So C cannot be a positive integer (or the solution C, B would have min(C,B) < min(A,B)). But we have (A+1)(C+1) = A+C + AC + 1 = B² + (B-1)k + 1 > 0, so C > -1. C = kB - A is an integer, so C = 0. Hence k = B². 

Note that jumping straight to the minimal without the infinite descent avoids some of the verification needed in the infinite descent.

Read more

 

Solutions are also available in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.  

[more...]

28th International Mathematical Olympiad 1987 Problems & Solutions

A1.  Let p_n(k) be the number of permutations of the set {1, 2, 3, ... , n} which have exactly k fixed points. Prove that the sum from k = 0 to n of (k p_n(k) ) is n!. [A permutation f of a set S is a one-to-one mapping of S onto itself. An element i of S is called a fixed point if f(i) = i.]

A2.  In an acute-angled triangle ABC the interior bisector of angle A meets BC at L and meets the circumcircle of ABC again at N. From L perpendiculars are drawn to AB and AC, with feet K and M respectively. Prove that the quadrilateral AKNM and the triangle ABC have equal areas.

A3.  Let x₁, x₂, ... , x_n be real numbers satisfying x₁² + x₂² + ... + x_n² = 1. Prove that for every integer k ≥ 2 there are integers a₁, a₂, ... , a_n, not all zero, such that |a_i| ≤ k - 1 for all i, and |a₁x₁ + a₂x₂ + ... + a_nx_n| ≤ (k - 1)√n/(kⁿ - 1).

B1.  Prove that there is no function f from the set of non-negative integers into itself such that f(f(n)) = n + 1987 for all n.

B2.  Let n be an integer greater than or equal to 3. Prove that there is a set of n points in the plane such that the distance between any two points is irrational and each set of 3 points determines a non-degenerate triangle with rational area.

B3.  Let n be an integer greater than or equal to 2. Prove that if k² + k + n is prime for all integers k such that 0 ≤ k ≤ √(n/3), then k² + k + n is prime for all integers k such that 0 ≤ k ≤ n-2. 

Solutions

Problem A1

1.  Let p_n(k) be the number of permutations of the set {1, 2, 3, ... , n} which have exactly k fixed points. Prove ∑₀ⁿ (k p_n(k) ) = n!.

First Solution

We show first that the number of permutations of n objects with no fixed points is n!(1/0! - 1/1! + 1/2! - ... + (-1)ⁿ/n!). This follows immediately from the law of inclusion and exclusion: let N_i be the number which fix i, N_ij the number which fix i and j, and so on. Then N₀, the number with no fixed points, is n! - all N_i + all N_ij - ... + (-1)ⁿN_1...n. But N_i = (n-1)!, N_ij = (n-2)! and so on. So N₀ = n! ( 1 - 1/1! + ... + (-1)^r(n-r)!/(r! (n-r)!) + ... + (-1)ⁿ/n!) = n! (1/0! - 1/1! + ... + (-1)ⁿ/n!).

Hence the number of permutations of n objects with exactly r fixed points = no. of ways of choosing the r fixed points x no. of perms of the remaining n - r points with no fixed points = n!/(r! (n-r)!) x (n-r)! (1/0! - 1/1! + ... + (-1)^n-r/(n-r)! ). Thus we wish to prove that the sum from r = 1 to n of 1/(r-1)! (1/0! - 1/1! + ... + (-1)^n-r/(n-r)! ) is 1. We use induction on n. It is true for n = 1. Suppose it is true for n. Then the sum for n+1 less the sum for n is: 1/0! (-1)ⁿ/n! + 1/1! (-1)^n-1/(n-1)! + ... + 1/n! 1/0! = 1/n! (1 - 1)ⁿ = 0. Hence it is true for n + 1, and hence for all n.

Comment

This is a plodding solution. If you happen to know the result for no fixed points (which many people do), then it is essentially a routine induction.

Second solution

Count all pairs (x, s) where s is a permutation with x a fixed point of x. Clearly, if we fix x, then there are (n-1)! possible permutations s. So the total count is n!. But if we count the number of permutations s with exactly k fixed points, then we get the sum in the question.

Comment

This much more elegant solution is due to Gerhard Wöginger (email 24 Aug 99).  

Problem A2

In an acute-angled triangle ABC the interior bisector of angle A meets BC at L and meets the circumcircle of ABC again at N. From L perpendiculars are drawn to AB and AC, with feet K and M respectively. Prove that the quadrilateral AKNM and the triangle ABC have equal areas.

Solution

by Gerhard Wöginger

AKL and AML are congruent, so KM is perpendicular to AN and area AKNM = KM.AN/2.
AKLM is cyclic (2 opposite right angles), so angle AKM = angle ALM and hence KM/sin BAC = AM/sin AKM (sine rule) = AM/sin ALM = AL.
ABL and ANC are similar, so AB.AC = AN.AL. Hence area ABC = 1/2 AB.AC sin BAC = 1/2 AN.AL sin BAC = 1/2 AN.KM = area AKNM. 

Problem A3

Let x₁, x₂, ... , x_n be real numbers satisfying x₁² + x₂² + ... + x_n² = 1. Prove that for every integer k ≥ 2 there are integers a₁, a₂, ... , a_n, not all zero, such that |a_i| ≤ k - 1 for all i, and |a₁x₁ + a₂x₂ + ... + a_nx_n| ≤ (k - 1)√n/(kⁿ - 1).

Solution

This is an application of the pigeon-hole principle.

Assume first that all x_i are non-negative. Observe that the sum of the x_i is at most √n. [This is a well-known variant, (∑_1≤i≤n x_i)² ≤ n ∑_1≤i≤n x_i², of the AM-GM result. See, for example, Arthur Engel, Problem Solving Strategies, Springer 1998, p163, ISBN 0387982191].

Consider the kⁿ possible values of ∑_1≤i≤n b_ix_i, where each b_i is an integer in the range [0,k-1]. Each value must lie in the interval [0, k-1 √n]. Divide this into kⁿ-1 equal subintervals. Two values must lie in the same subinterval. Take their difference. Its coefficients are the required a_i. Finally, if any x_i are negative, solve for the absolute values and then flip signs in the a_i.

Comment

This solution is due to Gerhard Woeginger, email 24 Aug 99.  

Problem B1

Prove that there is no function f from the set of non-negative integers into itself such that f(f(n)) = n + 1987 for all n.

Solution

We prove that if f(f(n)) = n + k for all n, where k is a fixed positive integer, then k must be even. If k = 2h, then we may take f(n) = n + h.

Suppose f(m) = n with m = n (mod k). Then by an easy induction on r we find f(m + kr) = n + kr, f(n + kr) = m + k(r+1). We show this leads to a contradiction. Suppose m < n, so n = m + ks for some s > 0. Then f(n) = f(m + ks) = n + ks. But f(n) = m + k, so m = n + k(s - 1) ≥ n. Contradiction. So we must have m ≥ n, so m = n + ks for some s ≥ 0. But now f(m + k) = f(n + k(s+1)) = m + k(s + 2). But f(m + k) = n + k, so n = m + k(s + 1) > n. Contradiction.

So if f(m) = n, then m and n have different residues mod k. Suppose they have r₁ and r₂ respectively. Then the same induction shows that all sufficiently large s = r₁ (mod k) have f(s) = r₂ (mod k), and that all sufficiently large s = r₂ (mod k) have f(s) = r₁ (mod k). Hence if m has a different residue r mod k, then f(m) cannot have residue r₁ or r₂. For if f(m) had residue r₁, then the same argument would show that all sufficiently large numbers with residue r₁ had f(m) = r (mod k). Thus the residues form pairs, so that if a number is congruent to a particular residue, then f of the number is congruent to the pair of the residue. But this is impossible for k odd.

A better solution by Sawa Pavlov is as follows

Let N be the set of non-negative integers. Put A = N - f(N) (the set of all n such that we cannot find m with f(m) = n). Put B = f(A).

Note that f is injective because if f(n) = f(m), then f(f(n)) = f(f(m)) so m = n. We claim that B = f(N) - f( f(N) ). Obviously B is a subset of f(N) and if k belongs to B, then it does not belong to f( f(N) ) since f is injective. Similarly, a member of f( f(N) ) cannot belong to B.

Clearly A and B are disjoint. They have union N - f( f(N) ) which is {0, 1, 2, ... , 1986}. But since f is injective they have the same number of elements, which is impossible since {0, 1, ... , 1986} has an odd number of elements.

Problem B2

Let n be an integer greater than or equal to 3. Prove that there is a set of n points in the plane such that the distance between any two points is irrational and each set of 3 points determines a non-degenerate triangle with rational area.

Solution

Let x_n be the point with coordinates (n, n²) for n = 1, 2, 3, ... . We show that the distance between any two points is irrational and that the triangle determined by any 3 points has non-zero rational area.

Take n > m. |x_n - x_m| is the hypoteneuse of a triangle with sides n - m and n² - m² = (n - m)(n + m). So |x_n - x_m| = (n - m)√(1 + (n+m)²). Now (n + m)² < (n + m)² + 1 < (n + m + 1)² = (n + m)² + 1 + 2(n + m), so (n + m)² + 1 is not a perfect square. Hence its square root is irrational. [For this we may use the classical argument. Let N' be a non-square and suppose √N' is rational. Since N' is a non-square we must be able to find a prime p such that p^2a+1 divides N' but p^2a+2 does not divide N' for some a ≥ 0. Define N = N'/p^2a. Then √N = (√N')/p^a, which is also rational. So we have a prime p such that p divides N, but p² does not divide N. Take √N = r/s with r and s relatively prime. So s²N = r². Now p must divide r, hence p² divides r² and so p divides s². Hence p divides s. So r and s have a common factor. Contradiction. Hence non-squares have irrational square roots.]

Now take a < b < c. Let B be the point (b, a²), C the point (c, a²), and D the point (c, b²). Area x_ax_bx_c = area x_ax_cC - area x_ax_bB - area x_bx_cD - area x_bDCB = (c - a)(c² - a²)/2 - (b - a)(b² - a²)/2 - (c - b)(c² - b²)/2 - (c - b)(b² - a²) which is rational. 

Problem B3

Let n be an integer greater than or equal to 2. Prove that if k² + k + n is prime for all integers k such that 0 ≤ k ≤ √(n/3), then k² + k + n is prime for all integers k such that 0 ≤ k ≤ n - 2.

Solution

First observe that if m is relatively prime to b + 1, b + 2, ... , 2b - 1, 2b, then it is not divisible by any number less than 2b. For if c <= b, then take the largest j ≥ 0 such that 2^jc ≤ b. Then 2^j+1c lies in the range b + 1, ... , 2b, so it is relatively prime to m. Hence c is also. If we also have that (2b + 1)² > m, then we can conclude that m must be prime, since if it were composite it would have a factor ≤ √m.

Let n = 3r² + h, where 0 ≤ h < 6r + 3, so that r is the greatest integer less than or equal to √(n/3). We also take r ≥ 1. That excludes the value n = 2, but for n = 2, the result is vacuous, so nothing is lost.

Assume that n + k(k+1) is prime for k = 0, 1, ... , r. We show by induction that N = n + (r + s)(r + s + 1) is prime for s = 1, 2, ... , n - r - 2. By the observation above, it is sufficient to show that (2r + 2s + 1)² > N, and that N is relatively prime to all of r + s + 1, r + s + 2, ... , 2r + 2s. We have (2r + 2s + 1)² = 4r² + 8rs + 4s² + 4r + 4s + 1. Since r, s ≥ 1, we have 4s + 1 > s + 2, 4s² > s², and 6rs > 3r. Hence (2r + 2s + 1)² > 4r² + 2rs + s² + 7r + s + 2 = 3r² + 6r + 2 + (r + s)(r + s + 1) >= N.

Now if N has a factor which divides 2r - i with i in the range -2s to r - s - 1, then so does N - (i + 2s + 1)(2r - i) = n + (r - i - s - 1)(r - i - s) which has the form n + s'(s'+1) with s' in the range 0 to r + s - 1. But n + s'(s' + 1) is prime by induction (or absolutely for s = 1), so the only way it can have a factor in common with 2r - i is if it divides 2r - i. But 2r - i ≤ 2r + 2s ≤ 2n - 4 < 2n and n + s'(s' + 1) ≥ n, so if n + s'(s' + 1) has a factor in common with 2r - i, then it equals 2r - i = s + r + 1 + s'. Hence s'² = s - (n - r - 1) < 0, which is not possible. So we can conclude that N is relatively prime to all of r + s + 1, ... , 2r + 2s and hence prime.  

Read more

Solutions are also available in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

Creative Problem Solving in School Mathematics, Revised and Expanded 2nd Edition 

Mathematical Olympiad Challenges 

Challenge Math For the Elementary and Middle School Student (Second Edition) 

Math Olympiad Contest Problems for Elementary and Middle Schools, Vol. 1 

[more...]

27th International Mathematical Olympiad 1986 Problems & Solutions

A1.  Let d be any positive integer not equal to 2, 5 or 13. Show that one can find distinct a, b in the set {2, 5, 13, d} such that ab - 1 is not a perfect square.

A2.  Given a point P₀ in the plane of the triangle A₁A₂A₃. Define A_s = A_s-3 for all s >= 4. Construct a set of points P₁, P₂, P₃, ... such that P_k+1 is the image of P_k under a rotation center A_k+1 through an angle 120^o clockwise for k = 0, 1, 2, ... . Prove that if P₁₉₈₆ = P₀, then the triangle A₁A₂A₃ is equilateral.

A3.  To each vertex of a regular pentagon an integer is assigned, so that the sum of all five numbers is positive. If three consecutive vertices are assigned the numbers x, y, z respectively, and y < 0, then the following operation is allowed: x, y, z are replaced by x + y, -y, z + y respectively. Such an operation is performed repeatedly as long as at least one of the five numbers is negative. Determine whether this procedure necessarily comes to an end after a finite number of steps.

B1.  Let A, B be adjacent vertices of a regular n-gon (n ≥ 5) with center O. A triangle XYZ, which is congruent to and initially coincides with OAB, moves in the plane in such a way that Y and Z each trace out the whole boundary of the polygon, with X remaining inside the polygon. Find the locus of X.

B2.  Find all functions f defined on the non-negative reals and taking non-negative real values such that: f(2) = 0, f(x) ≠ 0 for 0 ≤ x < 2, and f(xf(y)) f(y) = f(x + y) for all x, y.

B3.  Given a finite set of points in the plane, each with integer coordinates, is it always possible to color the points red or white so that for any straight line L parallel to one of the coordinate axes the difference (in absolute value) between the numbers of white and red points on L is not greater than 1? 

Solutions

Problem A1

Let d be any positive integer not equal to 2, 5 or 13. Show that one can find distinct a, b in the set {2, 5, 13, d} such that ab - 1 is not a perfect square.

 

Solution

Consider residues mod 16. A perfect square must be 0, 1, 4 or 9 (mod 16). d must be 1, 5, 9, or 13 for 2d - 1 to have one of these values. However, if d is 1 or 13, then 13d - 1 is not one of these values. If d is 5 or 9, then 5d - 1 is not one of these values. So we cannot have all three of 2d - 1, 5d - 1, 13d - 1 perfect squares.

Alternative solution from Marco Dalai

Suppose 2d-1, 5d-1, 13d-1 are all squares. Squares mod 4 must be 0 or 1, considering 2d-1, so d must be odd. Put d = 2k+1. Then 10k+4 = b². So b must be even, so k must be even. Put k = 2h, then 5k+1 is a square. Similarly, 52h+12 is a square, so 13h+3 is a square. Hence (13h+3)-(5h+1) = 8h+2 is a difference of two squares, which is impossible (a difference of two squares must be 0, 1, or 3 mod 4). 

Problem A2

Given a point P₀ in the plane of the triangle A₁A₂A₃. Define A_s = A_s-3 for all s ≥ 4. Construct a set of points P₁, P₂, P₃, ... such that P_k+1 is the image of P_k under a rotation center A_k+1 through 120^o clockwise for k = 0, 1, 2, ... . Prove that if P₁₉₈₆ = P₀, then the triangle A₁A₂A₃ is equilateral.

 

Solution

The product of three successive rotations about the three vertices of a triangle must be a translation (see below). But that means that P₁₉₈₆ (which is the result of 662 such operations, since 1986 = 3 x 662) can only be P₀ if it is the identity, for a translation by a non-zero amount would keep moving the point further away. It is now easy to show that it can only be the identity if the triangle is equilateral. Take a circle center A₁, radius A₁A₂ and take P on the circle so that a 120^o clockwise rotation about A₁ brings P to A₂. Take a circle center A₃, radius A₃A₂ and take Q on the circle so that a 120^o clockwise rotation about A₃ takes A₂ to Q. Then successive 120^o clockwise rotations about A₁, A₂, A₃ take P to Q. So if these three are equivalent to the identity we must have P = Q. Hence ∠A₁A₂A₃ = ∠A₁A₂P + ∠A₃A₂P = 30^o + 30^o = 60^o. Also A₂P = 2A₁A₂cos 30^o and = 2A₂A₃cos 30^o. Hence A₁A₂ = A₂A₃. So A₁A₂A₂ is equilateral. Note in passing that it is not sufficient for the triangle to be equilateral. We also have to take the rotations in the right order. If we move around the vertices the opposite way, then we get a net translation.

It remains to show that the three rotations give a translation. Define rectangular coordinates (x, y) by taking A₁ to be the origin and A₂ to be (a, b). Let A₃ be (c, d). A clockwise rotation through 120 degrees about the origin takes (x, y) to (-x/2 + y√3/2, -x√3/2 - y/2). A clockwise rotation through 120 degrees about some other point (e, f) is obtained by subtracting (e, f) to get (x - e, y - f), the coordinates relative to (e, f), then rotating, then adding (e, f) to get the coordinates relative to (0, 0). Thus after the three rotations we will end up with a linear combination of x's, y's, a's, b's, c's and d's for each coordinate. But the linear combination of x's and y's must be just x for the x-coordinate and y for the y-coordinate, since three successive 120 degree rotations about the same point is the identity. Hence we end up with simply (x + constant, y + constant), in other words, a translation.

[Of course, there is nothing to stop you actually carrying out the computation. It makes things slightly easier to take the triangle to be (0, 0), (1, 0), (a, b). The net result turns out to be (x, y) goes to (x + 3a/2 - b√3/2, y - √3 + a√3/2 + 3b/2). For this to be the identity requires a = 1/2, b = √3/2. So the third vertex must make the triangle equilateral (and it must be on the correct side of the line joining the other two). This approach avoids the need for the argument in the first paragraph above, but is rather harder work.]  

Problem A3

To each vertex of a regular pentagon an integer is assigned, so that the sum of all five numbers is positive. If three consecutive vertices are assigned the numbers x, y, z respectively, and y < 0, then the following operation is allowed: x, y, z are replaced by x + y, -y, z + y respectively. Such an operation is performed repeatedly as long as at least one of the five numbers is negative. Determine whether this procedure necessarily comes to an end after a finite number of steps.

 

Solution

Let S be the sum of the absolute value of each set of adjacent vertices, so if the integers are a, b, c, d, e, then S = |a| + |b| + |c| + |d| + |e| + |a + b| + |b + c| + |c + d| + |d + e| + |e + a| + |a + b + c| + |b + c + d| + |c + d + e| + |d + e + a| + |e + a + b| + |a + b + c + d| + |b + c + d + e| + |c + d + e + a| + |d + e + a + b| + |e + a + b + c| + |a + b + c + d + e|. Then the operation reduces S, but S is a greater than zero, so the process must terminate in a finite number of steps. So see that S is reduced, we can simply write out all the terms. Suppose the integers are a, b, c, d, e before the operation, and a+b, -b, b+c, d, e after it. We find that we mostly get the same terms before and after (although not in the same order), so that the sum S' after the operation is S - |a + c + d + e| + |a + 2b + c + d + e|. Certainly a + c + d + e > a + 2b + c + d + e since b is negative, and a + c + d + e > -(a + 2b+ c + d + e) because a + b + c + d + e > 0.

S is not the only expression we can use. If we take T = (a - c)² + (b - d)² + (c - e)² + (d - a)² +(e - b)², then after replacing a, b, c by a+b, -b, b+c, we get T' = T + 2b(a + b + c + d + e) < T. Thanks to Demetres Chrisofides for T

Problem B1

Let A, B be adjacent vertices of a regular n-gon (n ≥ 5) with center O. A triangle XYZ, which is congruent to and initially coincides with OAB, moves in the plane in such a way that Y and Z each trace out the whole boundary of the polygon, with X remaining inside the polygon. Find the locus of X.

 

Solution

Take AB = 2 and let M be the midpoint of AB. Take coordinates with origin at A, x-axis as AB and y-axis directed inside the n-gon. Let Z move along AB from B towards A. Let ∠YZA be t. Let the coordinates of X be (x, y). ∠YZX = π/2 - π/n, so XZ = 1/sin π/n and y = XZ sin(t + π/2 - π/n) = sin t + cot π/n cos t.

BY sin 2π/n = YZ sin t = 2 sin t. MX = cot π/n. So x = MY cos t - BY cos 2π/n + MX sin t = cos t + (cot π/n - 2 cot 2π/n) sin t = cos t + tan π/n sin t = y tan π/n. Thus the locus of X is a star formed of n lines segments emanating from O. X moves out from O to the tip of a line segement and then back to O, then out along the next segment and so on. x² + y² = (1/sin²π/n + 1/cos²π/n) cos²(t + π/n). Thus the length of each segment is (1 - cos π/n)/(sin π/n cos π/n). 

Problem B2

Find all functions f defined on the non-negative reals and taking non-negative real values such that: f(2) = 0, f(x) ≠ 0 for 0 ≤ x < 2, and f(xf(y)) f(y) = f(x + y) for all x, y.

 

Solution

f(x+2) = f(xf(2)) f(2) = 0. So f(x) = 0 for all x ≥ 2.

f(y) f((2-y)f(y)) = f(2) = 0. So if y < 2, then f((2-y) f(y)) = 0 and hence (2 - y) f(y) ≥ 2, or f(y) ≥ 2/(2 - y).

Suppose that for some y₀ we have f(y₀) > 2/(2 - y₀), then we can find y₁ > y₀ (and y₁ < 2) so that f(y₀) = 2/(2 - y₁). Now let x₁ = 2 - y₁. Then f(x₁f(y₀)) = f(2) = 0, so f(x₁ + y₀) = 0. But x₁ + y₀ < 2. Contradiction. So we must have f(x) = 2/(2 - x) for all x < 2.

We have thus established that if a function f meets the conditions then it must be defined as above. It remains to prove that with this definition f does meet the conditions. Clearly f(2) = 0 and f(x) is non-zero for 0 ≤ x < 2. f(xf(y)) = f(2x/(2 - y)). If 2x/(2 - y) ≥ 2, then f(xf(y)) = 0. But it also follows that x + y ≥ 2, and so f(x + y) = 0 and hence f(xf(y)) f(y) = f(x + y) as required. If 2x/(2 - y) < 2, then f(xf(y)) f(y) = 2/(2 - 2x/(2-y)) 2/(2 - y) = 2/(2 - x - y) = f(x + y). So the unique function satisfying the conditions is:

      f(x) = 0 for x ≥ 2, and 2/(2 - x) for 0 ≤ x < 2. 

Problem B3

Given a finite set of points in the plane, each with integer coordinates, is it always possible to color the points red or white so that for any straight line L parallel to one of the coordinate axes the difference (in absolute value) between the numbers of white and red points on L is not greater than 1?

 

Solution

Answer: yes.

We prove the result by induction on the number n of points. It is clearly true for n = 1. Suppose it is true for all numbers less than n. Pick an arbitrary point P and color it red. Now take a point in the same row and color it white. Take a point in the same column as the new point and color it red. Continue until either you run out of eligible points or you pick a point in the same column as P. The process must terminate because there are only finitely many points. Suppose the last point picked is Q. Let S be the set of points picked.

If Q is in the same column as P, then it is colored white (because the "same row" points are all white, and the "same column" points are all red). Now every row and column contains an equal number of red points of S and of white points of S. By induction we can color the points excluding those in S, then the difference between the numbers of red and white points in each row and column will be unaffected by adding the points in S and so we will have a coloring for the whole set. This completes the induction for the case where Q is in the same column as P.

If it is not, then continue the path backwards from P. In other words, pick a point in the same column as P and color it white. Then pick a point in the same row as the new point and color it red and so on. Continue until either you run out of eligible points or you pick a point to pair with Q. If Q was picked as being in the same row as its predecessor, this means a point in the same column as Q; if Q was picked as being in the same column as its predecessor, this means a point in the same row as Q. Again the process must terminate. Suppose the last point picked is R. Let S be the set of all points picked.

If R pairs with Q, then we can complete the coloring by induction as before. Suppose S does not pair with Q. Then there is a line (meaning a row or column) containing Q and no uncolored points. There is also a line containing R and no uncolored points. These two lines have an excess of one red or one white. All other lines contain equal number of red and white points of S. Now color the points outside S by induction. This gives a coloring for the whole set, because no line with a color excess in S has any points outside S. So we have completed the induction.

Read more

 

 

Solutions are also available in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X. 

[more...]