MathDB
Problems
Contests
National and Regional Contests
Russia Contests
Saint Petersburg Mathematical Olympiad
2020 Saint Petersburg Mathematical Olympiad
2020 Saint Petersburg Mathematical Olympiad
Part of
Saint Petersburg Mathematical Olympiad
Subcontests
(8)
7.
2
Hide problems
Classical combi
The exam has
25
25
25
topics, each of which has
8
8
8
questions. On a test, there are
4
4
4
questions of different topics. Is it possible to make
50
50
50
tests so that each question was asked exactly once, and for any two topics there is a test where are questions of both topics?
Graph problem that is given as a graph problem, unusual
Let
G
G
G
be a graph with
400
400
400
vertices. For any edge
A
B
AB
A
B
we call a cuttlefish the set of all edges from
A
A
A
and
B
B
B
(including
A
B
AB
A
B
). Each edge of the graph is assigned a value of
1
1
1
or
−
1
-1
−
1
. It is known that the sum of edges at any cuttlefish is greater than or equal to
1
1
1
. Prove that the sum of the numbers at all edges is at least
−
1
0
4
-10^4
−
1
0
4
.
7
1
Hide problems
Some oligarchs want to create a corporate
N
N
N
oligarchs built a country with
N
N
N
cities with each one of them owning one city. In addition, each oligarch built some roads such that the maximal amount of roads an oligarch can build between two cities is
1
1
1
(note that there can be more than
1
1
1
road going through two cities, but they would belong to different oligarchs). A total of
d
d
d
roads were built. Some oligarchs wanted to create a corporation by combining their cities and roads so that from any city of the corporation you can go to any city of the corporation using only corporation roads (roads can go to other cities outside corporation) but it turned out that no group of less than
N
N
N
oligarchs can create a corporation. What is the maximal amount that
d
d
d
can have?
5.
3
Hide problems
Geometric inequality again
The altitudes
B
B
1
BB_1
B
B
1
and
C
C
1
CC_1
C
C
1
of the acute triangle
△
A
B
C
\triangle ABC
△
A
BC
intersect at
H
H
H
. The circle centered at
O
b
O_b
O
b
passes through points
A
,
C
1
A,C_1
A
,
C
1
, and the midpoint of
B
H
BH
B
H
. The circle centered at
O
c
O_c
O
c
passes through
A
,
B
1
A,B_1
A
,
B
1
and the midpoint of
C
H
CH
C
H
. Prove that
B
1
O
b
+
C
1
O
c
>
B
C
4
B_1 O_b +C_1O_c > \frac{BC}{4}
B
1
O
b
+
C
1
O
c
>
4
BC
Rays passing through a point
Rays
ℓ
,
ℓ
1
,
ℓ
2
\ell, \ell_1, \ell_2
ℓ
,
ℓ
1
,
ℓ
2
have the same starting point
O
O
O
, such that the angle between
ℓ
\ell
ℓ
and
ℓ
2
\ell_2
ℓ
2
is acute and the ray
ℓ
1
\ell_1
ℓ
1
lies inside this angle. The ray
ℓ
\ell
ℓ
contains a fixed point of
F
F
F
and an arbitrary point
L
L
L
. Circles passing through
F
F
F
and
L
L
L
and tangent to
ℓ
1
\ell_1
ℓ
1
at
L
1
L_1
L
1
, and passing through
F
F
F
and
L
L
L
and tangent to
ℓ
2
\ell_2
ℓ
2
at
L
2
L_2
L
2
. Prove that the circumcircle of
△
F
L
1
L
2
\triangle FL_1L_2
△
F
L
1
L
2
passes through a fixed point other than
F
F
F
independent on
L
L
L
.
an excircle and 4 points
Point
I
a
I_a
I
a
is the
A
A
A
-excircle center of
△
A
B
C
\triangle ABC
△
A
BC
which is tangent to
B
C
BC
BC
at
X
X
X
. Let
A
′
A'
A
′
be diametrically opposite point of
A
A
A
with respect to the circumcircle of
△
A
B
C
\triangle ABC
△
A
BC
. On the segments
I
a
X
,
B
A
′
I_aX, BA'
I
a
X
,
B
A
′
and
C
A
′
CA'
C
A
′
are chosen respectively points
Y
,
Z
Y,Z
Y
,
Z
and
T
T
T
such that
I
a
Y
=
B
Z
=
C
T
=
r
I_aY=BZ=CT=r
I
a
Y
=
BZ
=
CT
=
r
where
r
r
r
is the inradius of
△
A
B
C
\triangle ABC
△
A
BC
. Prove that the points
X
,
Y
,
Z
X,Y,Z
X
,
Y
,
Z
and
T
T
T
are concyclic.
6.
3
Hide problems
a_{n+2}=a_n(a_{n+1}+1) then (a_n)^n |a_{a_n}
The sequence
a
n
a_n
a
n
is given as a_1=1, a_2=2 \;\;\; \text{and} \;\;\;\; a_{n+2}=a_n(a_{n+1}+1) \forall n\geq 1 Prove that
a
a
n
a_{a_n}
a
a
n
is divisible by
(
a
n
)
n
(a_n)^n
(
a
n
)
n
for
n
≥
100
n\geq 100
n
≥
100
.
a connected social network
On a social network, no user has more than ten friends ( the state "friendship" is symmetrical). The network is connected: if, upon learning interesting news a user starts sending it to its friends, and these friends to their own friends and so on, then at the end, all users hear about the news. Prove that the network administration can divide users into groups so that the following conditions are met:[*] each user is in exactly one group [*] each group is connected in the above sense [*] one of the groups contains from
1
1
1
to
100
100
100
members and the remaining from
100
100
100
to
900
900
900
.
(1,1),(2,3),(4,5) and (999,111) exists point on y=2x
The points
(
1
,
1
)
,
(
2
,
3
)
,
(
4
,
5
)
(1,1),(2,3),(4,5)
(
1
,
1
)
,
(
2
,
3
)
,
(
4
,
5
)
and
(
999
,
111
)
(999,111)
(
999
,
111
)
are marked in the coordinate system. We continue to mark points in the following way : [*]If points
(
a
,
b
)
(a,b)
(
a
,
b
)
are marked then
(
b
,
a
)
(b,a)
(
b
,
a
)
and
(
a
−
b
,
a
+
b
)
(a-b,a+b)
(
a
−
b
,
a
+
b
)
can be marked [*]If points
(
a
,
b
)
(a,b)
(
a
,
b
)
and
(
c
,
d
)
(c,d)
(
c
,
d
)
are marked then so can be
(
a
d
+
b
c
,
4
a
c
−
4
b
d
)
(ad+bc, 4ac-4bd)
(
a
d
+
b
c
,
4
a
c
−
4
b
d
)
.Can we, after some finite number of these steps, mark a point belonging to the line
y
=
2
x
y=2x
y
=
2
x
.
2.
3
Hide problems
sum of some divisors is a square
Find all positive integers
n
n
n
such that the sum of the squares of the five smallest divisors of
n
n
n
is a square.
Rooks that can not see well
A short-sighted rook is a rook that beats all squares in the same column and in the same row for which he can not go more than
60
60
60
-steps. What is the maximal amount of short-sighted rooks that don't beat each other that can be put on a
100
×
100
100\times 100
100
×
100
chessboard.
three interesting numbers
For the triple
(
a
,
b
,
c
)
(a,b,c)
(
a
,
b
,
c
)
of positive integers we say it is interesting if
c
2
+
1
∣
(
a
2
+
1
)
(
b
2
+
1
)
c^2+1\mid (a^2+1)(b^2+1)
c
2
+
1
∣
(
a
2
+
1
)
(
b
2
+
1
)
but none of the
a
2
+
1
,
b
2
+
1
a^2+1, b^2+1
a
2
+
1
,
b
2
+
1
are divisible by
c
2
+
1
c^2+1
c
2
+
1
. Let
(
a
,
b
,
c
)
(a,b,c)
(
a
,
b
,
c
)
be an interesting triple, prove that there are positive integers
u
,
v
u,v
u
,
v
such that
(
u
,
v
,
c
)
(u,v,c)
(
u
,
v
,
c
)
is interesting and
u
v
<
c
3
uv<c^3
uv
<
c
3
.
3.
2
Hide problems
Concyclic points and a bisector
B
B
1
BB_1
B
B
1
is the angle bisector of
△
A
B
C
\triangle ABC
△
A
BC
, and
I
I
I
is its incenter. The perpendicular bisector of segment
A
C
AC
A
C
intersects the circumcircle of
△
A
I
C
\triangle AIC
△
A
I
C
at
D
D
D
and
E
E
E
. Point
F
F
F
is on the segment
B
1
C
B_1C
B
1
C
such that
A
B
1
=
C
F
AB_1=CF
A
B
1
=
CF
.Prove that the four points
B
,
D
,
E
B, D, E
B
,
D
,
E
and
F
F
F
are concyclic.
Geometric inequality
On the side
A
D
AD
A
D
of the convex quadrilateral
A
B
C
D
ABCD
A
BC
D
with an acute angle at
B
B
B
, a point
E
E
E
is marked. It is known that
∠
C
A
D
=
∠
A
D
C
=
∠
A
B
E
=
∠
D
B
E
\angle CAD = \angle ADC=\angle ABE =\angle DBE
∠
C
A
D
=
∠
A
D
C
=
∠
A
BE
=
∠
D
BE
. (Grade 9 version) Prove that
B
E
+
C
E
<
A
D
BE+CE<AD
BE
+
CE
<
A
D
. (Grade 10 version) Prove that
△
B
C
E
\triangle BCE
△
BCE
is isosceles.(Here the condition that
∠
B
\angle B
∠
B
is acute is not necessary.)
1.
3
Hide problems
Pythagorean triple thing
A positive integer is called hypotenuse if it can be represented as a sum of two squares of non-negative integers. Prove that any natural number greater than
10
10
10
is the difference of two hypotenuse numbers.
weights and stones
Andryusha has
100
100
100
stones of different weight and he can distinguish the stones by appearance, but does not know their weight. Every evening, Andryusha can put exactly
10
10
10
stones on the table and at night the brownie will order them in increasing weight. But, if the drum also lives in the house then surely he will in the morning change the places of some
2
2
2
stones.Andryusha knows all about this but does not know if there is a drum in his house. Can he find out?
Maximal number of solutions
What is the maximal number of solutions can the equation have
max
{
a
1
x
+
b
1
,
a
2
x
+
b
2
,
…
,
a
10
x
+
b
10
}
=
0
\max \{a_1x+b_1, a_2x+b_2, \ldots, a_{10}x+b_{10}\}=0
max
{
a
1
x
+
b
1
,
a
2
x
+
b
2
,
…
,
a
10
x
+
b
10
}
=
0
where
a
1
,
b
1
,
a
2
,
b
2
,
…
,
a
10
,
b
10
a_1,b_1, a_2, b_2, \ldots , a_{10},b_{10}
a
1
,
b
1
,
a
2
,
b
2
,
…
,
a
10
,
b
10
are real numbers, all
a
i
a_i
a
i
not equal to
0
0
0
.
4.
3
Hide problems
2/3*6 + 2*5/3*6*9 + ... + 2*5*...*2015/3*6...*2019
The sum
2
3
⋅
6
+
2
⋅
5
3
⋅
6
⋅
9
+
…
+
2
⋅
5
⋅
…
⋅
2015
3
⋅
6
⋅
9
⋅
…
⋅
2019
\frac{2}{3\cdot 6} +\frac{2\cdot 5}{3\cdot 6\cdot 9} +\ldots +\frac{2\cdot5\cdot \ldots \cdot 2015}{3\cdot 6\cdot 9\cdot \ldots \cdot 2019}
3
⋅
6
2
+
3
⋅
6
⋅
9
2
⋅
5
+
…
+
3
⋅
6
⋅
9
⋅
…
⋅
2019
2
⋅
5
⋅
…
⋅
2015
is written as a decimal number. Find the first digit after the decimal point.
Inequality over integers
Let
m
m
m
be a given positive integer. Prove that there exists a positive integer
k
k
k
such that it holds
1
≤
1
m
+
2
m
+
3
m
+
…
+
(
k
−
1
)
m
k
m
<
2.
1\leq \frac{1^m+2^m+3^m+\ldots +(k-1)^m}{k^m}<2.
1
≤
k
m
1
m
+
2
m
+
3
m
+
…
+
(
k
−
1
)
m
<
2.
Game of Columns
On a table with
25
25
25
columns and
300
300
300
rows, Kostya painted all its cells in three colors. Then, Lesha, looking at the table, for each row names one of the three colors and marks in that row all cells of that color (if there are no cells of that color in that row, he does nothing). After that, all columns that have at least a marked square will be deleted. Kostya wants to be left as few as possible columns in the table, and Lesha wants there to be as many as possible columns in the table. What is the largest number of columns Lesha can guarantee to leave?