MathDB
Problems
Contests
National and Regional Contests
Russia Contests
All-Russian Olympiad
2023 All-Russian Olympiad
2023 All-Russian Olympiad
Part of
All-Russian Olympiad
Subcontests
(8)
2
2
Hide problems
Operation with binary strings
Initially, a word of
250
250
250
letters with
125
125
125
letters
A
A
A
and
125
125
125
letters
B
B
B
is written on a blackboard. In each operation, we may choose a contiguous string of any length with equal number of letters
A
A
A
and equal number of letters
B
B
B
, reverse those letters and then swap each
B
B
B
with
A
A
A
and each
A
A
A
with
B
B
B
(Example:
A
B
A
B
B
A
ABABBA
A
B
A
BB
A
after the operation becomes
B
A
A
B
A
B
BAABAB
B
AA
B
A
B
). Decide if it possible to choose initial word, so that after some operations, it will become the same as the first word, but in reverse order.
Averages can’t be pairwise distinct
A group of
100
100
100
kids has a deck of
101
101
101
cards numbered by
0
,
1
,
2
,
…
,
100
0, 1, 2,\dots, 100
0
,
1
,
2
,
…
,
100
. The first kid takes the deck, shuffles it, and then takes the cards one by one; when he takes a card (not the last one in the deck), he computes the average of the numbers on the cards he took up to that moment, and writes down this average on the blackboard. Thus, he writes down
100
100
100
numbers, the first of which is the number on the first taken card. Then he passes the deck to the second kid which shuffles the deck and then performs the same procedure, and so on. This way, each of
100
100
100
kids writes down
100
100
100
numbers. Prove that there are two equal numbers among the
10000
10000
10000
numbers on the blackboard.
8
3
Hide problems
A weird device
Petya has
10
,
000
10, 000
10
,
000
balls, among them there are no two balls of equal weight. He also has a device, which works as follows: if he puts exactly
10
10
10
balls on it, it will report the sum of the weights of some two of them (but he doesn't know which ones). Prove that Petya can use the device a few times so that after a while he will be able to choose one of the balls and accurately tell its weight.
n-variable inequality
Given is a real number
a
∈
(
0
,
1
)
a \in (0,1)
a
∈
(
0
,
1
)
and positive reals
x
0
,
x
1
,
…
,
x
n
x_0, x_1, \ldots, x_n
x
0
,
x
1
,
…
,
x
n
such that
∑
x
i
=
n
+
a
\sum x_i=n+a
∑
x
i
=
n
+
a
and
∑
1
x
i
=
n
+
1
a
\sum \frac{1}{x_i}=n+\frac{1}{a}
∑
x
i
1
=
n
+
a
1
. Find the minimal value of
∑
x
i
2
\sum x_i^2
∑
x
i
2
.
Lowest maintenance cost in a city
In a country, there are
N
{}N{}
N
cities and
N
(
N
−
1
)
N(N-1)
N
(
N
−
1
)
one-way roads: one road from
X
X{}
X
to
Y
Y{}
Y
for each ordered pair of cities
X
≠
Y
X \neq Y
X
=
Y
. Every road has a maintenance cost. For each
k
=
1
,
…
,
N
k = 1,\ldots, N
k
=
1
,
…
,
N
let's consider all the ways to select
k
k{}
k
cities and
N
−
k
N - k{}
N
−
k
roads so that from each city it is possible to get to some selected city, using only selected roads. We call such a system of cities and roads with the lowest total maintenance cost
k
k{}
k
-optimal. Prove that cities can be numbered from
1
1{}
1
to
N
N{}
N
so that for each
k
=
1
,
…
,
N
k = 1,\ldots, N
k
=
1
,
…
,
N
there is a
k
k{}
k
-optimal system of roads with the selected cities numbered
1
,
…
,
k
1,\ldots, k
1
,
…
,
k
.Proposed by V. Buslov
7
2
Hide problems
Two exsimilicenters in a trapezoid
Given a trapezoid
A
B
C
D
ABCD
A
BC
D
, in which
A
D
∥
B
C
AD \parallel BC
A
D
∥
BC
, and rays
A
B
AB
A
B
and
D
C
DC
D
C
intersect at point
G
G
G
. The common external tangents to the circles
(
A
B
C
)
,
(
A
C
D
)
(ABC), (ACD)
(
A
BC
)
,
(
A
C
D
)
intersect at point
E
E
E
. The common external tangents to circles
(
A
B
D
)
,
(
C
B
D
)
(ABD), (CBD)
(
A
B
D
)
,
(
CB
D
)
meet at
F
F
F
. Prove that the points
E
,
F
E, F
E
,
F
and
G
G
G
are collinear.
Characterisation of special polynomials
We call a polynomial
P
(
x
)
P(x)
P
(
x
)
good if the numbers
P
(
k
)
P(k)
P
(
k
)
and
P
′
(
k
)
P'(k)
P
′
(
k
)
are integers for all integers
k
k
k
. Let
P
(
x
)
P(x)
P
(
x
)
be a good polynomial of degree
d
d
d
, and let
N
d
N_d
N
d
be the product of all composite numbers not exceeding
d
d
d
. Prove that the leading coefficient of the polynomial
N
d
⋅
P
(
x
)
N_d \cdot P(x)
N
d
⋅
P
(
x
)
is integer.
5
3
Hide problems
Heaps of stones
If there are several heaps of stones on the table, it is said that there are
<
s
p
a
n
c
l
a
s
s
=
′
l
a
t
e
x
−
i
t
a
l
i
c
′
>
m
a
n
y
<
/
s
p
a
n
>
<span class='latex-italic'>many</span>
<
s
p
an
c
l
a
ss
=
′
l
a
t
e
x
−
i
t
a
l
i
c
′
>
man
y
<
/
s
p
an
>
stones on the table, if we can find
50
50
50
piles and number them with the numbers from
1
1
1
to
50
50
50
so that the first pile contains at least one stone, the second - at least two stones,..., the
50
50
50
-th has at least
50
50
50
stones. Let the table be initially contain
100
100
100
piles of
100
100
100
stones each. Find the largest
n
≤
10000
n \leq 10 000
n
≤
10000
such that after removing any
n
n
n
stones, there will still be
<
s
p
a
n
c
l
a
s
s
=
′
l
a
t
e
x
−
i
t
a
l
i
c
′
>
m
a
n
y
<
/
s
p
a
n
>
<span class='latex-italic'>many</span>
<
s
p
an
c
l
a
ss
=
′
l
a
t
e
x
−
i
t
a
l
i
c
′
>
man
y
<
/
s
p
an
>
stones left on the table.
Easy NT divisibility
Find the largest natural number
n
n
n
for which the product of the numbers
n
,
n
+
1
,
n
+
2
,
…
,
n
+
20
n, n+1, n+2, \ldots, n+20
n
,
n
+
1
,
n
+
2
,
…
,
n
+
20
is divisible by the square of one of them.
Two players want to obtain a number divisible by 2023
Initially,
10
10
10
ones are written on a blackboard. Grisha and Gleb are playing game, by taking turns; Grisha goes first. On one move Grisha squares some
5
5
5
numbers on the board. On his move, Gleb picks a few (perhaps none) numbers on the board and increases each of them by
1
1
1
. If in
10
,
000
10,000
10
,
000
moves on the board a number divisible by
2023
2023
2023
appears, Gleb wins, otherwise Grisha wins. Which of the players has a winning strategy?
6
2
Hide problems
NT bijection
Consider all
100
100
100
-digit numbers divisible by
19
19
19
. Prove that the number of such numbers not containing the digits
4
,
5
4, 5
4
,
5
, and
6
6
6
is the number of such numbers that do not contain the digits
1
,
4
1, 4
1
,
4
and
7
7
7
.
3 midpoints of edges in tetrahedron and tangent's intersection, coplanar
The plane
α
\alpha
α
intersects the edges
A
B
AB
A
B
,
B
C
BC
BC
,
C
D
CD
C
D
and
D
A
DA
D
A
of the tetrahedron
A
B
C
D
ABCD
A
BC
D
at points
X
,
Y
,
Z
X, Y, Z
X
,
Y
,
Z
and
T
T
T
, respectively. It turned out, that points
Y
Y
Y
and
T
T
T
lie on a circle
ω
\omega
ω
constructed with segment
X
Z
XZ
XZ
as the diameter. Point
P
P
P
is marked in the plane
α
\alpha
α
so that the lines
P
Y
P Y
P
Y
and
P
T
P T
PT
are tangent to the circle
ω
\omega
ω
.Prove that the midpoints of the edges are
A
B
AB
A
B
,
B
C
BC
BC
,
C
D
,
CD,
C
D
,
D
A
DA
D
A
and the point
P
P
P
lie in the same plane.
1
3
Hide problems
Two quadratics
Given are two monic quadratics
f
(
x
)
,
g
(
x
)
f(x), g(x)
f
(
x
)
,
g
(
x
)
such that
f
,
g
,
f
+
g
f, g, f+g
f
,
g
,
f
+
g
have two distinct real roots. Suppose that the difference of the roots of
f
f
f
is equal to the difference of the roots of
g
g
g
. Prove that the difference of the roots of
f
+
g
f+g
f
+
g
is not bigger than the above common difference.
Rotate triangle about circumcenter by 120 degrees
Sidelines of an acute-angled triangle
T
T
T
are colored in red, green, and blue. These lines were rotated about the circumcenter of
T
T
T
clockwise by
12
0
∘
120^\circ
12
0
∘
(we assume that the line has the same color after rotation). Prove that three points of pairs of lines of the same color are the vertices of a triangle which is congruent to
T
T
T
.
Trigonometry makes rational number
If
x
∈
R
x\in\mathbb{R}
x
∈
R
satisfy
s
i
n
sin
s
in
x
+
t
a
n
x+tan
x
+
t
an
x
∈
Q
x\in\mathbb{Q}
x
∈
Q
,
c
o
s
cos
cos
x
+
c
o
t
x+cot
x
+
co
t
x
∈
Q
x\in\mathbb{Q}
x
∈
Q
Prove that
s
i
n
sin
s
in
2
x
2x
2
x
is a root of an integral coefficient quadratic function
4
3
Hide problems
Geometric inequality with excenters
Given is a triangle
A
B
C
ABC
A
BC
and a point
X
X
X
inside its circumcircle. If
I
B
,
I
C
I_B, I_C
I
B
,
I
C
denote the
B
,
C
B, C
B
,
C
excenters, then prove that
X
B
⋅
X
C
<
X
I
B
⋅
X
I
C
XB \cdot XC <XI_B \cdot XI_C
XB
⋅
XC
<
X
I
B
⋅
X
I
C
.
Table tennis mini-tournament
There is a queue of
n
n{}
n
girls on one side of a tennis table, and a queue of
n
n{}
n
boys on the other side. Both the girls and the boys are numbered from
1
1{}
1
to
n
n{}
n
in the order they stand. The first game is played by the girl and the boy with the number
1
1{}
1
and then, after each game, the loser goes to the end of their queue, and the winner remains at the table. After a while, it turned out that each girl played exactly one game with each boy. Prove that if
n
n{}
n
is odd, then a girl and a boy with odd numbers played in the last game. Proposed by A. Gribalko
Beautiful geo finale of day 1
Let
ω
\omega
ω
be the circumcircle of triangle
A
B
C
ABC
A
BC
with
A
B
<
A
C
AB<AC
A
B
<
A
C
. Let
I
I
I
be its incenter and let
M
M
M
be the midpoint of
B
C
BC
BC
. The foot of the perpendicular from
M
M
M
to
A
I
AI
A
I
is
H
H
H
. The lines
M
H
,
B
I
,
A
B
MH, BI, AB
M
H
,
B
I
,
A
B
form a triangle
T
b
T_b
T
b
and the lines
M
H
,
C
I
,
A
C
MH, CI, AC
M
H
,
C
I
,
A
C
form a triangle
T
c
T_c
T
c
. The circumcircle of
T
b
T_b
T
b
meets
ω
\omega
ω
at
B
′
B'
B
′
and the circumcircle of
T
c
T_c
T
c
meets
ω
\omega
ω
at
C
′
C'
C
′
. Prove that
B
′
,
H
,
C
′
B', H, C'
B
′
,
H
,
C
′
are collinear.
3
1
Hide problems
Existence of a weird polynomial satisfying divisibility condition
Given are positive integers
a
,
b
a, b
a
,
b
satisfying
a
≥
2
b
a \geq 2b
a
≥
2
b
. Does there exist a polynomial
P
(
x
)
P(x)
P
(
x
)
of degree at least
1
1
1
with coefficients from the set
{
0
,
1
,
2
,
…
,
b
−
1
}
\{0, 1, 2, \ldots, b-1 \}
{
0
,
1
,
2
,
…
,
b
−
1
}
such that
P
(
b
)
∣
P
(
a
)
P(b) \mid P(a)
P
(
b
)
∣
P
(
a
)
?