MathDB
Problems
Contests
National and Regional Contests
China Contests
China Team Selection Test
2014 China Team Selection Test
2014 China Team Selection Test
Part of
China Team Selection Test
Subcontests
(6)
6
3
Hide problems
2x2 square diagonal same sum
Let
n
≥
2
n\ge 2
n
≥
2
be a positive integer. Fill up a
n
×
n
n\times n
n
×
n
table with the numbers
1
,
2
,
.
.
.
,
n
2
1,2,...,n^2
1
,
2
,
...
,
n
2
exactly once each. Two cells are termed adjacent if they have a common edge. It is known that for any two adjacent cells, the numbers they contain differ by at most
n
n
n
. Show that there exist a
2
×
2
2\times 2
2
×
2
square of adjacent cells such that the diagonally opposite pairs sum to the same number.
Difference between number of factors of different types.
Let
k
k
k
be a fixed even positive integer,
N
N
N
is the product of
k
k
k
distinct primes
p
1
,
.
.
.
,
p
k
p_1,...,p_k
p
1
,
...
,
p
k
,
a
,
b
a,b
a
,
b
are two positive integers,
a
,
b
≤
N
a,b\leq N
a
,
b
≤
N
. Denote
S
1
=
{
d
∣
S_1=\{d|
S
1
=
{
d
∣
d
∣
N
,
a
≤
d
≤
b
,
d
d|N, a\leq d\leq b, d
d
∣
N
,
a
≤
d
≤
b
,
d
has even number of prime factors
}
\}
}
,
S
2
=
{
d
∣
S_2=\{d|
S
2
=
{
d
∣
d
∣
N
,
a
≤
d
≤
b
,
d
d|N, a\leq d\leq b, d
d
∣
N
,
a
≤
d
≤
b
,
d
has odd number of prime factors
}
\}
}
, Prove:
∣
S
1
∣
−
∣
S
2
∣
≤
C
k
k
2
|S_1|-|S_2|\leq C^{\frac{k}{2}}_k
∣
S
1
∣
−
∣
S
2
∣
≤
C
k
2
k
Representations of k as product of integers is bounded
For positive integer
k
>
1
k>1
k
>
1
, let
f
(
k
)
f(k)
f
(
k
)
be the number of ways of factoring
k
k
k
into product of positive integers greater than
1
1
1
(The order of factors are not countered, for example
f
(
12
)
=
4
f(12)=4
f
(
12
)
=
4
, as
12
12
12
can be factored in these
4
4
4
ways:
12
,
2
⋅
6
,
3
⋅
4
,
2
⋅
2
⋅
3
12,2\cdot 6,3\cdot 4, 2\cdot 2\cdot 3
12
,
2
⋅
6
,
3
⋅
4
,
2
⋅
2
⋅
3
. Prove: If
n
n
n
is a positive integer greater than
1
1
1
,
p
p
p
is a prime factor of
n
n
n
, then
f
(
n
)
≤
n
p
f(n)\leq \frac{n}{p}
f
(
n
)
≤
p
n
5
3
Hide problems
Arithmetic progressions
Let
a
1
<
a
2
<
.
.
.
<
a
t
a_1<a_2<...<a_t
a
1
<
a
2
<
...
<
a
t
be
t
t
t
given positive integers where no three form an arithmetic progression. For
k
=
t
,
t
+
1
,
.
.
.
k=t,t+1,...
k
=
t
,
t
+
1
,
...
define
a
k
+
1
a_{k+1}
a
k
+
1
to be the smallest positive integer larger than
a
k
a_k
a
k
satisfying the condition that no three of
a
1
,
a
2
,
.
.
.
,
a
k
+
1
a_1,a_2,...,a_{k+1}
a
1
,
a
2
,
...
,
a
k
+
1
form an arithmetic progression. For any
x
∈
R
+
x\in\mathbb{R}^+
x
∈
R
+
define
A
(
x
)
A(x)
A
(
x
)
to be the number of terms in
{
a
i
}
i
≥
1
\{a_i\}_{i\ge 1}
{
a
i
}
i
≥
1
that are at most
x
x
x
. Show that there exist
c
>
1
c>1
c
>
1
and
K
>
0
K>0
K
>
0
such that
A
(
x
)
≥
c
x
A(x)\ge c\sqrt{x}
A
(
x
)
≥
c
x
for any
x
>
K
x>K
x
>
K
.
Simple graph with 2 disjoint cycles, cycle contain chord
Find the smallest positive constant
c
c
c
satisfying: For any simple graph
G
=
G
(
V
,
E
)
G=G(V,E)
G
=
G
(
V
,
E
)
, if
∣
E
∣
≥
c
∣
V
∣
|E|\geq c|V|
∣
E
∣
≥
c
∣
V
∣
, then
G
G
G
contains
2
2
2
cycles with no common vertex, and one of them contains a chord.Note: The cycle of graph
G
(
V
,
E
)
G(V,E)
G
(
V
,
E
)
is a set of distinct vertices
v
1
,
v
2
.
.
.
,
v
n
⊆
V
{v_1,v_2...,v_n}\subseteq V
v
1
,
v
2
...
,
v
n
⊆
V
,
v
i
v
i
+
1
∈
E
v_iv_{i+1}\in E
v
i
v
i
+
1
∈
E
for all
1
≤
i
≤
n
1\leq i\leq n
1
≤
i
≤
n
(
n
≥
3
,
v
n
+
1
=
v
1
)
(n\geq 3, v_{n+1}=v_1)
(
n
≥
3
,
v
n
+
1
=
v
1
)
; a cycle containing a chord is the cycle
v
1
,
v
2
.
.
.
,
v
n
{v_1,v_2...,v_n}
v
1
,
v
2
...
,
v
n
, such that there exist
i
,
j
,
1
<
i
−
j
<
n
−
1
i,j, 1< i-j< n-1
i
,
j
,
1
<
i
−
j
<
n
−
1
, satisfying
v
i
v
j
∈
E
v_iv_j\in E
v
i
v
j
∈
E
.
China Team Selection Test 2014 TST 3 Day 2 Q5
Let
n
n
n
be a given integer which is greater than
1
1
1
. Find the greatest constant
λ
(
n
)
\lambda(n)
λ
(
n
)
such that for any non-zero complex
z
1
,
z
2
,
⋯
,
z
n
z_1,z_2,\cdots,z_n
z
1
,
z
2
,
⋯
,
z
n
,have that \sum_{k\equal{}1}^n |z_k|^2\geq \lambda(n)\min\limits_{1\le k\le n}\{|z_{k+1}-z_k|^2\}, where
z
n
+
1
=
z
1
z_{n+1}=z_1
z
n
+
1
=
z
1
.
1
3
Hide problems
Perpendicular diagonals in cyclic quadrilateral
A
B
C
D
ABCD
A
BC
D
is a cyclic quadrilateral, with diagonals
A
C
,
B
D
AC,BD
A
C
,
B
D
perpendicular to each other. Let point
F
F
F
be on side
B
C
BC
BC
, the parallel line
E
F
EF
EF
to
A
C
AC
A
C
intersect
A
B
AB
A
B
at point
E
E
E
, line
F
G
FG
FG
parallel to
B
D
BD
B
D
intersect
C
D
CD
C
D
at
G
G
G
. Let the projection of
E
E
E
onto
C
D
CD
C
D
be
P
P
P
, projection of
F
F
F
onto
D
A
DA
D
A
be
Q
Q
Q
, projection of
G
G
G
onto
A
B
AB
A
B
be
R
R
R
. Prove that
Q
F
QF
QF
bisects
∠
P
Q
R
\angle PQR
∠
PQR
.
Number of prime factors vs prime powers
Prove that for any positive integers
k
k
k
and
N
N
N
,
(
1
N
∑
n
=
1
N
(
ω
(
n
)
)
k
)
1
k
≤
k
+
∑
q
≤
N
1
q
,
\left(\frac{1}{N}\sum\limits_{n=1}^{N}(\omega (n))^k\right)^{\frac{1}{k}}\leq k+\sum\limits_{q\leq N}\frac{1}{q},
(
N
1
n
=
1
∑
N
(
ω
(
n
)
)
k
)
k
1
≤
k
+
q
≤
N
∑
q
1
,
where
∑
q
≤
N
1
q
\sum\limits_{q\leq N}\frac{1}{q}
q
≤
N
∑
q
1
is the summation over of prime powers
q
≤
N
q\leq N
q
≤
N
(including
q
=
1
q=1
q
=
1
). Note: For integer
n
>
1
n>1
n
>
1
,
ω
(
n
)
\omega (n)
ω
(
n
)
denotes number of distinct prime factors of
n
n
n
, and
ω
(
1
)
=
0
\omega (1)=0
ω
(
1
)
=
0
.
circumcentres and orthocentres
Let the circumcenter of triangle
A
B
C
ABC
A
BC
be
O
O
O
.
H
A
H_A
H
A
is the projection of
A
A
A
onto
B
C
BC
BC
. The extension of
A
O
AO
A
O
intersects the circumcircle of
B
O
C
BOC
BOC
at
A
′
A'
A
′
. The projections of
A
′
A'
A
′
onto
A
B
,
A
C
AB, AC
A
B
,
A
C
are
D
,
E
D,E
D
,
E
, and
O
A
O_A
O
A
is the circumcentre of triangle
D
H
A
E
DH_AE
D
H
A
E
. Define
H
B
,
O
B
,
H
C
,
O
C
H_B, O_B, H_C, O_C
H
B
,
O
B
,
H
C
,
O
C
similarly. Prove:
H
A
O
A
,
H
B
O
B
,
H
C
O
C
H_AO_A, H_BO_B, H_CO_C
H
A
O
A
,
H
B
O
B
,
H
C
O
C
are concurrent
4
3
Hide problems
China Team Selection Test 2014 TST 1 Day 2 Q4
For any real numbers sequence
{
x
n
}
\{x_n\}
{
x
n
}
,suppose that
{
y
n
}
\{y_n\}
{
y
n
}
is a sequence such that:
y
1
=
x
1
,
y
n
+
1
=
x
n
+
1
−
(
∑
i
=
1
n
x
i
2
)
1
2
y_1=x_1, y_{n+1}=x_{n+1}-(\sum\limits_{i = 1}^{n} {x^2_i})^{ \frac{1}{2}}
y
1
=
x
1
,
y
n
+
1
=
x
n
+
1
−
(
i
=
1
∑
n
x
i
2
)
2
1
(
n
≥
1
)
{(n \ge 1})
(
n
≥
1
)
. Find the smallest positive number
λ
\lambda
λ
such that for any real numbers sequence
{
x
n
}
\{x_n\}
{
x
n
}
and all positive integers
m
m
m
, have
1
m
∑
i
=
1
m
x
i
2
≤
∑
i
=
1
m
λ
m
−
i
y
i
2
.
\frac{1}{m}\sum\limits_{i = 1}^{m} {x^2_i}\le\sum\limits_{i = 1}^{m} {\lambda^{m-i}y^2_i} .
m
1
i
=
1
∑
m
x
i
2
≤
i
=
1
∑
m
λ
m
−
i
y
i
2
.
(High School Affiliated to Nanjing Normal University )
Circumradius and heights
Given circle
O
O
O
with radius
R
R
R
, the inscribed triangle
A
B
C
ABC
A
BC
is an acute scalene triangle, where
A
B
AB
A
B
is the largest side.
A
H
A
,
B
H
B
,
C
H
C
AH_A, BH_B,CH_C
A
H
A
,
B
H
B
,
C
H
C
are heights on
B
C
,
C
A
,
A
B
BC,CA,AB
BC
,
C
A
,
A
B
. Let
D
D
D
be the symmetric point of
H
A
H_A
H
A
with respect to
H
B
H
C
H_BH_C
H
B
H
C
,
E
E
E
be the symmetric point of
H
B
H_B
H
B
with respect to
H
A
H
C
H_AH_C
H
A
H
C
.
P
P
P
is the intersection of
A
D
,
B
E
AD,BE
A
D
,
BE
,
H
H
H
is the orthocentre of
△
A
B
C
\triangle ABC
△
A
BC
. Prove:
O
P
⋅
O
H
OP\cdot OH
OP
⋅
O
H
is fixed, and find this value in terms of
R
R
R
.(Edited)
Sum of 2 divisors of n^2+1/2
Let
k
k
k
be a fixed odd integer,
k
>
3
k>3
k
>
3
. Prove: There exist infinitely many positive integers
n
n
n
, such that there are two positive integers
d
1
,
d
2
d_1, d_2
d
1
,
d
2
satisfying
d
1
,
d
2
d_1,d_2
d
1
,
d
2
each dividing
n
2
+
1
2
\frac{n^2+1}{2}
2
n
2
+
1
, and
d
1
+
d
2
=
n
+
k
d_1+d_2=n+k
d
1
+
d
2
=
n
+
k
.
3
3
Hide problems
China Team Selection Test 2014 TST 1 Day 1 Q3
Let the function
f
:
N
∗
→
N
∗
f:N^*\to N^*
f
:
N
∗
→
N
∗
such that (1)
(
f
(
m
)
,
f
(
n
)
)
≤
(
m
,
n
)
2014
,
∀
m
,
n
∈
N
∗
(f(m),f(n))\le (m,n)^{2014} , \forall m,n\in N^*
(
f
(
m
)
,
f
(
n
))
≤
(
m
,
n
)
2014
,
∀
m
,
n
∈
N
∗
; (2)
n
≤
f
(
n
)
≤
n
+
2014
,
∀
n
∈
N
∗
n\le f(n)\le n+2014 , \forall n\in N^*
n
≤
f
(
n
)
≤
n
+
2014
,
∀
n
∈
N
∗
Show that: there exists the positive integers
N
N
N
such that
f
(
n
)
=
n
f(n)=n
f
(
n
)
=
n
, for each integer
n
≥
N
n \ge N
n
≥
N
. (High School Affiliated to Nanjing Normal University )
Pairs of points with same distance in convex n-gon
A
A
A
is the set of points of a convex
n
n
n
-gon on a plane. The distinct pairwise distances between any
2
2
2
points in
A
A
A
arranged in descending order is
d
1
>
d
2
>
.
.
.
>
d
m
>
0
d_1>d_2>...>d_m>0
d
1
>
d
2
>
...
>
d
m
>
0
. Let the number of unordered pairs of points in
A
A
A
such that their distance is
d
i
d_i
d
i
be exactly
μ
i
\mu _i
μ
i
, for
i
=
1
,
2
,
.
.
.
,
m
i=1, 2,..., m
i
=
1
,
2
,
...
,
m
. Prove: For any positive integer
k
≤
m
k\leq m
k
≤
m
,
μ
1
+
μ
2
+
.
.
.
+
μ
k
≤
(
3
k
−
1
)
n
\mu _1+\mu _2+...+\mu _k\leq (3k-1)n
μ
1
+
μ
2
+
...
+
μ
k
≤
(
3
k
−
1
)
n
.
China Team Selection Test 2014 TST 3 Day 1 Q3
Show that there are no 2-tuples
(
x
,
y
)
(x,y)
(
x
,
y
)
of positive integers satisfying the equation
(
x
+
1
)
(
x
+
2
)
⋯
(
x
+
2014
)
=
(
y
+
1
)
(
y
+
2
)
⋯
(
y
+
4028
)
.
(x+1) (x+2)\cdots (x+2014)= (y+1) (y+2)\cdots (y+4028).
(
x
+
1
)
(
x
+
2
)
⋯
(
x
+
2014
)
=
(
y
+
1
)
(
y
+
2
)
⋯
(
y
+
4028
)
.
2
3
Hide problems
China Team Selection Test 2014 TST 1 Day 1 Q2
Let
A
A
A
be a finite set of positive numbers ,
B
=
{
a
+
b
c
+
d
∣
a
,
b
,
c
,
d
∈
A
}
B=\{\frac{a+b}{c+d} |a,b,c,d \in A \}
B
=
{
c
+
d
a
+
b
∣
a
,
b
,
c
,
d
∈
A
}
. Show that:
∣
B
∣
≥
2
∣
A
∣
2
−
1
\left | B \right | \ge 2\left | A \right |^2-1
∣
B
∣
≥
2
∣
A
∣
2
−
1
, where
∣
X
∣
|X|
∣
X
∣
be the number of elements of the finite set
X
X
X
. (High School Affiliated to Nanjing Normal University )
Relation of no., sum, product of factors of n
Given a fixed positive integer
a
≥
9
a\geq 9
a
≥
9
. Prove: There exist finitely many positive integers
n
n
n
, satisfying: (1)
τ
(
n
)
=
a
\tau (n)=a
τ
(
n
)
=
a
(2)
n
∣
ϕ
(
n
)
+
σ
(
n
)
n|\phi (n)+\sigma (n)
n
∣
ϕ
(
n
)
+
σ
(
n
)
Note: For positive integer
n
n
n
,
τ
(
n
)
\tau (n)
τ
(
n
)
is the number of positive divisors of
n
n
n
,
ϕ
(
n
)
\phi (n)
ϕ
(
n
)
is the number of positive integers
≤
n
\leq n
≤
n
and relatively prime with
n
n
n
,
σ
(
n
)
\sigma (n)
σ
(
n
)
is the sum of positive divisors of
n
n
n
.
triangle with colorued vertices on 101-gon
Let
A
1
A
2
.
.
.
A
101
A_1A_2...A_{101}
A
1
A
2
...
A
101
be a regular
101
101
101
-gon, and colour every vertex red or blue. Let
N
N
N
be the number of obtuse triangles satisfying the following: The three vertices of the triangle must be vertices of the
101
101
101
-gon, both the vertices with acute angles have the same colour, and the vertex with obtuse angle have different colour.
(
1
)
(1)
(
1
)
Find the largest possible value of
N
N
N
.
(
2
)
(2)
(
2
)
Find the number of ways to colour the vertices such that maximum
N
N
N
is acheived. (Two colourings a different if for some
A
i
A_i
A
i
the colours are different on the two colouring schemes).