MathDB

2009 All-Russian Olympiad

Part of All-Russian Olympiad

Subcontests

(8)
6
3

Colored positive integers with 2009 colors

Can be colored the positive integers with 2009 colors if we know that each color paints infinitive integers and that we can not find three numbers colored by three different colors for which the product of two numbers equal to the third one?

a finite tree and isomorphism

Given a finite tree T T and isomorphism f:T→T f: T\rightarrow T. Prove that either there exist a vertex a a such that f(a)\equal{}a or there exist two neighbor vertices a a, b b such that f(a)\equal{}b, f(b)\equal{}a.

k rooks on a 10x10 chessboard

There are k k rooks on a 10×10 10 \times 10 chessboard. We mark all the squares that at least one rook can capture (we consider the square where the rook stands as captured by the rook). What is the maximum value of k k so that the following holds for some arrangement of k k rooks: after removing any rook from the chessboard, there is at least one marked square not captured by any of the remaining rooks.
3
3

Prove that a > n^4 - n^3

Given are positive integers n>1 n>1 and a a so that a>n2 a>n^2, and among the integers a\plus{}1, a\plus{}2, \ldots, a\plus{}n one can find a multiple of each of the numbers n^2\plus{}1, n^2\plus{}2, \ldots, n^2\plus{}n. Prove that a>n^4\minus{}n^3.

Change the sign of the funtion

How many times changes the sign of the function f(x)\equal{}\cos x\cos\frac{x}{2}\cos\frac{x}{3}\cdots\cos\frac{x}{2009} at the interval [0,2009π2] \left[0, \frac{2009\pi}{2}\right]?

center of the sphere circumscribed to a pyramid

Let ABCD ABCD be a triangular pyramid such that no face of the pyramid is a right triangle and the orthocenters of triangles ABC ABC, ABD ABD, and ACD ACD are collinear. Prove that the center of the sphere circumscribed to the pyramid lies on the plane passing through the midpoints of AB AB, AC AC and AD AD.
8
2
1
3

irreducible fractions

The denominators of two irreducible fractions are 600 and 700. Find the minimum value of the denominator of their sum (written as an irreducible fraction).

Number of nonzero coefficients

Find all value of n n for which there are nonzero real numbers a,b,c,d a, b, c, d such that after expanding and collecting similar terms, the polynomial (ax \plus{} b)^{100} \minus{} (cx \plus{} d)^{100} has exactly n n nonzero coefficients.

the roads in a country

In a country, there are some cities linked together by roads. The roads just meet each other inside the cities. In each city, there is a board which showing the shortest length of the road originating in that city and going through all other cities (the way can go through some cities more than one times and is not necessary to turn back to the originated city). Prove that 2 random numbers in the boards can't be greater or lesser than 1.5 times than each other.
5
3

Prove that abc = 0

Let a a, b b, c c be three real numbers satisfying that \left\{\begin{array}{c c c} \left(a\plus{}b\right)\left(b\plus{}c\right)\left(c\plus{}a\right)&\equal{}&abc\\ \left(a^3\plus{}b^3\right)\left(b^3\plus{}c^3\right)\left(c^3\plus{}a^3\right)&\equal{}&a^3b^3c^3\end{array}\right. Prove that abc\equal{}0.

Find the least possible value

Given strictly increasing sequence a1<a2<… a_1<a_2<\dots of positive integers such that each its term ak a_k is divisible either by 1005 or 1006, but neither term is divisible by 97 97. Find the least possible value of maximal difference of consecutive terms a_{i\plus{}1}\minus{}a_i.

Logarithm innequality

Prove that \log_ab\plus{}\log_bc\plus{}\log_ca\le \log_ba\plus{}\log_cb\plus{}\log_ac for all 1<a≤b≤c 1<a\le b\le c.
2
2
7
2

maximum number of times which the rook jumped over the fence

We call any eight squares in a diagonal of a chessboard as a fence. The rook is moved on the chessboard in such way that he stands neither on each square over one time nor on the squares of the fences (the squares which the rook passes is not considered ones it has stood on). Then what is the maximum number of times which the rook jumped over the fence?

Common tangent passes through A

The incircle (I) (I) of a given scalene triangle ABC ABC touches its sides BC BC, CA CA, AB AB at A1 A_1, B1 B_1, C1 C_1, respectively. Denote ωB \omega_B, ωC \omega_C the incircles of quadrilaterals BA1IC1 BA_1IC_1 and CA1IB1 CA_1IB_1, respectively. Prove that the internal common tangent of ωB \omega_B and ωC \omega_C different from IA1 IA_1 passes through A A.
4
3

2009 numbers on a circle

On a circle there are 2009 nonnegative integers not greater than 100. If two numbers sit next to each other, we can increase both of them by 1. We can do this at most k k times. What is the minimum k k so that we can make all the numbers on the circle equal?

Nice problem about finding a coin

There are n cups arranged on the circle. Under one of cups is hiden a coin. For every move, it is allowed to choose 4 cups and verify if the coin lies under these cups. After that, the cups are returned into its former places and the coin moves to one of two neigbor cups. What is the minimal number of moves we need in order to eventually find where the coin is?

A game with a set of points

Given a set M M of points (x,y) (x,y) with integral coordinates satisfying x2+y2≤1010 x^2 + y^2\leq 10^{10}. Two players play a game. One of them marks a point on his first move. After this, on each move the moving player marks a point, which is not yet marked and joins it with the previous marked point. Players are not allowed to mark a point symmetrical to the one just chosen. So, they draw a broken line. The requirement is that lengths of edges of this broken line must strictly increase. The player, which can not make a move, loses. Who have a winning strategy?