MathDB
Problems
Contests
National and Regional Contests
China Contests
China National Olympiad
2016 China National Olympiad
2016 China National Olympiad
Part of
China National Olympiad
Subcontests
(6)
6
1
Hide problems
Paths of fixed length in complete directed graph
Let
G
G
G
be a complete directed graph with
100
100
100
vertices such that for any two vertices
x
,
y
x,y
x
,
y
one can find a directed path from
x
x
x
to
y
y
y
. a) Show that for any such
G
G
G
, one can find a
m
m
m
such that for any two vertices
x
,
y
x,y
x
,
y
one can find a directed path of length
m
m
m
from
x
x
x
to
y
y
y
(Vertices can be repeated in the path)b) For any graph
G
G
G
with the properties above, define
m
(
G
)
m(G)
m
(
G
)
to be smallest possible
m
m
m
as defined in part a). Find the minimim value of
m
(
G
)
m(G)
m
(
G
)
over all such possible
G
G
G
's.
5
1
Hide problems
Existence of square with properties
Let
A
B
C
D
ABCD
A
BC
D
be a convex quadrilateral. Show that there exists a square
A
′
B
′
C
′
D
′
A'B'C'D'
A
′
B
′
C
′
D
′
(Vertices maybe ordered clockwise or counter-clockwise) such that
A
≠
A
′
,
B
≠
B
′
,
C
≠
C
′
,
D
≠
D
′
A \not = A', B \not = B', C \not = C', D \not = D'
A
=
A
′
,
B
=
B
′
,
C
=
C
′
,
D
=
D
′
and
A
A
′
,
B
B
′
,
C
C
′
,
D
D
′
AA',BB',CC',DD'
A
A
′
,
B
B
′
,
C
C
′
,
D
D
′
are all concurrent.
4
1
Hide problems
Set where no two elements divide each other
Let
n
≥
2
n \geq 2
n
≥
2
be a positive integer and define
k
k
k
to be the number of primes
≤
n
\leq n
≤
n
. Let
A
A
A
be a subset of
S
=
{
2
,
.
.
.
,
n
}
S = \{2,...,n\}
S
=
{
2
,
...
,
n
}
such that
∣
A
∣
≤
k
|A| \leq k
∣
A
∣
≤
k
and no two elements in
A
A
A
divide each other. Show that one can find a set
B
B
B
such that
∣
B
∣
=
k
|B| = k
∣
B
∣
=
k
,
A
⊆
B
⊆
S
A \subseteq B \subseteq S
A
⊆
B
⊆
S
and no two elements in
B
B
B
divide each other.
2
1
Hide problems
Concylic implies concyclic
In
△
A
E
F
\triangle AEF
△
A
EF
, let
B
B
B
and
D
D
D
be on segments
A
E
AE
A
E
and
A
F
AF
A
F
respectively, and let
E
D
ED
E
D
and
F
B
FB
FB
intersect at
C
C
C
. Define
K
,
L
,
M
,
N
K,L,M,N
K
,
L
,
M
,
N
on segments
A
B
,
B
C
,
C
D
,
D
A
AB,BC,CD,DA
A
B
,
BC
,
C
D
,
D
A
such that
A
K
K
B
=
A
D
B
C
\frac{AK}{KB}=\frac{AD}{BC}
K
B
A
K
=
BC
A
D
and its cyclic equivalents. Let the incircle of
△
A
E
F
\triangle AEF
△
A
EF
touch
A
E
,
A
F
AE,AF
A
E
,
A
F
at
S
,
T
S,T
S
,
T
respectively; let the incircle of
△
C
E
F
\triangle CEF
△
CEF
touch
C
E
,
C
F
CE,CF
CE
,
CF
at
U
,
V
U,V
U
,
V
respectively. Prove that
K
,
L
,
M
,
N
K,L,M,N
K
,
L
,
M
,
N
concyclic implies
S
,
T
,
U
,
V
S,T,U,V
S
,
T
,
U
,
V
concyclic.
3
1
Hide problems
Polynomial interpolating sequence mod p has small degree
Let
p
p
p
be an odd prime and
a
1
,
a
2
,
.
.
.
,
a
p
a_1, a_2,...,a_p
a
1
,
a
2
,
...
,
a
p
be integers. Prove that the following two conditions are equivalent:1) There exists a polynomial
P
(
x
)
P(x)
P
(
x
)
with degree
≤
p
−
1
2
\leq \frac{p-1}{2}
≤
2
p
−
1
such that
P
(
i
)
≡
a
i
(
m
o
d
p
)
P(i) \equiv a_i \pmod p
P
(
i
)
≡
a
i
(
mod
p
)
for all
1
≤
i
≤
p
1 \leq i \leq p
1
≤
i
≤
p
2) For any natural
d
≤
p
−
1
2
d \leq \frac{p-1}{2}
d
≤
2
p
−
1
,
∑
i
=
1
p
(
a
i
+
d
−
a
i
)
2
≡
0
(
m
o
d
p
)
\sum_{i=1}^p (a_{i+d} - a_i )^2 \equiv 0 \pmod p
i
=
1
∑
p
(
a
i
+
d
−
a
i
)
2
≡
0
(
mod
p
)
where indices are taken
(
m
o
d
p
)
\pmod p
(
mod
p
)
1
1
Hide problems
China Mathematical Olympiad 2016 Q1
Let
a
1
,
a
2
,
⋯
,
a
31
;
b
1
,
b
2
,
⋯
,
b
31
a_1,a_2,\cdots, a_{31} ;b_1,b_2, \cdots, b_{31}
a
1
,
a
2
,
⋯
,
a
31
;
b
1
,
b
2
,
⋯
,
b
31
be positive integers such that
a
1
<
a
2
<
⋯
<
a
31
≤
2015
a_1< a_2<\cdots< a_{31}\leq2015
a
1
<
a
2
<
⋯
<
a
31
≤
2015
,
b
1
<
b
2
<
⋯
<
b
31
≤
2015
b_1< b_2<\cdots<b_{31}\leq2015
b
1
<
b
2
<
⋯
<
b
31
≤
2015
and
a
1
+
a
2
+
⋯
+
a
31
=
b
1
+
b
2
+
⋯
+
b
31
.
a_1+a_2+\cdots+a_{31}=b_1+b_2+\cdots+b_{31}.
a
1
+
a
2
+
⋯
+
a
31
=
b
1
+
b
2
+
⋯
+
b
31
.
Find the maximum value of
S
=
∣
a
1
−
b
1
∣
+
∣
a
2
−
b
2
∣
+
⋯
+
∣
a
31
−
b
31
∣
.
S=|a_1-b_1|+|a_2-b_2|+\cdots+|a_{31}-b_{31}|.
S
=
∣
a
1
−
b
1
∣
+
∣
a
2
−
b
2
∣
+
⋯
+
∣
a
31
−
b
31
∣.