MathDB
Problems
Contests
National and Regional Contests
Korea Contests
Korea Summer Program Practice Test
2016 Korea Summer Program Practice Test
2016 Korea Summer Program Practice Test
Part of
Korea Summer Program Practice Test
Subcontests
(7)
8
1
Hide problems
Nonintersecting perfect matching with reasonable length
There are distinct points
A
1
,
A
2
,
…
,
A
2
n
A_1, A_2, \dots, A_{2n}
A
1
,
A
2
,
…
,
A
2
n
with no three collinear. Prove that one can relabel the points with the labels
B
1
,
…
,
B
2
n
B_1, \dots, B_{2n}
B
1
,
…
,
B
2
n
so that for each
1
≤
i
<
j
≤
n
1 \le i < j \le n
1
≤
i
<
j
≤
n
the segments
B
2
i
−
1
B
2
i
B_{2i-1} B_{2i}
B
2
i
−
1
B
2
i
and
B
2
j
−
1
B
2
j
B_{2j-1} B_{2j}
B
2
j
−
1
B
2
j
do not intersect and the following inequality holds.
B
1
B
2
+
B
3
B
4
+
⋯
+
B
2
n
−
1
B
2
n
≥
2
π
(
A
1
A
2
+
A
3
A
4
+
⋯
+
A
2
n
−
1
A
2
n
)
B_1 B_2 + B_3 B_4 + \dots + B_{2n-1} B_{2n} \ge \frac{2}{\pi} (A_1 A_2 + A_3 A_4 + \dots + A_{2n-1} A_{2n})
B
1
B
2
+
B
3
B
4
+
⋯
+
B
2
n
−
1
B
2
n
≥
π
2
(
A
1
A
2
+
A
3
A
4
+
⋯
+
A
2
n
−
1
A
2
n
)
7
1
Hide problems
Infinite sequence with parallelograms
A infinite sequence
{
a
n
}
n
≥
0
\{ a_n \}_{n \ge 0}
{
a
n
}
n
≥
0
of real numbers satisfy
a
n
≥
n
2
a_n \ge n^2
a
n
≥
n
2
. Suppose that for each
i
,
j
≥
0
i, j \ge 0
i
,
j
≥
0
there exist
k
,
l
k, l
k
,
l
with
(
i
,
j
)
≠
(
k
,
l
)
(i,j) \neq (k,l)
(
i
,
j
)
=
(
k
,
l
)
,
l
−
k
=
j
−
i
l - k = j - i
l
−
k
=
j
−
i
, and
a
l
−
a
k
=
a
j
−
a
i
a_l - a_k = a_j - a_i
a
l
−
a
k
=
a
j
−
a
i
. Prove that
a
n
≥
(
n
+
2016
)
2
a_n \ge (n + 2016)^2
a
n
≥
(
n
+
2016
)
2
for some
n
n
n
.
6
1
Hide problems
Partitioning into groups of equal sum
A finite set
S
S
S
of positive integers is given. Show that there is a positive integer
N
N
N
dependent only on
S
S
S
, such that any
x
1
,
…
,
x
m
∈
S
x_1, \dots, x_m \in S
x
1
,
…
,
x
m
∈
S
whose sum is a multiple of
N
N
N
, can be partitioned into groups each of whose sum is exactly
N
N
N
. (The numbers
x
1
,
…
,
x
m
x_1, \dots, x_m
x
1
,
…
,
x
m
need not be distinct.)
5
1
Hide problems
Maximal number of sets
Find the maximal possible
n
n
n
, where
A
1
,
…
,
A
n
⊆
{
1
,
2
,
…
,
2016
}
A_1, \dots, A_n \subseteq \{1, 2, \dots, 2016\}
A
1
,
…
,
A
n
⊆
{
1
,
2
,
…
,
2016
}
satisfy the following properties. - For each
1
≤
i
≤
n
1 \le i \le n
1
≤
i
≤
n
,
∣
A
i
∣
=
4
\lvert A_i \rvert = 4
∣
A
i
∣
=
4
. - For each
1
≤
i
<
j
≤
n
1 \le i < j \le n
1
≤
i
<
j
≤
n
,
∣
A
i
∩
A
j
∣
\lvert A_i \cap A_j \rvert
∣
A
i
∩
A
j
∣
is even.
4
1
Hide problems
Inequality on the number of local extrema and saddles
Two integers
0
<
k
<
n
0 < k < n
0
<
k
<
n
and distinct real numbers
a
1
,
a
2
,
…
,
a
n
a_1, a_2, \dots ,a_n
a
1
,
a
2
,
…
,
a
n
are given. Define the sets as the following, where all indices are modulo
n
n
n
. \begin{align*} A &= \{ 1 \le i \le n : a_i > a_{i-k}, a_{i-1}, a_{i+1}, a_{i+k} \text{ or } a_i < a_{i-k}, a_{i-1}, a_{i+1}, a_{i+k} \} \\ B &= \{ 1 \le i \le n : a_i > a_{i-k}, a_{i+k} \text{ and } a_i < a_{i-1}, a_{i+1} \} \\ C &= \{ 1 \le i \le n ; a_i > a_{i-1}, a_{i+1} \text{ and } a_i < a_{i-k}, a_{i+k} \} \end{align*} Prove that
∣
A
∣
≥
∣
B
∣
+
∣
C
∣
\lvert A \rvert \ge \lvert B \rvert + \lvert C \rvert
∣
A
∣
≥
∣
B
∣
+
∣
C
∣
.
2
1
Hide problems
Collinearity of three points
Let the incircle of triangle
A
B
C
ABC
A
BC
meet the sides
B
C
BC
BC
,
C
A
CA
C
A
,
A
B
AB
A
B
at
D
D
D
,
E
E
E
,
F
F
F
, and let the
A
A
A
-excircle meet the lines
B
C
BC
BC
,
C
A
CA
C
A
,
A
B
AB
A
B
at
P
P
P
,
Q
Q
Q
,
R
R
R
. Let the line passing through
A
A
A
and perpendicular to
B
C
BC
BC
meet the lines
E
F
EF
EF
,
Q
R
QR
QR
at
K
K
K
,
L
L
L
. Let the intersection of
L
D
LD
L
D
and
E
F
EF
EF
be
S
S
S
, and the intersection of
K
P
KP
K
P
and
Q
R
QR
QR
be
T
T
T
. Prove that
A
A
A
,
S
S
S
,
T
T
T
are collinear.
1
1
Hide problems
Iterative system of equations
Find all real numbers
x
1
,
…
,
x
2016
x_1, \dots, x_{2016}
x
1
,
…
,
x
2016
that satisfy the following equation for each
1
≤
i
≤
2016
1 \le i \le 2016
1
≤
i
≤
2016
. (Here
x
2017
=
x
1
x_{2017} = x_1
x
2017
=
x
1
.)
x
i
2
+
x
i
−
1
=
x
i
+
1
x_i^2 + x_i - 1 = x_{i+1}
x
i
2
+
x
i
−
1
=
x
i
+
1