2. A chooses a positive integer X ≤ 100. B has to find it. B is allowed to ask 7 questions of the form "What is the greatest common divisor of X + m and n?" for positive integers m, n < 100. Show that he can find X.
3. O is the circumcenter of the obtuse-angled triangle ABC. K is the circumcenter of AOC. The lines AB, BC meet the circumcircle of AOC again at M, N respectively. L is the reflection of K in the line MN. Show that the lines BL and AC are perpendicular.
4. Some pairs of towns are connected by a road. At least 3 roads leave each town. Show that there is a cycle containing a number of towns which is not a multiple of 3.
5. Find [1/3] + [2/3] + [22/3] + [23/3] + ... + [21000/3].
6. We have -1 < x1 < x2 < ... < xn < 1 and y1 < y2 < ... < yn such that x1 + x2 + ... + xn = x113 + x213 + ... + xn13. Show that x113y1 + x213y2 + ... + xn13yn < x1y1 + ... + xnyn.
7. ABC is acute-angled and is not isosceles. The bisector of the acute angle between the altitudes from A and C meets AB at P and BC at Q. The angle bisector of B meets the line joining HN at R, where H is the orthocenter and N is the midpoint of AC. Show that BPRQ is cyclic. 
8. We wish to place 5 stones with distinct weights in increasing order of weight. The stones are indistinguisable (apart from their weights). Nine questions of the form "Is it true that A < B < C?" are allowed (and get a yes/no answer). Is that sufficient?
9. R is the reals. Find all functions f: R → R which satisfy f(x+y) + f(y+z) + f(z+x) ≥ 3f(x+2y+3z) for all x, y, z.
10. Show that it is possible to partition the positive integers into 100 non-empty sets so that if a + 99b = c for integers a, b, c, then a, b, c are not all in different sets.
11. ABCDE is a convex pentagon whose vertices are all lattice points. A'B'C'D'E' is the pentagon formed by the diagonals. Show that it must have a lattice point on its boundary or inside it.
12. a1, a2, ... , an are non-negative integers not all zero. Put m1 = a1, m2 = max(a2, (a1+a2)/2), m3 = max(a3, (a2+a3)/2 + (a1+a2+a3)/3), m4 = max(a4, (a3+a4)/2, (a2+a3+a4)/3, (a1+a2+a3+a4)/4), ... , mn = max(an, (an-1+an)/2, (an-2+an-1+an)/3, ... , (a1+a2+...+an)/n). Show that for any α > 0 the number of mi > α is < (a1+a2+...+an)/α.
13. The sequence a1, a2, a3, ... is constructed as follows. a1 = 1. an+1 = an - 2 if an - 2 is a positive integer which has not yet appeared in the sequence, and an + 3 otherwise. Show that if an is a square, then an > an-1.
14. Some cells of a 2n x 2n board contain a white token or a black token. All black tokens which have a white token in the same column are removed. Then all white tokens which have one of the remaining black tokens in the same row are removed. Show that we cannot end up with more than n2 black tokens and more than n2 white tokens.
15. ABC is a triangle. E is a point on the median from C. A circle through E touches AB at A and meets AC again at M. Another circle through E touches AB at B and meets BC again at N. Show that the circumcircle of CMN touches the two circles. 
16. 100 positive integers are arranged around a circle. The greatest common divisor of the numbers is 1. An allowed operation is to add to a number the greatest common divisor of its two neighbors. Show that by a sequence of such operations we can get 100 numbers, every two of which are relatively prime.
17. S is a finite set of numbers such that given any three there are two whose sum is in S. What is the largest number of elements that S can have?
18. A perfect number is equal to the sum of all its positive divisors other than itself. Show that if a perfect number > 6 is divisible by 3, then it is divisible by 9. Show that a perfect number > 28 divisible by 7 must be divisible by 49.
19. A larger circle contains a smaller circle and touches it at N. Chords BA, BC of the larger circle touch the smaller circle at K, M respectively. The midpoints of the arcs BC, BA (not containing N) are P, Q respectively. The circumcircles of BPM, BQK meet again at B'. Show that BPB'Q is a parallelogram. 
20. Several thin unit cardboard squares are put on a rectangular table with sides parallel to the sides of the table. The squares may overlap. Each square is colored with one of k colors. Given any k squares of different colors, we can find two that overlap. Show that for one of the colors we can nail all the squares of that color to the table with 2k-2 nails.
21. Show that sinn2x + (sinnx - cosnx)2 ≤ 1.
22. ABCD has an inscribed circle center O. The lines AB and CD meet at X. The incircle of XAD touches AD at L. The excircle of XBC opposite X touches BC at K. X, K, L are collinear. Show that O lies on the line joining the midpoints of AD and BC.
23. Each cell of a 100 x 100 board is painted with one of four colors, so that each row and each column contains exactly 25 cells of each color. Show that there are two rows and two columns whose four intersections are all different colors.
Solutions
Problem 1
The equations x2 + ax + 1 = 0 and x2 + bx + c = 0 have a common real root, and the equations x2 + x + a = 0 and x2 + cx + b = 0 have a common real root. Find a + b + c.
Answer
-3
Solution
The common root of x2 + ax + 1 = 0 and x2 + bx + c = 0 must also satisfy (a-b)x + (1-c) = 0, so it must be (c-1)/(a-b). Note that the other root of x2 + ax + 1 = 0 must be (a-b)/(c-1), since the product of the roots is 1. Similarly the common root of x2 + x + a = 0 and x2 + cx + b = 0 must satisfy (c-1)x + (b-a) = 0, so it is x = (a-b)/(c-1). Hence x2 + x + a = 0 and x2 + ax + 1 = 0 have a common root. Hence it satisfies (a-1)x + (1-a) = 0. Now we cannot have a = 1, for then x2 + ax + 1 has no real roots. Hence the common root must be 1. Hence both roots of x2 + ax + 1 = 0 are 1 and so a = -2.
So x2 + bx + c = 0 has one root 1. Then its other root must be c/1 = c. Hence -b = 1 + c, or b + c = -1. Hence a + b + c = -3.
Problem 2
A chooses a positive integer X ≤ 100. B has to find it. B is allowed to ask 7 questions of the form "What is the greatest common divisor of X + m and n?" for positive integers m, n < 100. Show that he can find X.
Solution
The idea is that X can be regarded as having 7 binary digits b6b5...b0 and we can find each digit with one question. If there was no restriction on the numbers m, n, then the procedure would be trivial: having determined the last k binary digits which give a number m, we then ask for gcd(X - m, 2k+1). If it is 2k+1, then bk = 0, if it is 2k, then bk = 1. Given the restrictions, we have to use a slight variant on this procedure.
For b0 we can ask for gcd(X+1,2). If it is 1, then b0 = 0. If it is 2, then b0 = 1. Now if we have found b0, b1, ... bk-1 with k ≤ 5, we want to subtract off b = bk-1...b1b0. So we add m = 2k+1 - b. Then the last k+1 digits of X + 2k+1 - b are bk0...0, so gcd(X+m,2k+1) is 2k+1 if bk = 0, or 2k if bk = 1. That gives us b0, b1, ... , b5 in the first 6 questions. If b = b5b4...b0, we know that X = b or b+64. These are different mod 3. So we take m = 1, 2 or 3 to give b + m a multiple of 3 and and take n = 3. Then gcd(X+m,n) distinguishes b and b+64.
Problem 3
O is the circumcenter of the triangle ABC. K is the circumcenter of AOC. The lines AB, BC meet the circumcircle of AOC again at M, N respectively. L is the reflection of K in the line MN. Show that the lines BL and AC are perpendicular.
Solution
We start by showing that ∠MCB = ∠MBC. The argument is slightly different in the three different cases. In the first we have: ∠MCB = ∠MCO + ∠OCB = ∠MAO + ∠OBC = ∠MBO + ∠OBC = ∠MBC. In the second case we have ∠MCB = ∠OCB - ∠OCM = ∠OBC - ∠OAB = ∠OBC - ∠OBA = ∠MBC. In the third case we have ∠MCB = ∠MCO - ∠OCB = (180o - ∠OAB) - ∠OBC = 180o - ∠OBA - ∠OBC = ∠MBC.
Next we show that L is the circumcenter of MNB. In all cases we have ∠MLN = ∠MKN. In the first case, ∠MKN = 2∠MCN = 2∠MBN. But LM = LN (because KM = KN), so L is the circumcenter. In the second case, ∠MKN = 2∠MAN = 2∠MCB = 2∠MBN and then as before. In the third case, ∠MKN = 2∠MCN = 360o - 2∠MBN. So 360o - ∠MLN = 2∠MBN, so L is the circumcenter.
Finally, we have ∠MLB = 2∠MNB = 2∠A. Hence ∠MLB = 90o-∠A.
Problem 4
Some pairs of towns are connected by a road. At least 3 roads leave each town. Show that there is a cycle containing a number of towns which is not a multiple of 3.
Solution
Take any town T1. Now having found T1, T2, ... , Ti take Ti+1 distinct from T1, T2, ... , Ti such that there is a road from Ti to Ti+1. Since there are only finitely many towns, this process must terminate at some Tn. Since Tn has at least 3 roads and the chain cannot be extended there must be at least two towns Ta and Tb with roads to Tn in the chain (apart from Tn-1). wlog a < b. Now consider the cycles:
Ta, Ta+1, ... , Tn length n-a+1
Tb, Tb+1, ... , Tn length n-b+1
Ta, Ta+1, ... , Tb, Tn length b-a+2
Now (n-a+1) - (n-b+1) - (b-a+2) = -2, which is not divisible by 3, so at least one of the cycles must have length not divisible by 3.
Ta, Ta+1, ... , Tn length n-a+1
Tb, Tb+1, ... , Tn length n-b+1
Ta, Ta+1, ... , Tb, Tn length b-a+2
Now (n-a+1) - (n-b+1) - (b-a+2) = -2, which is not divisible by 3, so at least one of the cycles must have length not divisible by 3.
Problem 5
Find [1/3] + [2/3] + [22/3] + [23/3] + ... + [21000/3].
Answer
(2/3)(21000-1)-500
Solution
Let f(n) = [2n/3]. Note that f(0) = f(1) = 0. We have 2n = (3-1)n = (-1)n mod 3, so if n is even, then 2n/3 = f(n) + 1/3 and hence 2n+1/3 = 2f(n) + 2/3. So f(n+1) = 2f(n). Similarly, if n is odd, f(n+1) = 2f(n) + 1. Thus f(2n) = 2f(2n-1)+1 = 4f(2n-2)+1. Put un = f(2n) + 1/3, then un = 4un-1. But u1 = 4/3, so un = 4n/3.
Hence u1 + u2 + ... + un = (4/3)(1 + ... + 4n-1) = (4/9)(4n-1). So f(2) + f(4) + ... + f(2n) = (4/9)(4n-1) - n/3. We have f(2n+1) = f(2n), so f(3) + f(5) + ... + f(2n-1) = (8/9)(4n-1-1) - (2/3)(n-1). Hence f(2) + f(3) + ... + f(2n) = (2/3)(4n-1) - n.
Thanks to Suat Namli
Problem 6
We have -1 < x1 < x2 < ... < xn < 1 and y1 < y2 < ... < yn such that x1 + x2 + ... + xn = x113 + x213 + ... + xn13. Show that x113y1 + x213y2 + ... + xn13yn < x1y1 + ... + xnyn.
Solution
Note that if xi > 0, then xi13 < xi and if xi < 0, then xi13 > xi. So not all the xi can be non-negative and not all can be non-positive. Hence x1 < 0 < xn.
Put zi = xi - xi13. Then z1 < z2 < z3 < ... < zn. So if zi + zi+1 + ... + zn ≤ 0 for i > 1, then zi must be negative and hence all of z1, z2, ... , zi-1 must be negative and hence z1 + z2 + ... + zn < 0. Contradiction. hence zi + zi+1 + ... + zn > 0 for i > 1.
Now we have ∑ xiyi - ∑ xiyi13 = ∑ yizi = y1(z1 + z2 + ... + zn) + (y2 - y1)(z2 + ... + zn) + (y3 - y2)(z3 + ... + zn) + ... + (yn - yn-1)zn > 0.
Problem 8
We wish to place 5 stones with distinct weights in increasing order of weight. The stones are indistinguisable (apart from their weights). Nine questions of the form "Is it true that A < B < C?" are allowed (and get a yes/no answer). Is that sufficient?
Answer
no
Solution
There are 120 possible orders for the weights. 20 will fit any given A < B < C. So a "No" answer can exclude at most 20 possible orders. Thus if the answer to the first 5 questions is "No", then there are still 20 possible orders after them. Now if a "No" to the next question leaves k possibilities, then a "Yes" will leave at least 20-k, so one answer must leave at least 10 possibilities. Similarly, one answer to the 7th question must leave at least 5 possibilities, one answer to the 8th question must leave at least 3 possibilities, and one answer to the 9th question must leave at least 2 possibilities.
Problem 9
R is the reals. Find all functions f: R → R which satisfy f(x+y) + f(y+z) + f(z+x) ≥ 3f(x+2y+3z) for all x, y, z.
Answer
f constant.
Solution
Put x = a, y = z = 0, then 2f(a) + f(0) ≥ 3f(a), so f(0) ≥ f(a). Put x = a/2, y = a/2, z = -a/2. Then f(a) + f(0) + f(0) ≥ 3f(0), so f(a) ≥ f(0). Hence f(a) = f(0) for all a. But any constant function obviously satisfies the given relation.
Problem 10
Show that it is possible to partition the positive integers into 100 non-empty sets so that if a + 99b = c for integers a, b, c, then a, b, c are not all in different sets.
Solution
Let t(n) be the largest k such that 2k divides n. Put Ai = {n : t(n) = i mod 100} for i = 0, 1, 2, ... , 99.
Suppose a + 99b = c and t(a) < t(b). Then 99b is divisible by a higher power of 2, than a. Hence t(c) = t(a). Similarly if t(a) > t(b), then t(c) = t(b). So at least two of t(a), t(b), t(c) must be the same.
Problem 13
The sequence a1, a2, a3, ... is constructed as follows. a1 = 1. an+1 = an - 2 if an - 2 is a positive integer which has not yet appeared in the sequence, and an + 3 otherwise. Show that if an is a square, then an > an-1.
Solution
We show by induction that a5n+1 = 5n+1, a5n+2 = 5n+4, a5n+3 = 5n+2, a5n+4 = 5n+5, a5n+5 = 5n+3. It is easy to check that a1 = 1, a2 = 4, a3 = 2, a4 = 5, a5 = 3, which establishes n = 1.
So now suppose the result is true for n and smaller. Then in particular a5n+5 - 2 = 5n+1 is already in the sequence. Hence a5n+6 = a5n+5 + 3 = 5(n+1)+1. Similarly a5n+6 - 2 = 5n+4 is already in the sequence, so a5n+7 = a5n+6 + 3 = 5(n+1)+4. But 5(n+1)+2 = a5n+7 - 2 is not yet in the sequence, so a5n+8 = 5(n+1)+2. 5(n+1) is already in the sequence, so a5n+9 = a5n+8 + 3 = 5(n+1)+5. 5(n+1)+3 is not yet in the sequence, so a5n+10 = a5n+9 - 2 = 5(n+1)+3. So we have established the result for n+1 and hence for all n.
Now any square must be 0, 1 or 4 mod 5, so it must be a5n+4, a5n+1 or a5n+2, which all satisfy the required condition.
Problem 14
Some cells of a 2n x 2n board contain a white token or a black token. All black tokens which have a white token in the same column are removed. Then all white tokens which have one of the remaining black tokens in the same row are removed. Show that we cannot end up with more than n2 black tokens and more than n2 white tokens.
Solution
After the first move every column contains nothing but black tokens (and empty cells) or nothing but white tokens (and empty cells). After the second move the same applies to the rows. So let B be the number of rows containing a black token, and W be the number of rows with no black token. Similarly, let b be the number of columns containing a black token, and w the number of columns with no black token. Then B+W+b+w = 4n, so BWbw ≤ n4 (by AM/GM). Hence either Bb ≤ n2 or Ww ≤ n2. But the number of black tokens ≤ Bb (because only rows contain black tokens, and in each of those columns there are at most b black tokens). Similarly, the no. of white tokens is ≤ Ww.
Problem 17
S is a finite set of numbers such that given any three there are two whose sum is in S. What is the largest number of elements that S can have?
Answer
7
Solution
Consider S = {-3, -2, -1, 0, 1, 2, 3}. Suppose {a, b, c} ⊆ S. If a = 0, then a+b ∈ S. If a and b have opposite sign, then |a+b| < max(|a|,|b|), so a+b ∈ S. The only remaining possibilities are {1,2,3} and {-3,-2,-1} and 1+2, -1-2 ∈ S. So there is a set with 7 elements having the required property.
Now suppose S has 4 positive elements. Take the largest four: a < b < c < d. Consider {b,c,d}. Clearly c+d, b+d ∉ S, so b+c ∈ S and hence b+c = d. But the same argument shows that a+c = d, so a = b. Contradiction. Hence S has at most 3 positive elements. Similarly, it has at most 3 negative elements, and hence at most 7 elements in all.
Problem 18
A perfect number is equal to the sum of all its positive divisors other than itself. Show that if a perfect number > 6 is divisible by 3, then it is divisible by 9. Show that a perfect number > 28 divisible by 7 must be divisible by 49.
Solution
Suppose n is perfect and divisible by 3 but not 9. Put n = 3m. Write the sum of the positive divisors of k as s(k). Then 6m = s(n) = s(3m) = s(3)s(m) = 4s(m), so s(m) = 3m/2. Hence, in particular m is even. So it certainly has divisors 1, m, m/2 (which are all distinct for n > 6, but not for n = 6, when m/2 = 1) with sum > 3m/2. Contradiction.
Similarly, if n is divisible by 7 but not 49, but n = 7k. Then 14k = s(n) = s(7k) = s(7)s(k) = 8s(k), so s(k) = 7/4 k. Hence k must be divisible by 4, so it certainly has factors 1, k, k/2, k/4 (which are all distinct for n > 28, but not for n = 28, when k/4 = 1) with sum 7k/4 + 1. Contradiction.
Thanks to Stefanos Aretakis
Problem 21
Show that sinn2x + (sinnx - cosnx)2 ≤ 1.
Solution
Put s = sin x, c = cos x, so s2 + c2 = 1. Then lhs = 2ns2nc2n + (sn - cn)2 = (2n-2)sncn + s2n + c2n and rhs = 1 = (s2 + c2)n = s2n + c2n + ∑1n-1 nCi s2n-2ic2i. So we have to show that (2n-2)sncn ≤ ∑1n-1 nCi s2n-2ic2i. But that is immediate from AM/GM applied to the 2n-2 terms shck. (Note that there are the same number of terms s2n-2ic2i and s2ic2n-2i and the product of each pair is s2nc2n. Hence the geometric mean is sncn.)
Labels:
Russian Mathematical Olympiad
Previous Article
