China National Team Selection Test

Let $O$ be the center of circle $C$, $a_n$ is the length of a regular $n$-gon $A_1{A}_2\cdots A_n$ inscribed in $\odot O$. Then $a_6=10>9$, $a_7<10\times \frac{2\pi }{7}<10\times \frac{2\times 3.15}{7}<9$.

(1) Let $A_1{A}_2\cdots A_6$ be a regular 6-gon inscribed in $\odot O$, then $A_i{A}_{i+1}=a_6>9$. So we can choose a point $B_i$ in $\widehat{A_i{A}_{i+1}}$ such that $B_i{A}_{i+1}>9$. Then $\angle B_{i}O{A}_{i+1}>\frac{2\pi }{7}$ ($A_7=A_1$), and $$\angle A_{i}O{B}_i=\angle A_{i}O{A}_{i+1}-\angle B_{i}O{A}_{i+1}<\frac{2\pi }{6}-\frac{2\pi }{7}<\frac{2\pi }{7}.$$ It follows that $A_i{B}_i<9$ ($i=1,2,\dots ,6$).

In each of $\widehat{A_1{B}_1},\widehat{A_2{B}_2},\widehat{A_3{B}_3}$, choose 11 points, and in each of $\widehat{A_4{B}_4},\widehat{A_5{B}_5},\widehat{A_6{B}_6}$, choose 10 points. We obtain a set $M$ which has 63 points on the circle $C$. It is easy to see for $M$ the value of $S$ is $S_0$, where $$\begin{array}{rl}{S}_0& =\left(\genfrac{}{}{0ex}{}{3}{3}\right)\times 11^3+\left(\genfrac{}{}{0ex}{}{3}{2}\right)\cdot \left(\genfrac{}{}{0ex}{}{3}{1}\right)\times 11^2\times 10\\ & +\left(\genfrac{}{}{0ex}{}{3}{1}\right)\cdot \left(\genfrac{}{}{0ex}{}{3}{2}\right)\times 11\times 10^2+\left(\genfrac{}{}{0ex}{}{3}{3}\right)\times 10^3\\ & =23121.\end{array}$$ So the maximum value of $S$ is not less than $S_0$.

(2) We prove that the maximum is $S_0$. We need three lemmas.

Lemma 1 For $P$ on circle $C$, we call the arc $\widehat{APB}$ “an arc of $P$”, if $P$ is the midpoint of arc $\widehat{APB}$, and $\angle AOB=\frac{4\pi }{7}$. Now for every given $n$ points on circle $C$, there is a point $P$, such that there are $\lfloor \frac{n+5}{6}\rfloor$ points of the given $n$ points on the “arc of $P$”.

Proof: Let $A$ be one of the given $n$ points, and an “arc of $A$” be $\widehat{A_{1}A{A}_6}$. Now suppose $A_2,A_3,\dots ,A_5$ are on the arc $\widehat{A_1{A}_6}$ (not including $A$), and $A_1{A}_2=A_2{A}_3=\cdots =A_5{A}_6$ (see the figure). So $\angle A_{i}O{A}_{i+1}=\frac{2\pi }{7},i=1,2,\dots ,5$.



If there is a point $P_i$ (of the given $n$ points) on $\widehat{A_i{A}_{i+1}}$, then all the points (of the given $n$ points) on $\widehat{A_i{A}_{i+1}}$ are on “an arc of $P_i$”. So the given $n$ points are on $6$ “arcs of $P_i$” (including “arc of $A$”). This shows that there are $\lfloor \frac{n-1}{6}\rfloor +1=\lfloor \frac{n+5}{6}\rfloor$ points of the given points on an “arc of $P_i$”, where $P_i$ is one of the given $n$ points.

Lemma 2 Take the arc $\widehat{A_{1}B{A}_6}$ arbitrary on the circle $C$ with radius 10, where $\widehat{A_{1}B{A}_6}$ is $\frac{5}{7}$ of the perimeter. Then take any $5m+r$ points on the arc $\widehat{A_{1}B{A}_6}$ ($m,r$ are non-negative integers and $0\le r<5$). Prove that number of lines from the given points whose lengths are more than 9 is at most $$10m^2+4rm+\frac{1}{2}r(r-1).$$

Proof: Divide $\overrightarrow{A_{1}B{A}_6}$ in five equal parts, where the corresponding points are $A_2,A_3,A_4,A_5$ (see the figure), then the length of $\overrightarrow{A_i{A}_{i+1}}$ is exactly $\frac{1}{7}$ of the perimeter ($i=1,2,3,4,5$), and the distance of any two points is not more than $a_7<9$. Suppose there are $m_i$ given points on the arc $\overrightarrow{A_i{A}_{i+1}}$, then the number of lines from the given points whose lengths are more than 9 is at most $$l=\sum _{1\le i<j\le 5}{m}_i{m}_j,\stackrel{◯}{1}$$ where $$m_1+m_2+\cdots +m_5=5m+r.\stackrel{◯}{2}$$ Since there are finitely many non-negative integer groups ($m_1,m_2,m_3,m_4,m_5$), the maximum value of $l$ exists. Now we prove that when the maximum is attained the inequality $$|m_i-m_j|\le 1,(1\le i<j\le 5),$$ must hold.

