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 (2n + 1)/n2 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 n0 > 1, two players A and B choose integers n1, n2, n3, ... alternately according to the following rules:
Knowing n2k, A chooses any integer n2k+1 such that n2k ≤ n2k+1 ≤ n2k2.
Knowing n2k+1, B chooses any integer n2k+2 such that n2k+1/n2k+2 = pr 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 n0 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 12, 22, ... , 19902 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 = 180o - ∠CEF = 180o - ∠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 (2n + 1)/n2 is an integer.
Solution
by Gerhard Wöginger, Technical University, Graz
Answer: n = 3.
Since 2n + 1 is odd, n must also be odd. Let p be its smallest prime divisor. Let x be the smallest positive integer such that 2x = -1 (mod p), and let y be the smallest positive integer such that 2y = 1 (mod p). y certainly exists and indeed y < p, since 2p-1 = 1 (mod p). x exists since 2n = -1 (mod p). Write n = ys + r, with 0 ≤ r < y. Then - 1 = 2n = (2y)s2r = 2r (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 = 2n = (-1)h2k (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 3m is the largest power of 3 dividing n. We show that m must be 1. Expand (3 - 1)n + 1 by the binomial theorem, to get (since n is odd):   1 - 1 + n.3 - 1/2 n(n - 1) 32 + ... = 3n - (n - 1)/2 n 32 + ... . Evidently 3n is divisible by 3m+1, but not 3m+2. We show that the remaining terms are all divisible by 3m+2. It follows that 3m+1 is the highest power 3 dividing 2n + 1. But 2n + 1 is divisible by n2 and hence by 32m, so m must be 1.
The general term is (3ma)Cb 3b, for b ≥ 3. The binomial coefficients are integral, so the term is certainly divisible by 3m+2 for b ≥ m+2. We may write the binomial coefficient as (3ma/b) (3m - 1)/1 (3m - 2)/2 (3m - 3)/3 ... (3m - (b-1)) / (b - 1). For b not a multiple of 3, the first term has the form 3m 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 3m, since b > 3, this means that the whole term is divisible by at least 3m+3. Similarly, for b a multiple of 3, the whole term has the same maximum power of 3 dividing it as 3m 3b/b. But b is at least 3, so 3b/b is divisible by at least 9, and hence the whole term is divisible by at least 3m+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 2w = -1 (mod q), and v the smallest positive integer for which 2v = 1 (mod q). v certainly exists and < q since 2q-1 = 1 (mod q). 2n = -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 23 = -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 = {p1, p2, ... } and T= {q1, q2, ... }. Define f(pn) = qn, and f(qn) = 1/pn. We extend this definition to all rationals using f(xy) = f(x) f(y): f(pi1pi2...qj1qj2.../(pk1...qm1...)) = pm1...qi1.../(pj1...qk1...). It is now trivial to verify that f(x f(y)) = f(x)/y.  

Problem B2
Given an initial integer n0 > 1, two players A and B choose integers n1, n2, n3, ... alternately according to the following rules:
Knowing n2k, A chooses any integer n2k+1 such that n2k ≤ n2k+1 ≤ n2k2.
Knowing n2k+1, B chooses any integer n2k+2 such that n2k+1/n2k+2 = pr 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 n0 does
(a)  A have a winning strategy?
(b)  B have a winning strategy?
(c)  Neither player have a winning strategy?
Solution
Answer: if n0 = 2, 3, 4 or 5 then A loses; if n0 ≥ 8, then A wins; if n0 = 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 ∈ [11r181 + 1, 11r+1181] for some r > 0, pick 11r+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 11r+1181, then B must pick 181, 11.181, ... , 11r.181 or 11r+1, all of which are ≤ 11r.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 12, 22, ... , 19902 in some order.
Solution
By Robin Chapman, Dept of Maths, Macquarie University, Australia
In the complex plane we can represent the sides as pn2wn, where pn 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)iajbk, 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)2 (-1)iajbk is zero.
We sum first over i. This gives -9952 x sum of ajbk which is zero, and - 1990 x sum s(j,k) ajbk, where s(j,k) = 1 + 199j + k. So it is sufficient to show that the sum of s(j,k) ajbk 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 bk, which gives zero when summed over k. 




Read more

