CN-TST 2021

Given positive integers $m$ and $n$ . Let $a_{i,j} ( 1 \le i \le m, 1 \le j \le n)$ be non-negative real numbers, such that $$a_{i,1} \ge a_{i,2} \ge \cdots \ge a_{i,n} \text{ and } a_{1,j} \ge a_{2,j} \ge \cdots \ge a_{m,j}$$ holds for all $1 \le i \le m$ and $1 \le j \le n$ . Denote $$X_{i,j}=a_{1,j}+\cdots+a_{i-1,j}+a_{i,j}+a_{i,j-1}+\cdots+a_{i,1},$$ $$Y_{i,j}=a_{m,j}+\cdots+a_{i+1,j}+a_{i,j}+a_{i,j+1}+\cdots+a_{i,n}.$$ Prove that $$\prod_{i=1}^{m} \prod_{j=1}^{n} X_{i,j} \ge \prod_{i=1}^{m} \prod_{j=1}^{n} Y_{i,j}.$$

Given positive integers $n$ and $k$ , $n > k^2 >4.$ In a $n \times n$ grid, a $k$ -group is a set of $k$ unit squares lying in different rows and different columns. Determine the maximal possible $N$ , such that one can choose $N$ unit squares in the grid and color them, with the following condition holds: in any $k$ -group from the colored $N$ unit squares, there are two squares with the same color, and there are also two squares with different colors.

Given positive integer $n$ . Prove that for any integers $a_1,a_2,\cdots,a_n,$ at least $\lceil \tfrac{n(n-6)}{19} \rceil$ numbers from the set $\{ 1,2, \cdots, \tfrac{n(n-1)}{2} \}$ cannot be represented as $a_i-a_j (1 \le i, j \le n)$ .

Let $f(x),g(x)$ be two polynomials with integer coefficients. It is known that for infinitely many prime $p$ , there exist integer $m_p$ such that $$f(a) \equiv g(a+m_p) \pmod p$$ holds for all $a \in \mathbb{Z}.$ Prove that there exists a rational number $r$ such that $$f(x)=g(x+r).$$

Given a triangle $ABC$ , a circle $\Omega$ is tangent to $AB,AC$ at $B,C,$ respectively. Point $D$ is the midpoint of $AC$ , $O$ is the circumcenter of triangle $ABC$ . A circle $\Gamma$ passing through $A,C$ intersects the minor arc $BC$ on $\Omega$ at $P$ , and intersects $AB$ at $Q$ . It is known that the midpoint $R$ of minor arc $PQ$ satisfies that $CR \perp AB$ . Ray $PQ$ intersects line $AC$ at $L$ , $M$ is the midpoint of $AL$ , $N$ is the midpoint of $DR$ , and $X$ is the projection of $M$ onto $ON$ . Prove that the circumcircle of triangle $DNX$ passes through the center of $\Gamma$ .

Given positive integer $n$ and $r$ pairwise distinct primes $p_1,p_2,\cdots,p_r.$ Initially, there are $(n+1)^r$ numbers written on the blackboard: $p_1^{i_1}p_2^{i_2}\cdots p_r^{i_r} (0 \le i_1,i_2,\cdots,i_r \le n).$ Alice and Bob play a game by making a move by turns, with Alice going first. In Alice's round, she erases two numbers $a,b$ (not necessarily different) and write $\gcd(a,b)$ . In Bob's round, he erases two numbers $a,b$ (not necessarily different) and write $\mathrm{lcm} (a,b)$ . The game ends when only one number remains on the blackboard.

Determine the minimal possible $M$ such that Alice could guarantee the remaining number no greater than $M$ , regardless of Bob's move.

A cyclic quadrilateral $ABCD$ has circumcircle $\Gamma$ , and $AB+BC=AD+DC$ . Let $E$ be the midpoint of arc $BCD$ , and $F (\neq C)$ be the antipode of $A$ wrt $\Gamma$ . Let $I,J,K$ be the incenter of $\triangle ABC$ , the $A$ -excenter of $\triangle ABC$ , the incenter of $\triangle BCD$ , respectively. Suppose that a point $P$ satisfies $\triangle BIC \stackrel{+}{\sim} \triangle KPJ$ . Prove that $EK$ and $PF$ intersect on $\Gamma.$

Given positive integers $n,k$ , $n \ge 2$ . Find the minimum constant $c$ satisfies the following assertion: For any positive integer $m$ and a $kn$ -regular graph $G$ with $m$ vertices, one could color the vertices of $G$ with $n$ different colors, such that the number of monochrome edges is at most $cm$ .

Given positive integers $a,b,c$ which are pairwise coprime. Let $f(n)$ denotes the number of the non-negative integer solution $(x,y,z)$ to the equation $$ax+by+cz=n.$$ Prove that there exists constants $\alpha, \beta, \gamma \in \mathbb{R}$ such that for any non-negative integer $n$ , $$|f(n)- \left( \alpha n^2+ \beta n + \gamma \right) | < \frac{1}{12} \left( a+b+c \right).$$

Find all functions $f: \mathbb{Z}^+\rightarrow \mathbb{Z}^+$ such that for all positive integers $m,n$ with $m\ge n$ , $$f(m\varphi(n^3)) = f(m)\cdot \varphi(n^3).$$ Here $\varphi(n)$ denotes the number of positive integers coprime to $n$ and not exceeding $n$ .