In fact, if there exist $i,j$ ($1\le i<j\le 5$) such that $|m_i-m_j|\ge 2$ when the maximum is attained, we can suppose $m_1-m_2\ge 2$. Then let $$m_1^{\prime }=m_1-1,m_2^{\prime }=m_2+1,m^{\prime }=m,$$ and the corresponding integer is $l^{\prime }$, we will have $$\begin{array}{rl}{m}_1^{\prime }+m_2^{\prime }& =m_1+m_2,\\ m_1^{\prime }+m_2^{\prime }+m_3^{\prime }+m_4^{\prime }+m_5^{\prime }& =m_1+m_2+m_3+m_4+m_5,\\ l^{\prime }-l& =(m_1^{\prime }{m}_2^{\prime }-m_1{m}_2)+[(m_1^{\prime }+m_2^{\prime })\\ & -(m_1+m_2)](m_3+m_4+m_5)\\ & =m_1-m_2-1\ge 1.\end{array}$$ Contradiction!

Therefore, when $l$ reaches the maximum value, the number of $m+1$ is $r$ and the number of $m$ is $5-r$. Thus, the number of lines from the given points whose lengths are more than 9 are at most $$\begin{array}{rl}& \left(\genfrac{}{}{0ex}{}{r}{2}\right)(m+1{)}^2+(\genfrac{}{}{0ex}{}{r}{1})(5-r)(m+1)m+(\genfrac{}{}{0ex}{}{5-r}{2})m^2\\ & =10m^2+4rm+\frac{1}{2}r(r-1).\end{array}$$

Lemma 3 Take arbitrary $n$ points on the circle $C$ with radius 10 to form set $M$, where $n=6m+r$ ($m,r$ are non-negative integers, $0\le r<6$). Assume that there are $S_n$ triangles whose vertices are from $M$ and each side is longer than 9. Prove $$S_n\le 20m^3+10r{m}^2+2r(r-1)m+\frac{1}{6}r(r-1)(r-2).$$

Proof: We shall prove by mathematical induction.

When $n=1,2$, $S_n=0$. It is true.

Suppose when $n=k$, it is true and set $k=6m+r$ ($m,r$ are non-negative integers, $0\le r<6$). Then $$S_k\le 20m^3+10r{m}^2+2r(r-1)m+\frac{1}{6}r(r-1)(r-2).$$ From Lemma 1, when $n=k+1$, the $k+1$ given points must include the point $P$, where at least $\lfloor \frac{k+1+5}{6}\rfloor =m+1$ given points are in the $\frac{2}{7}\text{arc }{A}_{1}P{A}_6$. And the distances of such points to $P$ are $\le P{A}_1=P{A}_6=a_7<9$. Hence, there are at most $(k+1)-(m+1)=5m+r$ given points whose distances to $P$ are more than 9, and such points are all in the other $\frac{5}{7}\arccos \overline{A_{1}P{A}_6}$ without $P$. From Lemma 2, the lines from such points whose lengths are more than 9 are at most $$10m^2+4rm+\frac{1}{2}r(r-1).$$ (From Lemma 2, when $r=5$, it is $10(m+1{)}^2$, which is also true.) Thus, the number of triangles whose vertex is $P$ and each side is larger than 9 is not more than $$S_p=10m^2+4rm+\frac{1}{2}r(r-1).$$ Without $P$, there are $k=6m+r$ given points. Let there be $S_k$ triangles whose vertices are from the $k$ points and each side is larger than 9, then using mathematical induction, we get $$S_k\le 20m^3+10r{m}^2+2r(r-1)m+\frac{1}{6}r(r-1)(r-2).$$ Furthermore $$\begin{array}{rl}{S}_{k+1}& =S_k+S_p\\ & \le 20m^3+10r{m}^2+2r(r-1)m+\frac{1}{6}r(r-1)(r-2)\\ & +10m^2+4rm+\frac{1}{2}r(r-1)\\ & =20m^3+10(r+1)m^2+2r(r+1)m\\ & +\frac{1}{6}r(r-1)(r+1),\end{array}$$ which means the case $n=k+1=6m+(r+1)$ is also true.

On the other hand, when $r=5$, then $m=k+1=6(m+1)$ and $S_{k+1}$ can be simplified to $S_{k+1}=20(m+1{)}^3$, which is also true.

Therefore, we have proved Lemma 3.

Now considering the original problem, we have $$n=63=6\times 10+3.$$ It follows from Lemma 3, $$\begin{array}{rl}S& \le 20\times 10^3+10\times 10^2+2\times 3\times 2\times 10+\frac{1}{6}\times 3\times 2\times 1\\ & =23121.\end{array}$$ Thus, $S_{\max }=23121$.