MathDB
Problems
Contests
National and Regional Contests
Russia Contests
239 Open Math Olympiad
2019 239 Open Mathematical Olympiad
2019 239 Open Mathematical Olympiad
Part of
239 Open Math Olympiad
Subcontests
(8)
8
2
Hide problems
Correct coloring
Given a natural number
k
>
1
k> 1
k
>
1
. Prove that if through any edge of the graph
G
G
G
passes less than
[
e
(
k
−
1
)
!
−
1
]
[e(k-1)! - 1]
[
e
(
k
−
1
)!
−
1
]
simple cycles, then the vertices of this graph can be colored with
k
k
k
colors in the correct way.
Help the band with their instruments
There are
n
n
n
instruments in the laboratory, each two of them can be connected with a wire. Moreover, if four devices
A
,
B
,
C
,
D
A, B, C, D
A
,
B
,
C
,
D
, are such that wires of
A
B
AB
A
B
,
B
C
BC
BC
and
C
D
CD
C
D
are connected but there is no connected pair between
C
A
CA
C
A
,
A
D
AD
A
D
and
D
B
DB
D
B
, a collapse occurs. A professor invented a wiring diagram that does not collapse. Coming to the laboratory, he found that the collapse has not yet occurred, but the devices are connected not according to his scheme. Prove that he can implement his scheme, each time connecting or disconnecting a pair of devices, so that the collapse won’t happen anytime.
7
1
Hide problems
Inequality with 4n numbers
Given positive numbers
a
1
,
…
,
a
n
a_1, \ldots , a_n
a
1
,
…
,
a
n
,
b
1
,
…
,
b
n
b_1, \ldots , b_n
b
1
,
…
,
b
n
,
c
1
,
…
,
c
n
c_1, \ldots , c_n
c
1
,
…
,
c
n
. Let
m
k
m_k
m
k
be the maximum of the products
a
i
b
j
c
l
a_ib_jc_l
a
i
b
j
c
l
over the sets
(
i
,
j
,
l
)
(i, j, l)
(
i
,
j
,
l
)
for which
m
a
x
(
i
,
j
,
l
)
=
k
max(i, j, l) = k
ma
x
(
i
,
j
,
l
)
=
k
. Prove that
(
a
1
+
…
+
a
n
)
(
b
1
+
…
+
b
n
)
(
c
1
+
…
+
c
n
)
≤
n
2
(
m
1
+
…
+
m
n
)
.
(a_1 + \ldots + a_n) (b_1 +\ldots + b_n) (c_1 +\ldots + c_n) \leq n^2 (m_1 + \ldots + m_n).
(
a
1
+
…
+
a
n
)
(
b
1
+
…
+
b
n
)
(
c
1
+
…
+
c
n
)
≤
n
2
(
m
1
+
…
+
m
n
)
.
6
1
Hide problems
Two conditions for f(x)
Find all functions
f
:
(
0
,
+
∞
)
→
R
f : (0, +\infty) \to \mathbb{R}
f
:
(
0
,
+
∞
)
→
R
satisfying the following conditions:
(
i
)
(i)
(
i
)
f
(
x
)
+
f
(
1
x
)
=
1
f(x) + f(\frac{1}{x}) = 1
f
(
x
)
+
f
(
x
1
)
=
1
for all
x
>
0
x> 0
x
>
0
;
(
i
i
)
(ii)
(
ii
)
f
(
x
y
+
x
+
y
)
=
f
(
x
)
f
(
y
)
f(xy + x + y) = f(x)f(y)
f
(
x
y
+
x
+
y
)
=
f
(
x
)
f
(
y
)
for all
x
,
y
>
0
x, y> 0
x
,
y
>
0
.
5
2
Hide problems
Tangent circles
Circle
Γ
\Gamma
Γ
touches the circumcircle of triangle
A
B
C
ABC
A
BC
at point
R
R
R
, and it touches the sides
A
B
AB
A
B
and
A
C
AC
A
C
at points
P
P
P
and
Q
Q
Q
, respectively. Rays
P
Q
PQ
PQ
and
B
C
BC
BC
intersect at point
X
X
X
. The tangent line at point
R
R
R
to the circle
Γ
\Gamma
Γ
meets the segment
Q
X
QX
QX
at point
Y
Y
Y
. The line segment
A
X
AX
A
X
intersects the circumcircle of triangle
A
P
Q
APQ
A
PQ
at point
Z
Z
Z
. Prove that the circumscribed circles of triangles
A
B
C
ABC
A
BC
and
X
Y
Z
XY Z
X
Y
Z
are tangent.
n! good sets
We call an ordered set of distinct natural numbers good if for any two numbers in it, the larger one is divided by the smaller one. Prove that the number
(
n
+
1
)
!
–
1
(n + 1)! – 1
(
n
+
1
)!
–1
can be represented as
x
1
+
2
x
2
+
…
+
n
x
n
x_1 + 2x_2 + \ldots + nx_n
x
1
+
2
x
2
+
…
+
n
x
n
, where
{
x
1
,
x
2
,
…
,
x
n
}
\{ x_1, x_2, \ldots , x_n \}
{
x
1
,
x
2
,
…
,
x
n
}
is a good set, by at least
n
!
n!
n
!
ways.
4
2
Hide problems
Truth or lie at a table
There are
n
>
1000
n>1000
n
>
1000
people at a round table. Some of them are knights who always tell the truth, and the rest are liars who always tell lies. Each of those sitting said the phrase: “among the
20
20
20
people sitting clockwise from where I sit there are as many knights as among the
20
20
20
people seated counterclockwise from where I sit”. For what
n
n
n
could this happen?
20x20 treasure map
A
20
×
20
20 \times 20
20
×
20
treasure map is glued to a torus. A treasure is hidden in a cell of this map. We can ask questions about
1
×
4
1\times 4
1
×
4
or
4
×
1
4 \times 1
4
×
1
rectangles so that we find out if there is a treasure in this rectangle or not. The answers to all questions are absolutely true, but they are given only after all rectangles we want to ask are set. What is the least amount of questions needed to be asked so that we can be sure to find the treasure? (If you describe the position of the cells in a torus with numbers
(
i
,
j
)
(i, j)
(
i
,
j
)
of row and column,
1
≤
i
,
j
≤
20
1 \leq i, j \leq 20
1
≤
i
,
j
≤
20
, then two cells are neighbors, if and only if two of the coordinates they have are the same, and the other two differ by
1
1
1
mod
20
20
20
.)
3
2
Hide problems
Calculating the radius length
The radius of the circumscribed circle of an acute-angled triangle is
23
23
23
and the radius of its Inscribed circle is
9
9
9
. Common external tangents to its ex-circles, other than straight lines containing the sides of the original triangle, form a triangle. Find the radius of its inscribed circle.
Making a triangle with 3 segments
Circle
ω
\omega
ω
touches the side
A
C
AC
A
C
of the equilateral triangle
A
B
C
ABC
A
BC
at point
D
D
D
, and its circumcircle at the point
E
E
E
lying on the arc \overarc{BC}. Prove that with segments
A
D
AD
A
D
,
B
E
BE
BE
and
C
D
CD
C
D
, you can form a triangle, in which the difference of two of its angles is
6
0
∘
60^{\circ}
6
0
∘
.
2
2
Hide problems
Splitting 100x100 table into rectangles
Several cells are marked in a
100
×
100
100 \times 100
100
×
100
table. Vasya wants to split the square into several rectangles such that each rectangle does not contain more than two marked cells and there are at most
k
k
k
rectangles containing less than two cells. What is the smallest
k
k
k
such that Vasya will certainly be able to do this?
Consecutive numbers with 900 divisors
Is it true that there are
130
130
130
consecutive natural numbers, such that each of them has exactly
900
900
900
natural divisors?
1
2
Hide problems
Differences of fractions
The following fractions are written on the board
1
n
,
2
n
−
1
,
3
n
−
2
,
…
,
n
1
\frac{1}{n}, \frac{2}{n-1}, \frac{3}{n-2}, \ldots , \frac{n}{1}
n
1
,
n
−
1
2
,
n
−
2
3
,
…
,
1
n
where
n
n
n
is a natural number. Vasya calculated the differences of the neighboring fractions in this row and found among them
10000
10000
10000
fractions of type
1
k
\frac{1}{k}
k
1
(with natural
k
k
k
). Prove that he can find even
5000
5000
5000
more of such these differences.
Island of knights and liars
On the island of knights and liars, a tennis tournament was held, in which
100
100
100
people participated in. Each two of them played exactly
1
1
1
time with the other one. After the tournament, each of the participants declared: “I have beaten as many knights as liars,” while all the knights told the truth, and all the liars lied. What is the largest number of knights that could participate in the tournament?