Let $n$ be a positive integer and $a_1,a_2,\ldots a_{2n+1}$ be positive reals. For $k=1,2,\ldots ,2n+1$ , denote $b_k = \max_{0\le m\le n}\left(\frac{1}{2m+1} \sum_{i=k-m}^{k+m} a_i \right)$ , where indices are taken modulo $2n+1$ . Prove that the number of indices $k$ satisfying $b_k\ge 1$ does not exceed $2\sum_{i=1}^{2n+1} a_i$ .

Find the smallest positive real constant $a$ , such that for any three points $A,B,C$ on the unit circle, there exists an equilateral triangle $PQR$ with side length $a$ such that all of $A,B,C$ lie on the interior or boundary of $\triangle PQR$ .

Given positive integer $n \ge 5$ and a convex polygon $P$ , namely $A_1A_2...A_n$ . No diagonals of $P$ are concurrent. Proof that it is possible to choose a point inside every quadrilateral $A_iA_jA_kA_l (1\le i<j<k<l\le n)$ not on diagonals of $P$ , such that the $\tbinom{n}{4}$ points chosen are distinct, and any segment connecting these points intersect with some diagonal of P.

Given distinct positive integer $a_1,a_2,…,a_{2020}$ . For $n \ge 2021$ , $a_n$ is the smallest number different from $a_1,a_2,…,a_{n-1}$ which doesn't divide $a_{n-2020}...a_{n-2}a_{n-1}$ . Proof that every number large enough appears in the sequence.

Determine the greatest real number $C$ , such that for every positive integer $n\ge 2$ , there exists $x_1, x_2,..., x_n \in [-1,1]$ , so that $$\prod_{1\le i<j\le n}(x_i-x_j) \ge C^{\frac{n(n-1)}{2}}$$ .

Proof that $$\sum_{m=1}^n5^{\omega (m)} \le \sum_{k=1}^n\lfloor \frac{n}{k} \rfloor \tau (k)^2 \le \sum_{m=1}^n5^{\Omega (m)} .$$

Determine all $f:R\rightarrow R$ such that $$f(xf(y)+y^3)=yf(x)+f(y)^3$$

Proof that there exist constant $\lambda$ , so that for any positive integer $m(\ge 2)$ , and any lattice triangle $T$ in the Cartesian coordinate plane, if $T$ contains exactly one $m$ -lattice point in its interior(not containing boundary), then $T$ has area $\le \lambda m^3$ . PS. lattice triangles are triangles whose vertex are lattice points; $m$ -lattice points are lattice points whose both coordinates are divisible by $m$ .

Let $n(\ge2)$ be a positive integer. Find the minimum $m$ , so that there exists $x_{ij}(1\le i ,j\le n)$ satisfying: (1)For every $1\le i ,j\le n, x_{ij}=max\{x_{i1},x_{i2},...,x_{ij}\}$ or $x_{ij}=max\{x_{1j},x_{2j},...,x_{ij}\}.$ (2)For every $1\le i \le n$ , there are at most $m$ indices $k$ with $x_{ik}=max\{x_{i1},x_{i2},...,x_{ik}\}.$ (3)For every $1\le j \le n$ , there are at most $m$ indices $k$ with $x_{kj}=max\{x_{1j},x_{2j},...,x_{kj}\}.$

Let triangle $ABC(AB<AC)$ with incenter $I$ circumscribed in $\odot O$ . Let $M,N$ be midpoint of arc $\widehat{BAC}$ and $\widehat{BC}$ , respectively. $D$ lies on $\odot O$ so that $AD//BC$ , and $E$ is tangency point of $A$ -excircle of $\bigtriangleup ABC$ . Point $F$ is in $\bigtriangleup ABC$ so that $FI//BC$ and $\angle BAF=\angle EAC$ . Extend $NF$ to meet $\odot O$ at $G$ , and extend $AG$ to meet line $IF$ at L. Let line $AF$ and $DI$ meet at $K$ . Proof that $ML\bot NK$ .

Find all positive integer $n(\ge 2)$ and rational $\beta \in (0,1)$ satisfying the following: There exist positive integers $a_1,a_2,...,a_n$ , such that for any set $I \subseteq \{1,2,...,n\}$ which contains at least two elements, $$S(\sum_{i\in I}a_i)=\beta \sum_{i\in I}S(a_i).$$ where $S(n)$ denotes sum of digits of decimal representation of $n$ .

Suppose $x_1,x_2,...,x_{60}\in [-1,1]$ , find the maximum of $$\sum_{i=1}^{60}x_i^2(x_{i+1}-x_{i-1}),$$ where $x_{i+60}=x_i$ .

Find the smallest real $\alpha$ , such that for any convex polygon $P$ with area $1$ , there exist a point $M$ in the plane, such that the area of convex hull of $P\cup Q$ is at most $\alpha$ , where $Q$ denotes the image of $P$ under central symmetry with respect to $M$ .

Let $n(\ge 2)$ be an integer. $2n^2$ contestants participate in a Chinese chess competition, where any two contestant play exactly once. There may be draws. It is known that (1)If A wins B and B wins C, then A wins C. (2)there are at most $\frac{n^3}{16}$ draws. Proof that it is possible to choose $n^2$ contestants and label them $P_{ij}(1\le i,j\le n)$ , so that for any $i,j,i',j'\in \{1,2,...,n\}$ , if $i<i'$ , then $P_{ij}$ wins $P_{i'j'}$ .