MathDB
Problems
Contests
National and Regional Contests
Russia Contests
Saint Petersburg Mathematical Olympiad
2009 Saint Petersburg Mathematical Olympiad
2009 Saint Petersburg Mathematical Olympiad
Part of
Saint Petersburg Mathematical Olympiad
Subcontests
(7)
6
2
Hide problems
Color graph
Some cities in country are connected by road, and from every city goes
≥
2008
\geq 2008
≥
2008
roads. Every road is colored in one of two colors. Prove, that exists cycle without self-intersections ,where
≥
504
\geq 504
≥
504
roads and all roads are same color.
Periodic sequence
(
x
n
)
(x_n)
(
x
n
)
is sequence, such that
x
n
+
2
=
∣
x
n
+
1
∣
−
x
n
x_{n+2}=|x_{n+1}|-x_n
x
n
+
2
=
∣
x
n
+
1
∣
−
x
n
. Prove, that it is periodic.
3
2
Hide problems
Minimal Road
Streets of Moscow are some circles (rings) with common center
O
O
O
and some straight lines from center
O
O
O
to external ring. Point
A
,
B
A,B
A
,
B
- two crossroads on external ring. Three friends want to move from
A
A
A
to
B
B
B
. Dima goes by external ring, Kostya goes from
A
A
A
to
O
O
O
then to
B
B
B
. Sergey says, that there is another way, that is shortest. Prove, that he is wrong.
Square trinomials
f
(
x
)
,
g
(
x
)
,
h
(
x
)
f(x),g(x),h(x)
f
(
x
)
,
g
(
x
)
,
h
(
x
)
are square trinomials with discriminant, that equals
2
2
2
. And
f
(
x
)
+
g
(
x
)
,
f
(
x
)
+
h
(
x
)
,
g
(
x
)
+
h
(
x
)
f(x)+g(x),f(x)+h(x),g(x)+h(x)
f
(
x
)
+
g
(
x
)
,
f
(
x
)
+
h
(
x
)
,
g
(
x
)
+
h
(
x
)
are square trinomials with discriminant, that equals
1
1
1
. Prove,that
f
(
x
)
+
g
(
x
)
+
h
(
x
)
f(x)+g(x)+h(x)
f
(
x
)
+
g
(
x
)
+
h
(
x
)
has not roots.
7
3
Hide problems
Special sequence
f
(
x
)
=
x
2
+
x
f(x)=x^2+x
f
(
x
)
=
x
2
+
x
b
1
,
.
.
.
,
b
10000
>
0
b_1,...,b_{10000}>0
b
1
,
...
,
b
10000
>
0
and
∣
b
n
+
1
−
f
(
b
n
)
∣
≤
1
1000
|b_{n+1}-f(b_n)|\leq \frac{1}{1000}
∣
b
n
+
1
−
f
(
b
n
)
∣
≤
1000
1
for
n
=
1
,
.
.
.
,
9999
n=1,...,9999
n
=
1
,
...
,
9999
Prove, that there is such
a
1
>
0
a_1>0
a
1
>
0
that
a
n
+
1
=
f
(
a
n
)
;
n
=
1
,
.
.
.
,
9999
a_{n+1}=f(a_n);n=1,...,9999
a
n
+
1
=
f
(
a
n
)
;
n
=
1
,
...
,
9999
and
∣
a
n
−
b
n
∣
<
1
100
|a_n-b_n|<\frac{1}{100}
∣
a
n
−
b
n
∣
<
100
1
Another geometry
Points
Y
,
X
Y,X
Y
,
X
lies on
A
B
,
B
C
AB,BC
A
B
,
BC
of
△
A
B
C
\triangle ABC
△
A
BC
and
X
,
Y
,
A
,
C
X,Y,A,C
X
,
Y
,
A
,
C
are concyclic.
A
X
AX
A
X
and
C
Y
CY
C
Y
intersect in
O
O
O
. Points
M
,
N
M,N
M
,
N
are midpoints of
A
C
AC
A
C
and
X
Y
XY
X
Y
. Prove, that
B
O
BO
BO
is tangent to circumcircle of
△
M
O
N
\triangle MON
△
MON
Discriminants
Discriminants of square trinomials
f
(
x
)
,
g
(
x
)
,
h
(
x
)
,
f
(
x
)
+
g
(
x
)
,
f
(
x
)
+
h
(
x
)
,
g
(
x
)
+
h
(
x
)
f(x),g(x),h(x),f(x)+g(x),f(x)+h(x),g(x)+h(x)
f
(
x
)
,
g
(
x
)
,
h
(
x
)
,
f
(
x
)
+
g
(
x
)
,
f
(
x
)
+
h
(
x
)
,
g
(
x
)
+
h
(
x
)
equals
1
1
1
. Prove that
f
(
x
)
+
h
(
x
)
+
g
(
x
)
≡
0
f(x)+h(x)+g(x) \equiv 0
f
(
x
)
+
h
(
x
)
+
g
(
x
)
≡
0
5
3
Hide problems
Geometry with circles
O
O
O
-circumcenter of
A
B
C
D
ABCD
A
BC
D
.
A
C
AC
A
C
and
B
D
BD
B
D
intersect in
E
E
E
,
A
D
AD
A
D
and
B
C
BC
BC
in
F
F
F
.
X
,
Y
X,Y
X
,
Y
- midpoints of
A
D
AD
A
D
and
B
C
BC
BC
.
O
1
O_1
O
1
-circumcenter of
E
X
Y
EXY
EX
Y
. Prove that
O
F
∥
O
1
E
OF \parallel O_1E
OF
∥
O
1
E
Chess rooks
Call a set of some cells in infinite chess field as board. Set of rooks on the board call as awesome if no one rook can beat another, but every empty cell is under rook attack. There are awesome set with
2008
2008
2008
rooks and with
2010
2010
2010
rooks. Prove, that there are awesome set with
2009
2009
2009
rooks.
Altitudes and sides
A
B
C
ABC
A
BC
is acute-angled triangle.
A
A
1
,
B
B
1
,
C
C
1
AA_1,BB_1,CC_1
A
A
1
,
B
B
1
,
C
C
1
are altitudes.
X
,
Y
X,Y
X
,
Y
- midpoints of
A
C
1
,
A
1
C
AC_1,A_1C
A
C
1
,
A
1
C
.
X
Y
=
B
B
1
XY=BB_1
X
Y
=
B
B
1
. Prove that one side of
A
B
C
ABC
A
BC
in
2
\sqrt{2}
2
greater than other side.
4
2
Hide problems
Cells in square
From
2008
×
2008
2008 \times 2008
2008
×
2008
square we remove one corner cell
1
×
1
1 \times 1
1
×
1
. Is number of ways to divide this figure to corners from
3
3
3
cells odd or even ?
Orthocenter
Points
A
1
A_1
A
1
and
C
1
C_1
C
1
are on
B
C
BC
BC
and
A
B
AB
A
B
of acute-angled triangle
A
B
C
ABC
A
BC
.
A
A
1
AA_1
A
A
1
and
C
C
1
CC_1
C
C
1
intersect in
K
K
K
. Circumcircles of
A
A
1
B
,
C
C
1
B
AA_1B,CC_1B
A
A
1
B
,
C
C
1
B
intersect in
P
P
P
- incenter of
A
K
C
AKC
A
K
C
. Prove, that
P
P
P
- orthocenter of
A
B
C
ABC
A
BC
2
3
Hide problems
LCM difference
[
x
,
y
]
−
[
x
,
z
]
=
y
−
z
[x,y]-[x,z]=y-z
[
x
,
y
]
−
[
x
,
z
]
=
y
−
z
and
x
≠
y
≠
z
≠
x
x \neq y \neq z \neq x
x
=
y
=
z
=
x
Prove, that
x
∣
y
,
x
∣
z
x|y,x|z
x
∣
y
,
x
∣
z
Quadrilateral
A
B
C
D
ABCD
A
BC
D
is convex quadrilateral with
A
B
=
C
D
AB=CD
A
B
=
C
D
.
A
C
AC
A
C
and
B
D
BD
B
D
intersect in
O
O
O
.
X
,
Y
,
Z
,
T
X,Y,Z,T
X
,
Y
,
Z
,
T
are midpoints of
B
C
,
A
D
,
A
C
,
B
D
BC,AD,AC,BD
BC
,
A
D
,
A
C
,
B
D
. Prove, that circumcenter of
O
Z
T
OZT
OZT
lies on
X
Y
XY
X
Y
.
Choice of problem
There are
40
40
40
members of jury, that want to choose problem for contest. There are list with
30
30
30
problems. They want to find such problem, that can be solved at least half members , but not all. Every member solved
26
26
26
problems, and every two members solved different sets of problems. Prove, that they can find problem for contest.
1
3
Hide problems
Sets of values.
f
(
x
)
=
a
x
2
+
b
x
+
c
;
a
,
b
,
c
f(x)=ax^2+bx+c;a,b,c
f
(
x
)
=
a
x
2
+
b
x
+
c
;
a
,
b
,
c
are reals.
M
=
{
f
(
2
n
)
∣
n
is integer
}
,
N
=
{
f
(
2
n
+
1
)
∣
n
is integer
}
M=\{f(2n)|n \text{ is integer}\},N=\{f(2n+1)|n \text{ is integer}\}
M
=
{
f
(
2
n
)
∣
n
is integer
}
,
N
=
{
f
(
2
n
+
1
)
∣
n
is integer
}
Prove that
M
=
N
M=N
M
=
N
or M \cap N = \O
GCD of degrees
x
,
y
x,y
x
,
y
are naturals.
G
C
M
(
x
7
,
y
4
)
∗
G
C
M
(
x
8
,
y
5
)
=
x
y
GCM(x^7,y^4)*GCM(x^8,y^5)=xy
GCM
(
x
7
,
y
4
)
∗
GCM
(
x
8
,
y
5
)
=
x
y
Prove that
x
y
xy
x
y
is cube
Division
b
,
c
b,c
b
,
c
are naturals.
b
∣
c
+
1
b|c+1
b
∣
c
+
1
Prove that exists such natural
x
,
y
,
z
x,y,z
x
,
y
,
z
that
x
+
y
=
b
z
,
x
y
=
c
z
x+y=bz,xy=cz
x
+
y
=
b
z
,
x
y
=
cz