MathDB
Problems
Contests
National and Regional Contests
Russia Contests
All-Russian Olympiad
2000 All-Russian Olympiad
2000 All-Russian Olympiad
Part of
All-Russian Olympiad
Subcontests
(8)
6
3
Hide problems
2n x 2n board with white/black markers
On some cells of a
2
n
×
2
n
2n \times 2n
2
n
×
2
n
board are placed white and black markers (at most one marker on every cell). We first remove all black markers which are in the same column with a white marker, then remove all white markers which are in the same row with a black one. Prove that either the number of remaining white markers or that of remaining black markers does not exceed
n
2
n^2
n
2
.
v_p(n) != 1 for perfect n>6
A perfect number, greater than
6
6
6
, is divisible by
3
3
3
. Prove that it is also divisible by
9
9
9
.
v_7(n) != 1 for perfect n > 28
A perfect number, greater than
28
28
28
is divisible by
7
7
7
. Prove that it is also divisible by
49
49
49
.
5
3
Hide problems
a_(n+1) = a_n - 2 if new, else a_n + 3
The sequence
a
1
=
1
a_1 = 1
a
1
=
1
,
a
2
,
a
3
,
⋯
a_2, a_3, \cdots
a
2
,
a
3
,
⋯
is defined as follows: if
a
n
−
2
a_n - 2
a
n
−
2
is a natural number not already occurring on the board, then
a
n
+
1
=
a
n
−
2
a_{n+1} = a_n-2
a
n
+
1
=
a
n
−
2
; otherwise,
a
n
+
1
=
a
n
+
3
a_{n+1} = a_n + 3
a
n
+
1
=
a
n
+
3
. Prove that every nonzero perfect square occurs in the sequence as the previous term increased by
3
3
3
.
Every three elements have a sum in M
Let
M
M
M
be a finite sum of numbers, such that among any three of its elements there are two whose sum belongs to
M
M
M
. Find the greatest possible number of elements of
M
M
M
.
sin^n(2x) + (sin^n x - cos^n x)^2 <= 1
Prove the inequality
sin
n
(
2
x
)
+
(
sin
n
x
−
cos
n
x
)
2
≤
1.
\sin^n (2x) + \left( \sin^n x - \cos^n x \right)^2 \le 1.
sin
n
(
2
x
)
+
(
sin
n
x
−
cos
n
x
)
2
≤
1.
4
3
Hide problems
Degrees >= 3 implies cycle not div by 3
Some pairs of cities in a certain country are connected by roads, at least three roads going out of each city. Prove that there exists a round path consisting of roads whose number is not divisible by
3
3
3
.
Five weights
We are given five equal-looking weights of pairwise distinct masses. For any three weights
A
A
A
,
B
B
B
,
C
C
C
, we can check by a measuring if
m
(
A
)
<
m
(
B
)
<
m
(
C
)
m(A) < m(B) < m(C)
m
(
A
)
<
m
(
B
)
<
m
(
C
)
, where
m
(
X
)
m(X)
m
(
X
)
denotes the mass of a weight
X
X
X
(the answer is yes or no.) Can we always arrange the masses of the weights in the increasing order with at most nine measurings?
Sequences and unusual averages
Let
a
1
,
a
2
,
⋯
,
a
n
a_1, a_2, \cdots, a_n
a
1
,
a
2
,
⋯
,
a
n
be a sequence of nonnegative integers. For
k
=
1
,
2
,
⋯
,
n
k=1,2,\cdots,n
k
=
1
,
2
,
⋯
,
n
denote
m
k
=
max
1
≤
l
≤
k
a
k
−
l
+
1
+
a
k
−
l
+
2
+
⋯
+
a
k
l
.
m_k = \max_{1 \le l \le k} \frac{a_{k-l+1} + a_{k-l+2} + \cdots + a_k}{l}.
m
k
=
1
≤
l
≤
k
max
l
a
k
−
l
+
1
+
a
k
−
l
+
2
+
⋯
+
a
k
.
Prove that for every
α
>
0
\alpha > 0
α
>
0
the number of values of
k
k
k
for which
m
k
>
α
m_k > \alpha
m
k
>
α
is less than
a
1
+
a
2
+
⋯
+
a
n
α
.
\frac{a_1+a_2+ \cdots +a_n}{\alpha}.
α
a
1
+
a
2
+
⋯
+
a
n
.
2
3
Hide problems
Sasha guessing X <= 100 in 7 questions
Tanya chose a natural number
X
≤
100
X\le100
X
≤
100
, and Sasha is trying to guess this number. He can select two natural numbers
M
M
M
and
N
N
N
less than
100
100
100
and ask about
gcd
(
X
+
M
,
N
)
\gcd(X+M,N)
g
cd
(
X
+
M
,
N
)
. Show that Sasha can determine Tanya's number with at most seven questions.
Inequality in 2n variables with 13th powers
Let
−
1
<
x
1
<
x
2
,
⋯
<
x
n
<
1
-1 < x_1 < x_2 , \cdots < x_n < 1
−
1
<
x
1
<
x
2
,
⋯
<
x
n
<
1
and
x
1
13
+
x
2
13
+
⋯
+
x
n
13
=
x
1
+
x
2
+
⋯
+
x
n
x_1^{13} + x_2^{13} + \cdots + x_n^{13} = x_1 + x_2 + \cdots + x_n
x
1
13
+
x
2
13
+
⋯
+
x
n
13
=
x
1
+
x
2
+
⋯
+
x
n
. Prove that if
y
1
<
y
2
<
⋯
<
y
n
y_1 < y_2 < \cdots < y_n
y
1
<
y
2
<
⋯
<
y
n
, then
x
1
13
y
1
+
⋯
+
x
n
13
y
n
<
x
1
y
1
+
x
2
y
2
+
⋯
+
x
n
y
n
.
x_1^{13}y_1 + \cdots + x_n^{13}y_n < x_1y_1 + x_2y_2 + \cdots + x_ny_n.
x
1
13
y
1
+
⋯
+
x
n
13
y
n
<
x
1
y
1
+
x
2
y
2
+
⋯
+
x
n
y
n
.
Partition into 100 sets with condition a+99b=c
Prove that one can partition the set of natural numbers into
100
100
100
nonempty subsets such that among any three natural numbers
a
a
a
,
b
b
b
,
c
c
c
satisfying
a
+
99
b
=
c
a+99b=c
a
+
99
b
=
c
, there are two that belong to the same subset.
7
3
Hide problems
Prove that CMN is tangent to S1 and S2
Let
E
E
E
be a point on the median
C
D
CD
C
D
of a triangle
A
B
C
ABC
A
BC
. The circle
S
1
\mathcal S_1
S
1
passing through
E
E
E
and touching
A
B
AB
A
B
at
A
A
A
meets the side
A
C
AC
A
C
again at
M
M
M
. The circle
S
2
S_2
S
2
passing through
E
E
E
and touching
A
B
AB
A
B
at
B
B
B
meets the side
B
C
BC
BC
at
N
N
N
. Prove that the circumcircle of
△
C
M
N
\triangle CMN
△
CMN
is tangent to both
S
1
\mathcal S_1
S
1
and
S
2
\mathcal S_2
S
2
.
Two circles are tangent
Two circles are internally tangent at
N
N
N
. The chords
B
A
BA
B
A
and
B
C
BC
BC
of the larger circle are tangent to the smaller circle at
K
K
K
and
M
M
M
respectively.
Q
Q
Q
and
P
P
P
are midpoint of arcs
A
B
AB
A
B
and
B
C
BC
BC
respectively. Circumcircles of triangles
B
Q
K
BQK
BQ
K
and
B
P
M
BPM
BPM
are intersect at
L
L
L
. Show that
B
P
L
Q
BPLQ
BP
L
Q
is a parallelogram.
Suppose O,K,L are collinear
A quadrilateral
A
B
C
D
ABCD
A
BC
D
is circumscribed about a circle
ω
\omega
ω
. The lines
A
B
AB
A
B
and
C
D
CD
C
D
meet at
O
O
O
. A circle
ω
1
\omega_1
ω
1
is tangent to side
B
C
BC
BC
at
K
K
K
and to the extensions of sides
A
B
AB
A
B
and
C
D
CD
C
D
, and a circle
ω
2
\omega_2
ω
2
is tangent to side
A
D
AD
A
D
at
L
L
L
and to the extensions of sides
A
B
AB
A
B
and
C
D
CD
C
D
. Suppose that points
O
O
O
,
K
K
K
,
L
L
L
lie on a line. Prove that the midpoints of
B
C
BC
BC
and
A
D
AD
A
D
and the center of
ω
\omega
ω
also lie on a line.
3
3
Hide problems
K is the circumcenter of triangle AOC
Let
O
O
O
be the center of the circumcircle
ω
\omega
ω
of an acute-angle triangle
A
B
C
ABC
A
BC
. A circle
ω
1
\omega_1
ω
1
with center
K
K
K
passes through
A
A
A
,
O
O
O
,
C
C
C
and intersects
A
B
AB
A
B
at
M
M
M
and
B
C
BC
BC
at
N
N
N
. Point
L
L
L
is symmetric to
K
K
K
with respect to line
N
M
NM
NM
. Prove that
B
L
⊥
A
C
BL \perp AC
B
L
⊥
A
C
.
P,B,Q,R lie on a circle
In an acute scalene triangle
A
B
C
ABC
A
BC
the bisector of the acute angle between the altitudes
A
A
1
AA_1
A
A
1
and
C
C
1
CC_1
C
C
1
meets the sides
A
B
AB
A
B
and
B
C
BC
BC
at
P
P
P
and
Q
Q
Q
respectively. The bisector of the angle
B
B
B
intersects the segment joining the orthocenter of
A
B
C
ABC
A
BC
and the midpoint of
A
C
AC
A
C
at point
R
R
R
. Prove that
P
P
P
,
B
B
B
,
Q
Q
Q
,
R
R
R
lie on a circle.
Convex Pentagon in a lattice
A convex pentagon
A
B
C
D
E
ABCDE
A
BC
D
E
is given in the coordinate plane with all vertices in lattice points. Prove that there must be at least one lattice point in the pentagon determined by the diagonals
A
C
AC
A
C
,
B
D
BD
B
D
,
C
E
CE
CE
,
D
A
DA
D
A
,
E
B
EB
EB
or on its boundary.
1
3
Hide problems
Quadratics with Common Roots
Let
a
,
b
,
c
a,b,c
a
,
b
,
c
be distinct numbers such that the equations
x
2
+
a
x
+
1
=
0
x^2+ax+1=0
x
2
+
a
x
+
1
=
0
and
x
2
+
b
x
+
c
=
0
x^2+bx+c=0
x
2
+
b
x
+
c
=
0
have a common real root, and the equations
x
2
+
x
+
a
=
0
x^2+x+a=0
x
2
+
x
+
a
=
0
and
x
2
+
c
x
+
b
x^2+cx+b
x
2
+
c
x
+
b
also have a common real root. Compute the sum
a
+
b
+
c
a+b+c
a
+
b
+
c
.
Sum floor 2^k/3 from k=0 to 100
Evaluate the sum
⌊
2
0
3
⌋
+
⌊
2
1
3
⌋
+
⌊
2
2
3
⌋
+
⋯
+
⌊
2
1000
3
⌋
.
\left\lfloor \frac{2^0}{3} \right\rfloor + \left\lfloor \frac{2^1}{3} \right\rfloor + \left\lfloor \frac{2^2}{3} \right\rfloor + \cdots + \left\lfloor \frac{2^{1000}}{3} \right\rfloor.
⌊
3
2
0
⌋
+
⌊
3
2
1
⌋
+
⌊
3
2
2
⌋
+
⋯
+
⌊
3
2
1000
⌋
.
Functions
Find all functions
f
:
R
⟶
R
f: \mathbb{R}\longrightarrow \mathbb{R}
f
:
R
⟶
R
such that f(x\plus{}y)\plus{}f(y\plus{}z)\plus{}f(z\plus{}x)\ge 3f(x\plus{}2y\plus{}3z) for all
x
,
y
,
z
∈
R
x, y, z \in \mathbb R
x
,
y
,
z
∈
R
.
8
3
Hide problems
100 numbers around a circle
One hundred natural numbers whose greatest common divisor is
1
1
1
are arranged around a circle. An allowed operation is to add to a number the greatest common divisor of its two neighhbors. Prove that we can make all the numbers pairwise copirme in a finite number of moves.
Nailing Paper Squares
Some paper squares of
k
k
k
distinct colors are placed on a rectangular table, with sides parallel to the sides of the table. Suppose that for any
k
k
k
squares of distinct colors, some two of them can be nailed on the table with only one nail. Prove that there is a color such that all squares of that color can be nailed with
2
k
−
2
2k-2
2
k
−
2
nails.
Coloring 100 x 100 array of points in four colors
All points in a
100
×
100
100 \times 100
100
×
100
array are colored in one of four colors red, green, blue or yellow in such a way that there are
25
25
25
points of each color in each row and in any column. Prove that there are two rows and two columns such that their four intersection points are all in different colors.