25th Russian 1999

25th Russian 1999 problems


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 n² 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} + ... + {√(n²)} ≤ (n² - 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 a₁, a₂, a₃, ... of positive integers is determined by its first two members and the rule a_n+2 = (a_n+1 + a_n)/gcd(a_n, a_n+1). For which values of a₁ and a₂ 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 n²/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 x² + y³ ≥ x³ + y⁴. Show that x³ + y³ ≤ 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 60^o iff the product of each pair of opposite sides of the tetrahedron is equal.