MathDB
Problems
Contests
International Contests
Tuymaada Olympiad
2023 Tuymaada Olympiad
2023 Tuymaada Olympiad
Part of
Tuymaada Olympiad
Subcontests
(8)
5
2
Hide problems
Graph numbering
A graph contains
p
p
p
vertices numbered from
1
1
1
to
p
p
p
, and
q
q
q
edges numbered from
p
+
1
p + 1
p
+
1
to
p
+
q
p + q
p
+
q
. It turned out that for each edge the sum of the numbers of its ends and of the edge itself equals the same number
s
s
s
. It is also known that the numbers of edges starting in all vertices are equal. Prove that
s
=
1
2
(
4
p
+
q
+
3
)
.
s = \dfrac{1}{2} (4p+q+3).
s
=
2
1
(
4
p
+
q
+
3
)
.
small ship sails on a polynomial determined coordinate
A small ship sails on an infinite coordinate sea. At the moment
t
t
t
the ship is at the point with coordinates
(
f
(
t
)
,
g
(
t
)
)
(f(t), g(t))
(
f
(
t
)
,
g
(
t
))
, where
f
f
f
and
g
g
g
are two polynomials of third degree. Yesterday at
14
:
00
14:00
14
:
00
the ship was at the same point as at
13
:
00
13:00
13
:
00
, and at
20
:
00
20:00
20
:
00
, it was at the same point as at
19
:
00
19:00
19
:
00
. Prove that the ship sails along a straight line.
6
2
Hide problems
Euclidean Step
An
<
s
p
a
n
c
l
a
s
s
=
′
l
a
t
e
x
−
i
t
a
l
i
c
′
>
E
u
c
l
i
d
e
a
n
s
t
e
p
<
/
s
p
a
n
>
<span class='latex-italic'>Euclidean step</span>
<
s
p
an
c
l
a
ss
=
′
l
a
t
e
x
−
i
t
a
l
i
c
′
>
E
u
c
l
i
d
e
an
s
t
e
p
<
/
s
p
an
>
transforms a pair
(
a
,
b
)
(a, b)
(
a
,
b
)
of positive integers,
a
>
b
a > b
a
>
b
, to the pair
(
b
,
r
)
(b, r)
(
b
,
r
)
, where
r
r
r
is the remainder when a is divided by
b
b
b
. Let us call the
<
s
p
a
n
c
l
a
s
s
=
′
l
a
t
e
x
−
i
t
a
l
i
c
′
>
c
o
m
p
l
e
x
i
t
y
<
/
s
p
a
n
>
<span class='latex-italic'>complexity</span>
<
s
p
an
c
l
a
ss
=
′
l
a
t
e
x
−
i
t
a
l
i
c
′
>
co
m
pl
e
x
i
t
y
<
/
s
p
an
>
of a pair
(
a
,
b
)
(a, b)
(
a
,
b
)
the number of Euclidean steps needed to transform it to a pair of the form
(
s
,
0
)
(s, 0)
(
s
,
0
)
. Prove that if
a
d
−
b
c
=
1
ad - bc = 1
a
d
−
b
c
=
1
, then the complexities of
(
a
,
b
)
(a, b)
(
a
,
b
)
and
(
c
,
d
)
(c, d)
(
c
,
d
)
differ at most by
2
2
2
.
Inequality on a plane
In the plane
n
n
n
segments with lengths
a
1
,
a
2
,
…
,
a
n
a_1, a_2, \dots , a_n
a
1
,
a
2
,
…
,
a
n
are drawn. Every ray beginning at the point
O
O
O
meets at least one of the segments. Let
h
i
h_i
h
i
be the distance from
O
O
O
to the
i
i
i
-th segment (not the line!) Prove the inequality
a
1
h
1
+
a
2
h
2
+
…
+
a
i
h
i
⩾
2
π
.
\frac{a_1}{h_1}+\frac{a_2}{h_2} + \ldots + \frac{a_i}{h_i} \geqslant 2 \pi.
h
1
a
1
+
h
2
a
2
+
…
+
h
i
a
i
⩾
2
π
.
7
2
Hide problems
People exchange places
3
n
3n
3
n
people forming
n
n
n
families of a mother, a father and a child, stand in a circle. Every two neighbours can exchange places except the case when a parent exchanges places with his/her child (this is forbidden). For what
n
n
n
is it possible to obtain every arrangement of those people by such exchanges? The arrangements differing by a circular shift are considered distinct.
Sliding Hexagonal Pieces
Hexagonal pieces numbered by positive integers are placed on the cells of a hexagonal board with side
n
n
n
. Two adjacent cells are left empty, and thanks to it some pieces can be moved. Two pieces with common sides exchanged places (see an example in the attachment 2). Prove that if
n
≥
3
n \ge 3
n
≥
3
the second arrangement cannot be obtained from the first one by moving pieceNote. Moving a piece a requires two adjacent empty cells. For instance, if they are on the right of a (attachment 1, left figure), a can be moved right till it touches an angle (attachment 1, middle figure), and then it can be moved upward right or downward right (attachment 1, right figure)
1
2
Hide problems
3-variable inequality for variables in [0;1]
Prove that for
a
,
b
,
c
∈
[
0
;
1
]
a, b, c \in [0;1]
a
,
b
,
c
∈
[
0
;
1
]
,
(
1
−
a
)
(
1
+
a
b
)
(
1
+
a
c
)
(
1
−
a
b
c
)
≤
(
1
+
a
)
(
1
−
a
b
)
(
1
−
a
c
)
(
1
+
a
b
c
)
.
(1-a)(1+ab)(1+ac)(1-abc) \leq (1+a)(1-ab)(1-ac)(1+abc).
(
1
−
a
)
(
1
+
ab
)
(
1
+
a
c
)
(
1
−
ab
c
)
≤
(
1
+
a
)
(
1
−
ab
)
(
1
−
a
c
)
(
1
+
ab
c
)
.
Infinite Spiral of integers
The numbers
1
,
2
,
3
,
…
1, 2, 3, \ldots
1
,
2
,
3
,
…
are arranged in a spiral in the vertices of an infinite square grid (see figure). Then in the centre of each square the sum of the numbers in its vertices is placed. Prove that for each positive integer n the centres of the squares contain infinitely many multiples of
n
n
n
.
3
2
Hide problems
Two angles summing to 180 degrees
Point
L
L
L
inside triangle
A
B
C
ABC
A
BC
is such that
C
L
=
A
B
CL = AB
C
L
=
A
B
and
∠
B
A
C
+
∠
B
L
C
=
18
0
∘
\angle BAC + \angle BLC = 180^{\circ}
∠
B
A
C
+
∠
B
L
C
=
18
0
∘
. Point
K
K
K
on the side
A
C
AC
A
C
is such that
K
L
∥
B
C
KL \parallel BC
K
L
∥
BC
. Prove that
A
B
=
B
K
AB = BK
A
B
=
B
K
Inequality with cubic roots
Prove that for every positive integer
n
≥
2
n \geq 2
n
≥
2
,
∑
1
≤
i
≤
n
i
n
+
1
3
n
≤
∑
1
≤
i
≤
n
−
1
i
n
3
n
−
1
.
\frac{\sum_{1\leq i \leq n} \sqrt[3]{\frac{i}{n+1}}}{n} \leq \frac{\sum_{1\leq i \leq n-1} \sqrt[3]{\frac{i}{n}}}{n-1}.
n
∑
1
≤
i
≤
n
3
n
+
1
i
≤
n
−
1
∑
1
≤
i
≤
n
−
1
3
n
i
.
4
2
Hide problems
Game involving stones on piles
Two players play a game. They have
n
>
2
n > 2
n
>
2
piles containing
n
10
+
1
n^{10}+1
n
10
+
1
stones each. A move consists of removing all the piles but one and dividing the remaining pile into
n
n
n
nonempty piles. The player that cannot move loses. Who has a winning strategy, the player that moves first or his adversary?
Circles (OCD) touching a fixed circle
Two points
A
A
A
and
B
B
B
and line
ℓ
\ell
ℓ
are fixed in the plane so that
ℓ
\ell
ℓ
is not perpendicular to
A
B
AB
A
B
and does not intersect the segment
A
B
AB
A
B
. We consider all circles with a centre
O
O
O
not lying on
ℓ
\ell
ℓ
, passing through
A
A
A
and
B
B
B
and meeting
ℓ
\ell
ℓ
at some points
C
C
C
and
D
D
D
. Prove that all the circumcircles of triangles
O
C
D
OCD
OC
D
touch a fixed circle.
2
2
Hide problems
Magic trick on flipping a binary string
Serge and Tanya want to show Masha a magic trick. Serge leaves the room. Masha writes down a sequence
(
a
1
,
a
2
,
…
,
a
n
)
(a_1, a_2, \ldots , a_n)
(
a
1
,
a
2
,
…
,
a
n
)
, where all
a
k
a_k
a
k
equal
0
0
0
or
1
1
1
. After that Tanya writes down a sequence
(
b
1
,
b
2
,
…
,
b
n
)
(b_1, b_2, \ldots , b_n)
(
b
1
,
b
2
,
…
,
b
n
)
, where all
b
k
b_k
b
k
also equal
0
0
0
or
1
1
1
. Then Masha either does nothing or says “Mutabor” and replaces both sequences: her own sequence by
(
a
n
,
a
n
−
1
,
…
,
a
1
)
(a_n, a_{n-1}, \ldots , a_1)
(
a
n
,
a
n
−
1
,
…
,
a
1
)
, and Tanya’s sequence by
(
1
−
b
n
,
1
−
b
n
−
1
,
…
,
1
−
b
1
)
(1 - b_n, 1 - b_{n-1}, \ldots , 1 - b_1)
(
1
−
b
n
,
1
−
b
n
−
1
,
…
,
1
−
b
1
)
. Masha’s sequence is covered by a napkin, and Serge is invited to the room. Serge should look at Tanya’s sequence and tell the sequence covered by the napkin. For what
n
n
n
Serge and Tanya can prepare and show such a trick? Serge does not have to determine whether the word “Mutabor” has been pronounced.
Weird identity for a graph
In a graph with
n
n
n
vertices every two vertices are connected by a unique path. For each two vertices
u
u
u
and
v
v
v
, let
d
(
u
,
v
)
d(u, v)
d
(
u
,
v
)
denote the distance between
u
u
u
and
v
v
v
, i.e. the number of edges in the path connecting these two vertices, and
deg
(
u
)
\deg(u)
de
g
(
u
)
denote the degree of a vertex
u
u
u
. Let
W
W
W
be the sum of pairwise distances between the vertices, and
D
D
D
the sum of weighted pairwise distances:
∑
{
u
,
v
}
(
deg
(
u
)
+
deg
(
v
)
)
d
(
u
,
v
)
\sum_{\{u, v\}}(\deg(u)+\deg(v))d(u, v)
∑
{
u
,
v
}
(
de
g
(
u
)
+
de
g
(
v
))
d
(
u
,
v
)
. Prove that
D
=
4
W
−
n
(
n
−
1
)
D=4W-n(n-1)
D
=
4
W
−
n
(
n
−
1
)
.
8
2
Hide problems
Locus of circumcentres
Circle
ω
\omega
ω
lies inside the circle
Ω
\Omega
Ω
and touches it internally at point
P
P
P
. Point
S
S
S
is taken on
ω
\omega
ω
and the tangent to
ω
\omega
ω
is drawn through it. This tangent meets
Ω
\Omega
Ω
at points
A
A
A
and
B
B
B
. Let
I
I
I
be the centre of
ω
\omega
ω
. Find the locus of circumcentres of triangles
A
I
B
AIB
A
I
B
.
Fractions in (0,1) with bounded denominators
Given is a positive integer
n
n
n
. Let
A
A
A
be the set of points
x
∈
(
0
;
1
)
x \in (0;1)
x
∈
(
0
;
1
)
such that
∣
x
−
p
q
∣
>
1
n
3
|x-\frac{p} {q}|>\frac{1}{n^3}
∣
x
−
q
p
∣
>
n
3
1
for each rational fraction
p
q
\frac{p} {q}
q
p
with denominator
q
≤
n
2
q \leq n^2
q
≤
n
2
. Prove that
A
A
A
is a union of intervals with total length not exceeding
100
n
\frac{100}{n}
n
100
.Proposed by Fedor Petrov