Solutions are also available in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X. 
[Read 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 A1, A2, ... , A117 in such a way that each Ai contains 17 elements and the sum of the elements in each Ai is the same.
A2.  In an acute-angled triangle ABC, the internal bisector of angle A meets the circumcircle again at A1. Points B1 and C1 are defined similarly. Let A0 be the point of intersection of the line AA1 with the external bisectors of angles B and C. Points B0 and C0 are defined similarly. Prove that the area of the triangle A0B0C0 is twice the area of the hexagon AC1BA1CB1 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 {x1, x2, ... , xm} of the set {1, 2, ... , 2n} where n is a positive integer is said to have property P if |xi - xi+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 A1, A2, ... , A117 in such a way that each Ai contains 17 elements and the sum of the elements in each Ai 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 A1. Points B1 and C1 are defined similarly. Let A0 be the point of intersection of the line AA1 with the external bisectors of angles B and C. Points B0 and C0 are defined similarly. Prove that the area of the triangle A0B0C0 is twice the area of the hexagon AC1BA1CB1 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 AA0, BB0, CC0 (the in-center). BIC = 180 - 1/2 ABC - 1/2 BCA = 180 - 1/2 (180 - CAB) = 90 + 1/2 CAB. Hence CA1B = 180 - CAB [BA1CA is cyclic] = 2(180 - BIC) = 2CA0B. But A1B = A1C, so A1 is the center of the circumcircle of BCA0. But I lies on this circumcircle (IBA0 = ICA0 = 90), and hence A1A0 = A1I.
Hence area IBA1 = area A0BA1 and area ICA1 = area A0CA1. Hence area IBA0C = 2 area IBA1C. Similarly, area ICB0A = 2 area ICB1A and area IAC0B = 2 area IAC1B. Hence area A0B0C0 = 2 area hexagon AB1CA1BC1.
A neat solution for the rest is as follows by Thomas Jäger
Let H be the orthocentre of ABC. Let H1 be the reflection of H in BC, so H1 lies on the circumcircle. So area BCH = area BCH1 <= area BCA1. Adding to the two similar inequalities gives area ABC <= area hexagon - area ABC.
Mazur's solution was as follows
CAB = 180o - CA1B and A1B = A1C, so A1BC = 90o - 1/2 CA1B = 1/2 CAB. Hence the perpendicular from A1 to BC has length 1/2 BC tan(CAB/2) and area CA1B = 1/4 BC2 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 CA1B = r2(y + z)2/(4x). Also area BIC = 1/2 r BC. Similarly for the other triangles, so area ABC = area BIC + area CIA + area AIB = r2(x + y + z). We have to show that area ABC ≤ area CA1B + area AB1C + area BC1A, or (x + y + z) ≤ (y + z)2/(4x) + (z + x)2/(4y) + (x + y)2/(4z).
Putting s = x + y + z, this is equivalent to: 4s ≤ (s - x)2/x + (s - y)2/y + (s - z)2/z, or 9s ≤ s2(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 {A0, B0} we must be able to find at least 3 points P on the perpendicular bisector of A0B0. But these points are collinear, contradicting the assumption in the question.
 
From an anonymous source
Let the points be P1, P2, ... , Pn. Let Ci be a circle center Pi containing at least k points of S. There are at least nk pairs (Ci,Pj), where Pj lies on Ci. 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/2 + 7/8 > (k - 1/2)2/2. Hence √(2n) + 1/2 > k.

By Thomas Jäger
Define Pi and Si as above. Let g(i) be the number of Sa containing Pi, and let f(i, j) be |Si ∩ Sj|. Let h(x) = x(x - 1)/2. We count the number N of pairs i, {a, b}, where point i is in Sa and Sb.
Point i is in g(i) sets Sj, from which we can choose Sa,Sb in h(g(i)) ways. Hence N = ∑ h(g(i)). But f(a, b) points are in Sa and Sb, 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 CA be the circle center A, radius AD, and CB the circle center B, radius BC. The circles touch on AB. Let CP the the circle center P, radius h. CP touches CA and CB and CD. Let t be the common tangent to CA and CB whose two points of contact are on the same side of AB as C and D. Then CP is confined inside the curvilinear triangle whose sides are segments of t, CA and CB. Evidently h attains its maximum value, for given lengths AB, AD, BC, when CP touches t, in which case D must be the point at which t touches CA, and C the point at which it touches CB. Suppose E is the point at which t touches CP.
Angles ADC and BCD are right angles, so CD2 = AB2 - (AD - BC)2 = 4 AD BC. Similarly, DE2 = 4 h AD, and CE2 = 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+2, (N!)2+3, ... , (N!)2+N. (N!)2+r is divisible by r, but ((N!)2+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 pr dividing r, so (N!)2+r is divisible by pr, but is not a power of pr. Hence it is not a prime or a prime power. Taking N = n+1 gives n consecutive numbers as required. 

Problem B3
A permutation {x1, x2, ... , xm} of the set {1, 2, ... , 2n} where n is a positive integer is said to have property P if |xi - xi+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 Ak 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 Ak.
Then |A| = Sumk |Ak| - Sumk<l |Ak∩Al| + Sumk<l<m |Ak∩Al∩Am| - ... . But this is an alternating sequence of monotonically decreasing terms, hence |A| ≥ ∑k |Ak| - Sumk<l |Ak∩Al|.
But |Ak| = 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, |Ak∩Al| = 4 (2n - 2)! So |A| ≥ (2n - 2)! [n.2(2n -1) - n(n - 1)/2 4] = 2n2 (2n - 2)! > (2n)!/2.
Read more




Solutions are also available in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
[Read 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 AB2 + BC2 + CA2.
(ii)  Find the locus of the midpoint of BC.
A2.  Let n be a positive integer and let A1, A2, ... , A2n+1 be subsets of a set B. Suppose that:
(i)  Each Ai has exactly 2n elements,
(ii)  The intersection of every two distinct Ai contains exactly one element, and
(iii)  Every element of B belongs to at least two of the Ai.
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 Ai 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 a2 + b2. Show that (a2 + b2)/(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 AB2 + BC2 + CA2.
(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 AP2 = 4r2 - 4x2. BM2 = R2 - OM2 = R2 - (r2 - x2). That is essentially all we need, because we now have: AB2 + AC2 + BC2 = (AP2 + (BM - x)2) + (AP2 + (BM + x)2) + 4BM2 = 2AP2 + 6BM2 + 2x2 = 2(4r2 - 4x2) + 6(R2 - r2 + x2) + 2x2 = 6R2 + 2r2 , 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 A1, A2, ... , A2n+1 be subsets of a set B. Suppose that:
(i)  Each Ai has exactly 2n elements,
(ii)  The intersection of every two distinct Ai contains exactly one element, and
(iii)  Every element of B belongs to at least two of the Ai.
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 Ai has 0 assigned to exactly n of its elements?
Solution
Answer: n even.
Each of the 2n elements of Ai belongs to at least one other Aj because of (iii). But given another Aj it cannot contain more than one element of Ai because of (ii). There are just 2n other Aj available, so each must contain exactly one element of Ai. 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 Ai and Aj (i,j). Then Ai 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, Ai 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, Ai 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. A2n+2 has the n+1 elements (i, 2n+2) with i <= n+1 and also (2n+2, 2n+4), giving n+2 in all. A2n+3 has the n+1 elements (i, 2n+3) for i ≤ n+1 and also (2n+3, 2n+5), giving n+2 in all. A2n+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 A2n+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 = br+1br...b2b1b0 in binary and n is odd, so that br+1 = b0 = 1, then f(n) = br+1b1b2...brb0. 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 2m < 2n+1 < 2m+1, then f(2n+1) = f(n) + 2m. 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 2m+1 < 4n+1 < 2m+2, then f(4n+1) = 2f(2n+1) - f(n) = 2(f(n) + 2m) - f(n) = f(n) + 2m+1 = f(2n) + 2m+1, so it is true for 4n+1. Similarly, if 4n+3 satisfies, 2m+1 < 4n+3 < 2m+2, then f(4n+3) = 3f(2n+1) - 2f(n) = f(2n+1) + 2(f(n) + 2m) - 2f(n) = f(2n+1) + 2m+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 = br+1br...b2b1b0 with b0 = br+1 = 1. We use induction on r. So assume it is true for smaller values. Say b1 = ... = bs = 0 and bs+1 = 1 (we may have s = 0, so that we have simply b1 = 1). Then n = br+1 ... b1 and f(n) = br+1bs+2bs+3...brbs+1 by induction. So f(n) + 2r+1 = br+10...0br+1bs+2...brbs+1, where there are s zeros. But we may write this as br+1b1...bsbs+1...brbr+1, since b1 = ... = bs = 0, and bs+1 = br+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 xn. Also f(x) ≥ 5/4 for x in (n, xn] and f(x) < 5/4 for x in (xn, 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 x70 in this range and f(x) >= 5/4 for x in (70, x70] and f(x) < 5/4 for x > x70. Thus we have established that f(x) ≥ 5/4 for x in any of the disjoint intervals (1, x1], (2, x2], ... , (70, x70] and f(x) < 5/4 elsewhere.
The total length of these intervals is (x1 - 1) + ... + (x70 - 70) = (x1 + ... + x70) - (1 + ... + 70). The xi 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 x69 divided by the coefficient of x70. The coefficient of x70 is simply k, and the coefficient of x69 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 = 45o 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 = AD2/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 a2 + b2. Show that (a2 + b2)/(ab + 1) is a perfect square.
Solution
A little experimentation reveals the following solutions: a, a3 giving a2; a3, a5 - a giving a2; and the recursive a1 = 2, b1 = 8, an+1 = bn, bn+1 = 4bn - an giving 4. The latter may lead us to: if a2 + b2 = k(ab + 1), then take A = b, B = kb - a, and then A2 + B2 = 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 a2 + b2 = k(ab + 1). If a = b, then 2a2 = k(a2 + 1). So a2 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 a3 > b. For (b/a - 1/a)(ab + 1) = b2 + b/a - b - 1/a < b2 < a2 + b2. So k > b/a - 1/a. But if a3 < b, then b/a (ab + 1) > b2 + a2, 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 a2 + b2 = k(ab + 1), and B and k are positive integers. Also a < b implies a2 + b2 < ab + b2 < ab + b2 + 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 A2 + B2 = k(AB + 1), so k = B2. 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 a2 + b2 = k(ab + 1), so a, b, and k are all positive integers. Now fixing k take positive integers A, B such that A2 + B2 = 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 = B2 - k. The second equation implies that C = B2/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 = B2 + (B-1)k + 1 > 0, so C > -1. C = kB - A is an integer, so C = 0. Hence k = B2

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

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





[Read More...]


28th International Mathematical Olympiad 1987 Problems & Solutions



A1.  Let pn(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 pn(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 x1, x2, ... , xn be real numbers satisfying x12 + x22 + ... + xn2 = 1. Prove that for every integer k ≥ 2 there are integers a1, a2, ... , an, not all zero, such that |ai| ≤ k - 1 for all i, and |a1x1 + a2x2 + ... + anxn| ≤ (k - 1)√n/(kn - 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 k2 + k + n is prime for all integers k such that 0 ≤ k ≤ √(n/3), then k2 + k + n is prime for all integers k such that 0 ≤ k ≤ n-2. 

Solutions

Problem A1
1.  Let pn(k) be the number of permutations of the set {1, 2, 3, ... , n} which have exactly k fixed points. Prove ∑0n (k pn(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/n!). This follows immediately from the law of inclusion and exclusion: let Ni be the number which fix i, Nij the number which fix i and j, and so on. Then N0, the number with no fixed points, is n! - all Ni + all Nij - ... + (-1)nN1...n. But Ni = (n-1)!, Nij = (n-2)! and so on. So N0 = n! ( 1 - 1/1! + ... + (-1)r(n-r)!/(r! (n-r)!) + ... + (-1)n/n!) = n! (1/0! - 1/1! + ... + (-1)n/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/n! + 1/1! (-1)n-1/(n-1)! + ... + 1/n! 1/0! = 1/n! (1 - 1)n = 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 x1, x2, ... , xn be real numbers satisfying x12 + x22 + ... + xn2 = 1. Prove that for every integer k ≥ 2 there are integers a1, a2, ... , an, not all zero, such that |ai| ≤ k - 1 for all i, and |a1x1 + a2x2 + ... + anxn| ≤ (k - 1)√n/(kn - 1).
Solution
This is an application of the pigeon-hole principle.
Assume first that all xi are non-negative. Observe that the sum of the xi is at most √n. [This is a well-known variant, (∑1≤i≤n xi)2 ≤ n ∑1≤i≤n xi2, of the AM-GM result. See, for example, Arthur Engel, Problem Solving Strategies, Springer 1998, p163, ISBN 0387982191].
Consider the kn possible values of ∑1≤i≤n bixi, where each bi is an integer in the range [0,k-1]. Each value must lie in the interval [0, k-1 √n]. Divide this into kn-1 equal subintervals. Two values must lie in the same subinterval. Take their difference. Its coefficients are the required ai. Finally, if any xi are negative, solve for the absolute values and then flip signs in the ai.
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 r1 and r2 respectively. Then the same induction shows that all sufficiently large s = r1 (mod k) have f(s) = r2 (mod k), and that all sufficiently large s = r2 (mod k) have f(s) = r1 (mod k). Hence if m has a different residue r mod k, then f(m) cannot have residue r1 or r2. For if f(m) had residue r1, then the same argument would show that all sufficiently large numbers with residue r1 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 xn be the point with coordinates (n, n2) 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. |xn - xm| is the hypoteneuse of a triangle with sides n - m and n2 - m2 = (n - m)(n + m). So |xn - xm| = (n - m)√(1 + (n+m)2). Now (n + m)2 < (n + m)2 + 1 < (n + m + 1)2 = (n + m)2 + 1 + 2(n + m), so (n + m)2 + 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 p2a+1 divides N' but p2a+2 does not divide N' for some a ≥ 0. Define N = N'/p2a. Then √N = (√N')/pa, which is also rational. So we have a prime p such that p divides N, but p2 does not divide N. Take √N = r/s with r and s relatively prime. So s2N = r2. Now p must divide r, hence p2 divides r2 and so p divides s2. 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, a2), C the point (c, a2), and D the point (c, b2). Area xaxbxc = area xaxcC - area xaxbB - area xbxcD - area xbDCB = (c - a)(c2 - a2)/2 - (b - a)(b2 - a2)/2 - (c - b)(c2 - b2)/2 - (c - b)(b2 - a2) which is rational. 

Problem B3
Let n be an integer greater than or equal to 2. Prove that if k2 + k + n is prime for all integers k such that 0 ≤ k ≤ √(n/3), then k2 + 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 2jc ≤ b. Then 2j+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)2 > m, then we can conclude that m must be prime, since if it were composite it would have a factor ≤ √m.
Let n = 3r2 + 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)2 > N, and that N is relatively prime to all of r + s + 1, r + s + 2, ... , 2r + 2s. We have (2r + 2s + 1)2 = 4r2 + 8rs + 4s2 + 4r + 4s + 1. Since r, s ≥ 1, we have 4s + 1 > s + 2, 4s2 > s2, and 6rs > 3r. Hence (2r + 2s + 1)2 > 4r2 + 2rs + s2 + 7r + s + 2 = 3r2 + 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'2 = 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

Creative Problem Solving in School Mathematics, Revised and Expanded 2nd EditionSolutions are also available in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.




[Read 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 P0 in the plane of the triangle A1A2A3. Define As = As-3 for all s >= 4. Construct a set of points P1, P2, P3, ... such that Pk+1 is the image of Pk under a rotation center Ak+1 through an angle 120o clockwise for k = 0, 1, 2, ... . Prove that if P1986 = P0, then the triangle A1A2A3 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 = b2. 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 P0 in the plane of the triangle A1A2A3. Define As = As-3 for all s ≥ 4. Construct a set of points P1, P2, P3, ... such that Pk+1 is the image of Pk under a rotation center Ak+1 through 120o clockwise for k = 0, 1, 2, ... . Prove that if P1986 = P0, then the triangle A1A2A3 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 P1986 (which is the result of 662 such operations, since 1986 = 3 x 662) can only be P0 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 A1, radius A1A2 and take P on the circle so that a 120o clockwise rotation about A1 brings P to A2. Take a circle center A3, radius A3A2 and take Q on the circle so that a 120o clockwise rotation about A3 takes A2 to Q. Then successive 120o clockwise rotations about A1, A2, A3 take P to Q. So if these three are equivalent to the identity we must have P = Q. Hence ∠A1A2A3 = ∠A1A2P + ∠A3A2P = 30o + 30o = 60o. Also A2P = 2A1A2cos 30o and = 2A2A3cos 30o. Hence A1A2 = A2A3. So A1A2A2 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 A1 to be the origin and A2 to be (a, b). Let A3 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)2 + (b - d)2 + (c - e)2 + (d - a)2 +(e - b)2, 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. x2 + y2 = (1/sin2π/n + 1/cos2π/n) cos2(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 y0 we have f(y0) > 2/(2 - y0), then we can find y1 > y0 (and y1 < 2) so that f(y0) = 2/(2 - y1). Now let x1 = 2 - y1. Then f(x1f(y0)) = f(2) = 0, so f(x1 + y0) = 0. But x1 + y0 < 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

 
Primary Grade Challenge Math 
Solutions are also available in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X. 
[Read More...]


Fun Math Games for Kids

 
Return to top of page Copyright © 2010 Copyright 2010 (C) CoolMath4Kids - Cool Math 4 Kids - Cool Math Games 4 Kids - Coolmath4kids Bloxorz - Coolmath-4kids - Math games, Fun Math Lessons, Puzzles and Brain Benders, Flash Cards for Addition, Subtration, Multiplication, Fraction, Division - Cool Math 4 Kids - Math Games, Math Puzzles, Math Lessons - Cool Math 4 Kids Math Lessones - 4KidsMathGames - CoolMath Games4Kids coolmath4kids.info. All right reseved.