MathDB
Problems
Contests
National and Regional Contests
China Contests
China Team Selection Test
2023 China Team Selection Test
2023 China Team Selection Test
Part of
China Team Selection Test
Subcontests
(24)
P23
1
Hide problems
Many Lattice Points
Given a prime
p
p
p
and a real number
λ
∈
(
0
,
1
)
\lambda \in (0,1)
λ
∈
(
0
,
1
)
. Let
s
s
s
and
t
t
t
be positive integers such that
s
⩽
t
<
λ
p
12
s \leqslant t < \frac{\lambda p}{12}
s
⩽
t
<
12
λ
p
.
S
S
S
and
T
T
T
are sets of
s
s
s
and
t
t
t
consecutive positive integers respectively, which satisfy
∣
{
(
x
,
y
)
∈
S
×
T
:
k
x
≡
y
(
m
o
d
p
)
}
∣
⩾
1
+
λ
s
.
\left| \left\{ (x,y) \in S \times T : kx \equiv y \pmod p \right\}\right| \geqslant 1 + \lambda s.
∣
{
(
x
,
y
)
∈
S
×
T
:
k
x
≡
y
(
mod
p
)
}
∣
⩾
1
+
λ
s
.
Prove that there exists integers
a
a
a
and
b
b
b
that
1
⩽
a
⩽
1
λ
1 \leqslant a \leqslant \frac{1}{ \lambda}
1
⩽
a
⩽
λ
1
,
∣
b
∣
⩽
t
λ
s
\left| b \right| \leqslant \frac{t}{\lambda s}
∣
b
∣
⩽
λ
s
t
and
k
a
≡
b
(
m
o
d
p
)
ka \equiv b \pmod p
ka
≡
b
(
mod
p
)
.
P20
1
Hide problems
Eventually Periodic Residues of Polynomial Indicate Rational Coefficients
Let
a
,
b
,
d
a,b,d
a
,
b
,
d
be integers such that
∣
a
∣
⩾
2
\left|a\right| \geqslant 2
∣
a
∣
⩾
2
,
d
⩾
0
d \geqslant 0
d
⩾
0
and
b
⩾
(
∣
a
∣
+
1
)
d
+
1
b \geqslant \left( \left|a\right| + 1\right)^{d + 1}
b
⩾
(
∣
a
∣
+
1
)
d
+
1
. For a real coefficient polynomial
f
f
f
of degree
d
d
d
and integer
n
n
n
, let
r
n
r_n
r
n
denote the residue of
[
f
(
n
)
⋅
a
n
]
\left[ f(n) \cdot a^n \right]
[
f
(
n
)
⋅
a
n
]
mod
b
b
b
. If
{
r
n
}
\left \{ r_n \right \}
{
r
n
}
is eventually periodic, prove that all the coefficients of
f
f
f
are rational.
P24
1
Hide problems
All Black Cells
Let
n
n
n
be a positive integer. Initially, a
2
n
×
2
n
2n \times 2n
2
n
×
2
n
grid has
k
k
k
black cells and the rest white cells. The following two operations are allowed : (1) If a
2
×
2
2\times 2
2
×
2
square has exactly three black cells, the fourth is changed to a black cell; (2) If there are exactly two black cells in a
2
×
2
2 \times 2
2
×
2
square, the black cells are changed to white and white to black. Find the smallest positive integer
k
k
k
such that for any configuration of the
2
n
×
2
n
2n \times 2n
2
n
×
2
n
grid with
k
k
k
black cells, all cells can be black after a finite number of operations.
P21
1
Hide problems
Inequality Problem
Given integer
n
≥
2
n\geq 2
n
≥
2
. Find the minimum value of
λ
\lambda {}
λ
, satisfy that for any real numbers
a
1
a_1
a
1
,
a
2
a_2
a
2
,
⋯
\cdots
⋯
,
a
n
{a_n}
a
n
and
b
{b}
b
,
λ
∑
i
=
1
n
∣
a
i
−
b
∣
+
n
∣
∑
i
=
1
n
a
i
∣
⩾
∑
i
=
1
n
∣
a
i
∣
.
\lambda\sum\limits_{i=1}^n\sqrt{|a_i-b|}+\sqrt{n\left|\sum\limits_{i=1}^na_i\right|}\geqslant\sum\limits_{i=1}^n\sqrt{|a_i|}.
λ
i
=
1
∑
n
∣
a
i
−
b
∣
+
n
i
=
1
∑
n
a
i
⩾
i
=
1
∑
n
∣
a
i
∣
.
P22
1
Hide problems
Functional equation
Find all functions
f
:
Z
→
Z
f:\mathbb {Z}\to\mathbb Z
f
:
Z
→
Z
, satisfy that for any integer
a
{a}
a
,
b
{b}
b
,
c
{c}
c
,
2
f
(
a
2
+
b
2
+
c
2
)
−
2
f
(
a
b
+
b
c
+
c
a
)
=
f
(
a
−
b
)
2
+
f
(
b
−
c
)
2
+
f
(
c
−
a
)
2
2f(a^2+b^2+c^2)-2f(ab+bc+ca)=f(a-b)^2+f(b-c)^2+f(c-a)^2
2
f
(
a
2
+
b
2
+
c
2
)
−
2
f
(
ab
+
b
c
+
c
a
)
=
f
(
a
−
b
)
2
+
f
(
b
−
c
)
2
+
f
(
c
−
a
)
2
P19
1
Hide problems
orz orz orz orz orz Geometry IV, and also orz Haozhe
Let
A
,
B
A,B
A
,
B
be two fixed points on the unit circle
ω
\omega
ω
, satisfying
2
<
A
B
<
2
\sqrt{2} < AB < 2
2
<
A
B
<
2
. Let
P
P
P
be a point that can move on the unit circle, and it can move to anywhere on the unit circle satisfying
△
A
B
P
\triangle ABP
△
A
BP
is acute and
A
P
>
A
B
>
B
P
AP>AB>BP
A
P
>
A
B
>
BP
. Let
H
H
H
be the orthocenter of
△
A
B
P
\triangle ABP
△
A
BP
and
S
S
S
be a point on the minor arc
A
P
AP
A
P
satisfying
S
H
=
A
H
SH=AH
S
H
=
A
H
. Let
T
T
T
be a point on the minor arc
A
B
AB
A
B
satisfying
T
B
∣
∣
A
P
TB || AP
TB
∣∣
A
P
. Let
S
T
∩
B
P
=
Q
ST\cap BP = Q
ST
∩
BP
=
Q
. Show that (recall
P
P
P
varies) the circle with diameter
H
Q
HQ
H
Q
passes through a fixed point.
P18
1
Hide problems
Another difficult grid problem in China TST
Find the greatest constant
λ
\lambda
λ
such that for any doubly stochastic matrix of order 100, we can pick
150
150
150
entries such that if the other
9850
9850
9850
entries were replaced by
0
0
0
, the sum of entries in each row and each column is at least
λ
\lambda
λ
.Note: A doubly stochastic matrix of order
n
n
n
is a
n
×
n
n\times n
n
×
n
matrix, all entries are nonnegative reals, and the sum of entries in each row and column is equal to 1.
P16
1
Hide problems
Orz Orz Orz Orz Orz Geometry III, and also orz Haozhe
Let
Γ
,
Γ
1
,
Γ
2
\Gamma, \Gamma_1, \Gamma_2
Γ
,
Γ
1
,
Γ
2
be mutually tangent circles. The three circles are also tangent to a line
l
l
l
. Let
Γ
,
Γ
1
\Gamma, \Gamma_1
Γ
,
Γ
1
be tangent to each other at
B
1
B_1
B
1
,
Γ
,
Γ
2
\Gamma, \Gamma_2
Γ
,
Γ
2
be tangent to each other at
B
2
B_2
B
2
,
Γ
1
,
Γ
2
\Gamma_1, \Gamma_2
Γ
1
,
Γ
2
be tangent to each other at
C
C
C
.
Γ
,
Γ
1
,
Γ
2
\Gamma, \Gamma_1, \Gamma_2
Γ
,
Γ
1
,
Γ
2
are tangent to
l
l
l
at
A
,
A
1
,
A
2
A, A_1, A_2
A
,
A
1
,
A
2
respectively, where
A
A
A
is between
A
1
,
A
2
A_1,A_2
A
1
,
A
2
. Let
D
1
=
A
1
C
∩
A
2
B
2
,
D
2
=
A
2
C
∩
A
1
B
1
D_1 = A_1C \cap A_2B_2, D_2 = A_2C \cap A_1B_1
D
1
=
A
1
C
∩
A
2
B
2
,
D
2
=
A
2
C
∩
A
1
B
1
. Prove that
D
1
D
2
D_1D_2
D
1
D
2
is parallel to
l
l
l
.
P17
1
Hide problems
2023 China TST Problem 17
Whether there are integers
a
1
a_1
a
1
,
a
2
a_2
a
2
,
⋯
\cdots
⋯
, that are different from each other, satisfying: (1) For
∀
k
∈
N
+
\forall k\in\mathbb N_+
∀
k
∈
N
+
,
a
k
2
>
0
a_{k^2}>0
a
k
2
>
0
and
a
k
2
+
k
<
0
a_{k^2+k}<0
a
k
2
+
k
<
0
; (2) For
∀
n
∈
N
+
\forall n\in\mathbb N_+
∀
n
∈
N
+
,
∣
a
n
+
1
−
a
n
∣
⩽
2023
n
\left| a_{n+1}-a_n\right|\leqslant 2023\sqrt n
∣
a
n
+
1
−
a
n
∣
⩽
2023
n
?
P15
1
Hide problems
Orz Orz Orz Orz Orz Geometry II, and also orz i3435.
For a convex quadrilateral
A
B
C
D
ABCD
A
BC
D
, call a point in the interior of
A
B
C
D
ABCD
A
BC
D
balanced, if(1)
P
P
P
is not on
A
C
,
B
D
AC,BD
A
C
,
B
D
(2) Let
A
P
,
B
P
,
C
P
,
D
P
AP,BP,CP,DP
A
P
,
BP
,
CP
,
D
P
intersect the boundaries of
A
B
C
D
ABCD
A
BC
D
at
A
′
,
B
′
,
C
′
,
D
′
A', B', C', D'
A
′
,
B
′
,
C
′
,
D
′
, respectively, then
A
P
⋅
P
A
′
=
B
P
⋅
P
B
′
=
C
P
⋅
P
C
′
=
D
P
⋅
P
D
′
AP \cdot PA' = BP \cdot PB' = CP \cdot PC' = DP \cdot PD'
A
P
⋅
P
A
′
=
BP
⋅
P
B
′
=
CP
⋅
P
C
′
=
D
P
⋅
P
D
′
Find the maximum possible number of balanced points.
P14
1
Hide problems
Finally an inequality
For any nonempty, finite set
B
B
B
and real
x
x
x
, define
d
B
(
x
)
=
min
b
∈
B
∣
x
−
b
∣
d_B(x) = \min_{b\in B} |x-b|
d
B
(
x
)
=
b
∈
B
min
∣
x
−
b
∣
(1) Given positive integer
m
m
m
. Find the smallest real number
λ
\lambda
λ
(possibly depending on
m
m
m
) such that for any positive integer
n
n
n
and any reals
x
1
,
⋯
,
x
n
∈
[
0
,
1
]
x_1,\cdots,x_n \in [0,1]
x
1
,
⋯
,
x
n
∈
[
0
,
1
]
, there exists an
m
m
m
-element set
B
B
B
of real numbers satisfying
d
B
(
x
1
)
+
⋯
+
d
B
(
x
n
)
≤
λ
n
d_B(x_1)+\cdots+d_B(x_n) \le \lambda n
d
B
(
x
1
)
+
⋯
+
d
B
(
x
n
)
≤
λn
(2) Given positive integer
m
m
m
and positive real
ϵ
\epsilon
ϵ
. Prove that there exists a positive integer
n
n
n
and nonnegative reals
x
1
,
⋯
,
x
n
x_1,\cdots,x_n
x
1
,
⋯
,
x
n
, satisfying for any
m
m
m
-element set
B
B
B
of real numbers, we have
d
B
(
x
1
)
+
⋯
+
d
B
(
x
n
)
>
(
1
−
ϵ
)
(
x
1
+
⋯
+
x
n
)
d_B(x_1)+\cdots+d_B(x_n) > (1-\epsilon)(x_1+\cdots+x_n)
d
B
(
x
1
)
+
⋯
+
d
B
(
x
n
)
>
(
1
−
ϵ
)
(
x
1
+
⋯
+
x
n
)
P13
1
Hide problems
2023 China TST Problem 13
Does there exists a positive irrational number
x
,
{x},
x
,
such that there are at most finite positive integers
n
,
{n},
n
,
satisfy that for any integer
1
≤
k
≤
n
,
1\leq k\leq n,
1
≤
k
≤
n
,
{
k
x
}
≥
1
n
+
1
?
\{kx\}\geq\frac 1{n+1}?
{
k
x
}
≥
n
+
1
1
?
P12
1
Hide problems
Lower bound on circumference while upper bound on area
Prove that there exists some positive real number
λ
\lambda
λ
such that for any
D
>
1
∈
R
D_{>1}\in\mathbb{R}
D
>
1
∈
R
, one can always find an acute triangle
△
A
B
C
\triangle ABC
△
A
BC
in the Cartesian plane such that [*]
A
,
B
,
C
A, B, C
A
,
B
,
C
lie on lattice points; [*]
A
B
,
B
C
,
C
A
>
D
AB, BC, CA>D
A
B
,
BC
,
C
A
>
D
; [*]
S
△
A
B
C
<
3
4
D
2
+
λ
⋅
D
4
/
5
S_{\triangle ABC}<\frac{\sqrt 3}{4}D^2+\lambda\cdot D^{4/5}
S
△
A
BC
<
4
3
D
2
+
λ
⋅
D
4/5
.
P10
1
Hide problems
combinatorics problem
The set of nonempty integers
A
A
A
is said to be "elegant" if it is for any
a
∈
A
,
a\in A,
a
∈
A
,
1
≤
k
≤
2023
,
1\leq k\leq 2023,
1
≤
k
≤
2023
,
∣
{
b
∈
A
:
⌊
b
3
k
⌋
=
⌊
a
3
k
⌋
}
∣
=
2
k
.
\left| \left\{ b\in A:\left\lfloor\frac b{3^k}\right\rfloor =\left\lfloor\frac a{3^k}\right\rfloor\right\}\right| =2^k.
{
b
∈
A
:
⌊
3
k
b
⌋
=
⌊
3
k
a
⌋
}
=
2
k
.
Prove that if the intersection of the integer set
S
S
S
and any "elegant" set is not empty
,
,
,
then
S
S
S
contains an "elegant" set.
P11
1
Hide problems
2023 China TST Problem 11
Let
n
∈
N
+
.
n\in\mathbb N_+.
n
∈
N
+
.
For
1
≤
i
,
j
,
k
≤
n
,
a
i
j
k
∈
{
−
1
,
1
}
.
1\leq i,j,k\leq n,a_{ijk}\in\{ -1,1\} .
1
≤
i
,
j
,
k
≤
n
,
a
ijk
∈
{
−
1
,
1
}
.
Prove that:
∃
x
1
,
x
2
,
⋯
,
x
n
,
y
1
,
y
2
,
⋯
,
y
n
,
z
1
,
z
2
,
⋯
,
z
n
∈
{
−
1
,
1
}
,
\exists x_1,x_2,\cdots ,x_n,y_1,y_2,\cdots ,y_n,z_1,z_2,\cdots ,z_n\in \{-1,1\} ,
∃
x
1
,
x
2
,
⋯
,
x
n
,
y
1
,
y
2
,
⋯
,
y
n
,
z
1
,
z
2
,
⋯
,
z
n
∈
{
−
1
,
1
}
,
satisfy
∣
∑
i
=
1
n
∑
j
=
1
n
∑
k
=
1
n
a
i
j
k
x
i
y
j
z
k
∣
>
n
2
3
.
\left| \sum\limits_{i=1}^n\sum\limits_{j=1}^n\sum\limits_{k=1}^na_{ijk}x_iy_jz_k\right| >\frac {n^2}3.
i
=
1
∑
n
j
=
1
∑
n
k
=
1
∑
n
a
ijk
x
i
y
j
z
k
>
3
n
2
.
Created by Yu Deng
P8
1
Hide problems
Finding out 3 circles
In non-isosceles acute
△
A
B
C
{}{\triangle ABC}
△
A
BC
,
A
P
AP
A
P
,
B
Q
BQ
BQ
,
C
R
CR
CR
is the height of the triangle.
A
1
A_1
A
1
is the midpoint of
B
C
BC
BC
,
A
A
1
AA_1
A
A
1
intersects
Q
R
QR
QR
at
K
K
K
,
Q
R
QR
QR
intersects a straight line that crosses
A
{A}
A
and is parallel to
B
C
BC
BC
at point
D
{D}
D
, the line connecting the midpoint of
A
H
AH
A
H
and
K
{K}
K
intersects
D
A
1
DA_1
D
A
1
at
A
2
A_2
A
2
. Similarly define
B
2
B_2
B
2
,
C
2
C_2
C
2
.
△
A
2
B
2
C
2
{}\triangle A_2B_2C_2
△
A
2
B
2
C
2
is known to be non-degenerate, and its circumscribed circle is
ω
\omega
ω
. Prove that: there are circles
⊙
A
′
\odot A'
⊙
A
′
,
⊙
B
′
\odot B'
⊙
B
′
,
⊙
C
′
\odot C'
⊙
C
′
tangent to and INSIDE
ω
\omega
ω
satisfying: (1)
⊙
A
′
\odot A'
⊙
A
′
is tangent to
A
B
AB
A
B
and
A
C
AC
A
C
,
⊙
B
′
\odot B'
⊙
B
′
is tangent to
B
C
BC
BC
and
B
A
BA
B
A
, and
⊙
C
′
\odot C'
⊙
C
′
is tangent to
C
A
CA
C
A
and
C
B
CB
CB
. (2)
A
′
A'
A
′
,
B
′
B'
B
′
,
C
C
C
' are different and collinear. Created by Sihui Zhang
P7
1
Hide problems
2023 China TST Problem 7
Given the integer
n
≥
2
n\geq 2
n
≥
2
and a integer
a
{a}
a
, which is coprime with
n
{n}
n
. A country has
n
{n}
n
islands
D
1
D_1
D
1
,
D
2
D_2
D
2
,
⋯
\cdots
⋯
,
D
n
D_n
D
n
. For any
1
≤
i
≠
j
≤
n
1\leq i\neq j\leq n
1
≤
i
=
j
≤
n
, there is a one-way ferry
D
i
D_i
D
i
to
D
j
D_j
D
j
if and only if
i
j
≡
i
a
(
m
o
d
n
)
ij\equiv ia\pmod n
ij
≡
ia
(
mod
n
)
. A tourist can initially fly to any of the islands, and then he can only take a one-way ferry. What is the maximum number of islands he can visit?Created by Zhenhua Qu
P9
1
Hide problems
2023 China TST Problem 9
Find the largest positive integer
m
m
m
which makes it possible to color several cells of a
70
×
70
70\times 70
70
×
70
table red such that [*] There are no two red cells satisfying: the two rows in which they are have the same number of red cells, while the two columns in which they are also have the same number of red cells; [*] There are two rows with exactly
m
m
m
red cells each.
P5
1
Hide problems
A geometry (combinatorics) problem that is not orz
Let
△
A
B
C
\triangle ABC
△
A
BC
be a triangle, and let
P
1
,
⋯
,
P
n
P_1,\cdots,P_n
P
1
,
⋯
,
P
n
be points inside where no three given points are collinear. Prove that we can partition
△
A
B
C
\triangle ABC
△
A
BC
into
2
n
+
1
2n+1
2
n
+
1
triangles such that their vertices are among
A
,
B
,
C
,
P
1
,
⋯
,
P
n
A,B,C,P_1,\cdots,P_n
A
,
B
,
C
,
P
1
,
⋯
,
P
n
, and at least
n
+
n
+
1
n+\sqrt{n}+1
n
+
n
+
1
of them contain at least one of
A
,
B
,
C
A,B,C
A
,
B
,
C
.
P3
1
Hide problems
Very interesting NT
(1) Let
a
,
b
a,b
a
,
b
be coprime positive integers. Prove that there exists constants
λ
\lambda
λ
and
β
\beta
β
such that for all integers
m
m
m
,
∣
∑
k
=
1
m
−
1
{
a
k
m
}
{
b
k
m
}
−
λ
m
∣
≤
β
\left| \sum\limits_{k=1}^{m-1} \left\{ \frac{ak}{m} \right\}\left\{ \frac{bk}{m} \right\} - \lambda m \right| \le \beta
k
=
1
∑
m
−
1
{
m
ak
}
{
m
bk
}
−
λm
≤
β
(2) Prove that there exists
N
N
N
such that for all
p
>
N
p>N
p
>
N
(where
p
p
p
is a prime number), and any positive integers
a
,
b
,
c
a,b,c
a
,
b
,
c
positive integers satisfying
p
∤
(
a
+
b
)
(
b
+
c
)
(
c
+
a
)
p\nmid (a+b)(b+c)(c+a)
p
∤
(
a
+
b
)
(
b
+
c
)
(
c
+
a
)
, there are at least
⌊
p
12
⌋
\lfloor \frac{p}{12} \rfloor
⌊
12
p
⌋
solutions
k
∈
{
1
,
⋯
,
p
−
1
}
k\in \{1,\cdots,p-1\}
k
∈
{
1
,
⋯
,
p
−
1
}
such that
{
a
k
p
}
+
{
b
k
p
}
+
{
c
k
p
}
≤
1
\left\{\frac{ak}{p}\right\} + \left\{\frac{bk}{p}\right\} + \left\{\frac{ck}{p}\right\} \le 1
{
p
ak
}
+
{
p
bk
}
+
{
p
c
k
}
≤
1
P2
1
Hide problems
2023 China TST, Day 1, Problem 2
n
n
n
people attend a party. There are no more than
n
n
n
pairs of friends among them. Two people shake hands if and only if they have at least
1
1
1
common friend. Given integer
m
≥
3
m\ge 3
m
≥
3
such that
n
≤
m
3
n\leq m^3
n
≤
m
3
. Prove that there exists a person
A
A
A
, the number of people that shake hands with
A
A
A
is no more than
m
−
1
m-1
m
−
1
times of the number of
A
A
A
‘S friends.
P6
1
Hide problems
2023 China TST Problem 6
Prove that: (1) In the complex plane, each line (except for the real axis) that crosses the origin has at most one point
z
{z}
z
, satisfy
1
+
z
23
z
64
∈
R
.
\frac {1+z^{23}}{z^{64}}\in\mathbb R.
z
64
1
+
z
23
∈
R
.
(2) For any non-zero complex number
a
{a}
a
and any real number
θ
\theta
θ
, the equation
1
+
z
23
+
a
z
64
=
0
1+z^{23}+az^{64}=0
1
+
z
23
+
a
z
64
=
0
has roots in
S
θ
=
{
z
∈
C
∣
Re
(
z
e
−
i
θ
)
⩾
∣
z
∣
cos
π
20
}
.
S_{\theta}=\left\{ z\in\mathbb C\mid\operatorname{Re}(ze^{-i\theta })\geqslant |z|\cos\frac{\pi}{20}\right\}.
S
θ
=
{
z
∈
C
∣
Re
(
z
e
−
i
θ
)
⩾
∣
z
∣
cos
20
π
}
.
Proposed by Yijun Yao
P1
1
Hide problems
A Special Cyclic Polygon
Given an integer
n
⩾
2
n \geqslant 2
n
⩾
2
. Suppose there is a point
P
P
P
inside a convex cyclic
2
n
2n
2
n
-gon
A
1
…
A
2
n
A_1 \ldots A_{2n}
A
1
…
A
2
n
satisfying
∠
P
A
1
A
2
=
∠
P
A
2
A
3
=
…
=
∠
P
A
2
n
A
1
,
\angle PA_1A_2 = \angle PA_2A_3 = \ldots = \angle PA_{2n}A_1,
∠
P
A
1
A
2
=
∠
P
A
2
A
3
=
…
=
∠
P
A
2
n
A
1
,
prove that
∏
i
=
1
n
∣
A
2
i
−
1
A
2
i
∣
=
∏
i
=
1
n
∣
A
2
i
A
2
i
+
1
∣
,
\prod_{i=1}^{n} \left|A_{2i - 1}A_{2i} \right| = \prod_{i=1}^{n} \left|A_{2i}A_{2i+1} \right|,
i
=
1
∏
n
∣
A
2
i
−
1
A
2
i
∣
=
i
=
1
∏
n
∣
A
2
i
A
2
i
+
1
∣
,
where
A
2
n
+
1
=
A
1
A_{2n + 1} = A_1
A
2
n
+
1
=
A
1
.
P4
1
Hide problems
2023 China TST Problem 4
Given
m
,
n
∈
N
+
,
m,n\in\mathbb N_+,
m
,
n
∈
N
+
,
define
S
(
m
,
n
)
=
{
(
a
,
b
)
∈
N
+
2
∣
1
≤
a
≤
m
,
1
≤
b
≤
n
,
gcd
(
a
,
b
)
=
1
}
.
S(m,n)=\left\{(a,b)\in\mathbb N_+^2\mid 1\leq a\leq m,1\leq b\leq n,\gcd (a,b)=1\right\}.
S
(
m
,
n
)
=
{
(
a
,
b
)
∈
N
+
2
∣
1
≤
a
≤
m
,
1
≤
b
≤
n
,
g
cd
(
a
,
b
)
=
1
}
.
Prove that: for
∀
d
,
r
∈
N
+
,
\forall d,r\in\mathbb N_+,
∀
d
,
r
∈
N
+
,
there exists
m
,
n
∈
N
+
,
m
,
n
≥
d
m,n\in\mathbb N_+,m,n\geq d
m
,
n
∈
N
+
,
m
,
n
≥
d
and
∣
S
(
m
,
n
)
∣
≡
r
(
m
o
d
d
)
.
\left|S(m,n)\right|\equiv r\pmod d.
∣
S
(
m
,
n
)
∣
≡
r
(
mod
d
)
.