1. The digits of n strictly increase from left to right. Find the sum of the digits of 9n.
2. Each edge of a finite connected graph is colored with one of N colors in such a way that there is just one edge of each color at each point. One edge of each color but one is deleted. Show that the graph remains connected.
3. ABC is a triangle. A' is the midpoint of the arc BC not containing A, and C' is the midpoint of the arc AB not containing C. S is the circle center A' touching BC and S' is the circle center C' touching AB. Show that the incenter of ABC lies on a common external tangent to S and S'.
4. The numbers from 1 to a million are colored black or white. A move consists of choosing a number and changing the color of the number and every other number which is not coprime to it. If the numbers are initially all black, can they all be changed to white by a series of moves?
5. An equilateral triangle side n is divided into n2 equilateral triangles of side 1 by lines parallel to its sides, thus giving a network of nodes connected by line segments of length 1. What is the maximum number of segments that can be chosen so that no three chosen segments form a triangle?
6. Let {x} denote the fractional part of x. Show that {√1} + {√2} + {√3} + ... + {√(n2)} ≤ (n2 - 1)/2.
7. ABC is a triangle. A circle through A and B meets BC again at D, and a circle through B and C meets AB again at E, so that A, E, D, C lie on a circle center O. The two circles meet at B and F. Show that ∠BFO = 90 deg.
8. A graph has 2000 points and every two points are joined by an edge. Two people play a game. The first player always removes one edge. The second player removes one or three edges. The player who first removes the last edge from a point wins. Does the first or second player have a winning strategy?
9. There are three empty bowls X, Y and Z on a table. Three players A, B and C take turns playing a game. A places a piece into bowl Y or Z, B places a piece into bowl Z or X, and C places a piece into bowl X or Y. The first player to place the 1999th piece into a bowl loses. Show that irrespective of who plays first and second (thereafter the order of play is determined) A and B can always conspire to make C lose.
10. The sequence a1, a2, a3, ... of positive integers is determined by its first two members and the rule an+2 = (an+1 + an)/gcd(an, an+1). For which values of a1 and a2 is it bounded?
11. The incircle of the triangle ABC touches the sides BC, CA, AB at D, E, F respectively. Each pair from the incircles of AEF, DBF, DEC has two common external tangents, one of which is a side of the triangle ABC. Show that the other three tangents are concurrent.
12. A piece is placed in each unit square of an n x n square on an infinite board of unit squares. A move consists of finding two adjacent pieces (in squares which have a common side) so that one of the pieces can jump over the other onto an empty square. The piece jumped over is removed. Moves are made until no further moves are possible. Show that at least n2/3 moves are made.
13. A number n has sum of digits 100, whilst 44n has sum of digits 800. Find the sum of the digits of 3n.
14. The positive reals x, y satisfy x2 + y3 ≥ x3 + y4. Show that x3 + y3 ≤ 2.
15. A graph of 12 points is such that every 9 points contain a complete subgraph of 5 points. Show that the graph has a complete subgraph of 6 points. [A complete graph has all possible edges.]
16. Do there exist 19 distinct positive integers whose sum is 1999 and each of which has the same digit sum? 
17. The function f assigns an integer to each rational. Show that there are two distinct rationals r and s, such that f(r) + f(s) ≤ 2 f(r/2 + s/2).
18. A quadrilateral has an inscribed circle C. For each vertex, the incircle is drawn for the triangle formed by the vertex and the two points at which C touches the adjacent sides. Each pair of adjacent incircles has two common external tangents, one a side of the quadrilateral. Show that the other four form a rhombus.
19. Four positive integers have the property that the square of the sum of any two is divisible by the product of the other two. Show that at least three of the integers are equal.
20. Three convex polygons are drawn in the plane. We say that one of the polygons, P, can be separated from the other two if there is a line which meets none of the polygons such that the other two polygons are on the opposite side of the line to P. Show that there is a line which intersects all three polygons iff one of the polygons cannot be separated from the other two.
21. Let A be a vertex of a tetrahedron and let p be the tangent plane at A to the circumsphere of the tetrahedron. Let L, L', L" be the lines in which p intersects the three sides of the tetrahedron through A. Show that the three lines form six angles of 60o iff the product of each pair of opposite sides of the tetrahedron is equal.
Solutions
Problem 1
The digits of n strictly increase from left to right. Find the sum of the digits of 9n.
Answer
9
Solution
Suppose the digits of n are a1a2...ak. Then the digits of 10n are a1a2...ak0. Now subtract n. The units digit is 10-ak and we have carried one from the tens place. But because ai > ai-1, no further carries are needed and the digits of 9n are a1 (a2-a1) (a3-a2) ... (ak-ak-1-1) (10-ak). Thus the sum of the digits is 9.
Problem 2
Each edge of a finite connected graph is colored with one of N colors in such a way that there is just one edge of each color at each point. One edge of each color but one is deleted. Show that the graph remains connected.
Solution
Induction on N. For N=2, the graph must be a cycle with edges of alternating color, so removing one edge will not disconnect it. Now assume the result is true for N.
Take a graph colored with N+1 colors such that there is just one edge of each color at each point. Remove all the edges of one color X. If the graph remains connected, then it still has an edge of each color at each point, so by induction if we remove an edge of each color but one, then it remains connected. Obviously, if we now put back all but one of the X-colored edges, then it remains connected. So suppose removing all the edges of color X disconnects the graph, giving components C1, C2, ... , Cr. By induction removing an edge of each color but one does not disconnect any of the components. Now each component must have an even number of points (because before removing the edges, if there are k points, then there are k/2 edges of any given color). Hence if we now put back the X-colored edges, then each component has an even number of X-colored edges to the other components. So if we regard the components as points, then every point of the resulting graph has even degree. But that means that every edge must be part of a cycle, so removing a single edge cannot disconnect the graph. Hence removing a single X-colored edge must leave all the components connected together and hence leave the graph connected.
Thanks to Vikram Nayak
Problem 5
An equilateral triangle side n is divided into n2 equilateral triangles of side 1 by lines parallel to its sides, thus giving a network of nodes connected by line segments of length 1. What is the maximum number of segments that can be chosen so that no three chosen segments form a triangle?
Answer
n(n+1)
Solution
Every segment belongs to just one of the n(n+1)/2 triangles with base horizontal. We can choose at most 2 sides of each of these triangles, or n(n+1) in all. If we choose all the segments that are not horizontal, then we choose n(n+1) segments. Since every triangle has one horizontal segment, no three chosen segments form a triangle.
Problem 6
Let {x} denote the fractional part of x. Show that {√1} + {√2} + {√3} + ... + {√(n2)} ≤ (n2 - 1)/2.
Solution
For i = 1, 2, ... , 2n we have {√(n2+i) } = √(n2+i) - n < (n+i/2n) - n = i/2n. So {√(n2+1) } + {√(n2+2) } + ... + {√(n2+2n+1) } = {√(n2+1) } + {√(n2+2) } + ... + {√(n2+2n) } < (1 + 2 + ... + 2n)/2n = (2n+1)/2. Hence {√1} + {√2} + {√3} + ... + {√(n2)} ≤ 3/2 + 5/2 + ... + (2n-1)/2 = (n-1)(2n+2)/2.
Problem 9
There are three empty bowls X, Y and Z on a table. Three players A, B and C take turns playing a game. A places a piece into bowl Y or Z, B places a piece into bowl Z or X, and C places a piece into bowl X or Y. The first player to place the 1999th piece into a bowl loses. Show that irrespective of who plays first and second (thereafter the order of play is determined) A and B can always conspire to make C lose.
Solution
A always plays into bowl X, and B always plays into bowl Y (if they can). For the first 999 moves each, A, B and C will certainly play into X and Y. If C can still play, then at least one of A and B can still play into X and Y. So for the next 500 moves C and at least one of A, B will play into X and Y. During that time at most 500 pieces go into Z, so A and B are still free to play into Z. After 999 + 500 moves there are at least 3·999 + 2·500 = 3997 pieces in X and Y. After the next piece is played into X and Y, they are both full and C cannot play. But both A and B can still play into Z. If both of A and B play into X/Y beyond the 999th move, then C loses quicker.
Problem 10
The sequence a1, a2, a3, ... of positive integers is determined by its first two members and the rule an+2 = (an+1 + an)/gcd(an, an+1). For which values of a1 and a2 is it bounded?
Answer
a1 = a2 = 2
Solution
Put dn = gcd(an, an+1). Note that dn+1 divides an+1 and an+1 and hence also dnan+2 - an+1 = an. So it also divides dn. Hence, in particular, dn ≥ dn+1. Since all dn are positive integers, we must have dn = d for all n ≥ some N.
If d = 1, then an+2 = an+1 + an > an+1 for any n > N. So an cannot be bounded.
If d ≥ 3, then an+2 < (an+1 + an)/2 for all n > N. Hence an+2 < max(an+1, an). Now an+3 < max(an+2, an+1) ≤ max(an+1, an). Hence max(an+3, an+2) < max(an+1, an). So we get an infinite strictly decreasing sequence of positive integers. Contradiction.
So we must have d = 2. Hence an+2 = (an+1 + an)/2 for all n > N. Hence an+2 - an+1 = (an - an+1)/2. So if aN ≠ aN+1, then for sufficiently large n we get an non-integral. Contradiction. So aN = aN+1. But gcd(aN,aN+1) = 2, so aN = aN+1 = 2. So 2 = (2 + aN-1)/gcd(2,aN-1). If gcd(2,aN-1) = 1, then aN-1 = 0. Contradiction. So gcd(2,aN-1) = 2. Hence aN-1 = 2 gcd(2,aN-1) - 2 = 2. Now by a trivial induction all terms are 2. In particular a1 and a2 are 2.
Problem 13
A number n has sum of digits 100, whilst 44n has sum of digits 800. Find the sum of the digits of 3n.
Answer
300
Solution
Suppose n has digits a1a2...ak and digit sum s = ∑ ai. If we temporarily allow digits larger than 9, then 4n = (4a1)(4a2)...(4ak). Each carry of one reduces the digit sum by 9, so after making all necessary carries, the digit sum for 4n is at most 4s. It can only be 4s iff there are no carries. Similarly, 11n has digit sum at most 2s, with equality iff there are no carries.
Since 44n has digit sum 8s, there cannot be any carries. In particular, there are no carries in forming 4n, so each digit of n is at most 2. Hence there are no carries in forming 3n and the digit sum of 3n is 300.
Problem 14
The positive reals x, y satisfy x2 + y3 ≥ x3 + y4. Show that x3 + y3 ≤ 2.
Solution
If x, y both ≤ 1, then the inequality is obvious. If x, y both > 1, then they do not satisfy the condition. So either x ≥ 1 ≥ y or y ≥ 1 ≥ x. We show first that x3 + y3 ≤ x2 + y2. In the first case we have x2 + y2(1-y) ≥ x2 + y3(1-y) ≥ x3 + y4 - y4 = x3, so x2 + y2 ≥ x3 + y3, as required. In the second case we have x2 ≥ x3 + y3(y-1) ≥ x3 + y2(y-1), so again x2 + y2 ≥ x3 + y3.
Now by Cauchy-Scwartz, x2 + y2 = x3/2x1/2 + y3/2y1/2 ≤ √(x3+y3) √(x+y). But x2 + y2 ≥ x3 + y3, so x2 + y2 ≤ x + y. But 2xy ≤ (x2+y2), so (x + y)2 ≤ & 2(x2 + y2) and we have just shown that 2(x2 + y2) ≤ 2(x + y), so x + y ≤ 2. Thus we have x3 + y3 ≤ x2 + y2 ≤ x + y ≤ 2.
Thanks to Bekjan Jumabaev
Problem 16
Do there exist 19 distinct positive integers whose sum is 1999 and each of which has the same digit sum?
Answer
no
Solution
Suppose each of the integers has digit sum k. Then each number = k mod 9 and so their sum = 19k mod 9. But their sum is 1999 = 1 mod 9. Hence k = 1 mod 9. So k = 1 or 10 or k ≥ 19. If k = 1, then the only possible numbers under 1999 are 1, 10, 100, 1000, so we cannot get 19 distinct integers. If k ≥ 19, then each number must have at least 3 digits. So their sum is at least 100 + 101 + ... + 118 = 2071 > 1999. So we must have k = 10.
The 20 smallest integers with digit sum 10 are: 19, 28, 37, 46, 55, 64, 73, 82, 91, 109, 118, 127, 136, 145, 154, 163, 172, 181, 190, 208. The sum of the first 19 is 1990, which is too small. However, the next smallest sum comes from replacing 190 by 208, but that gives 2008, which is too large.
Problem 19
Four positive integers have the property that the square of the sum of any two is divisible by the product of the other two. Show that at least three of the integers are equal.
Solution
Suppose that we can find 4 such integers with no three equal. Let a, b, c, d be the set with the smallest a + b + c + d. Suppose a prime p divides a and b. Since a divides (b+c)2 and (c+d)2, it follows that p must divide b+c and c+d. Hence it divides c and d. But now a/p, b/p, c/p, d/p has the same property and smaller sum. Contradiction.
Now suppose an odd prime p divides a. Then p must divide b+c, c+d and d+b and hence also their sum 2(b+c+d). But p is odd, so it must divide b+c+d and hence b = (b+c+d) - (c+d). Contradiction. So a must be a power of 2. Similarly, b, c, d must be powers of 2. If two of them are > 1, then they have a common factor 2. Contradiction. So three of them must be 1. Contradiction.
Labels:
Russian Mathematical Olympiad
Previous Article
