China Team Selection Test

Define $x_i=0$ or $1$ depending on whether $A_i$ is red or blue. For obtuse triangle $A_{i-a}{A}_i{A}_{i+b}$ (vertex $A_i$ is the vertex of the obtuse angle, i.e. $a+b\le 50$), these three vertices satisfy the conditions of the problem if and only if $$(x_i-x_{i-a})(x_i-x_{i+b})=1,\stackrel{◯}{1}$$ otherwise equals $0$, here the subscript is modulo $101$. Thus $$N=\sum _{i=1}^{101}\sum _{(a,b)}(x_i-x_{i-a})(x_i-x_{i+b}),$$ here ${\sum }_{(a,b)}$ stands for the summation of all positive integer pairs $(a,b)$ satisfying $a+b\le 50$, there are $49+48+\cdots +1=1225$ such positive integer pairs. Expand $\stackrel{◯}{1}$, we have $$\begin{array}{rl}N& =\sum _{i=1}^{101}\sum _{(a,b)}(x_i-x_{i-a})(x_i-x_{i+b})\\ & =\sum _{i=1}^{101}\sum _{(a,b)}(x_i^2-x_i{x}_{i-a}-x_i{x}_{i+b}+x_{i-a}{x}_{i+b})\\ & =1225\sum _{i=1}^{101}{x}_i^2+\sum _{i=1}^{101}\sum _{k=1}^{50}(k-1-2(50-k))x_i{x}_{i+k}\end{array}$$

$$=1225n+\sum _{i=1}^{101}\sum _{k=1}^{50}(3k-101)x_i{x}_{i+k},\stackrel{◯}{2}$$ here $n$ is the number of the blue vertices. For any two vertices $A_i,A_j$, $1\le i\le j\le 101$, let $$d(A_i,A_j)=d(A_j,A_i)=\min \{j-i,101-j+i\}.$$ Let $B\subseteq \{A_1,A_2,\dots ,A_{101}\}$ be the set of all blue vertices, then $\stackrel{◯}{2}$ can be written as $$N=1225n-101C_n^2+3\sum _{\{P,Q\}\subseteq B}d(P,Q),\stackrel{◯}{3}$$ where $\{P,Q\}$ runs through all the two-element subsets of $B$. Without loss of generality, we assume $n$ is even. Otherwise, color all the vertices the opposite, the value of $N$ does not change. Write $n=2t$, $0\le t\le 50$, from one point, renumber all the blue vertices as $P_1,P_2,\dots ,P_{2t}$ clockwise. Then $$\sum _{\{P,Q\}\subseteq B}d(P,Q)=\sum _{i=1}^{t}d(P_i,P_{i+t})+\frac{1}{2}\sum _{i=1}^t\sum _{j=1}^{t-1}(d(P_i,P_{i+j})+d(P_{i+j},P_{i+t})+d(P_{i+t},P_{i-j})+d(P_{i-j},P_i))\le 50t+\frac{101}{2}t(t-1),\stackrel{◯}{4}$$ here the subscript of $P_i$ is modulo $2t$, and we use the inequality $d(P_i,P_{i+t})\le 50$ and $$d(P_i,P_{i+j})+d(P_{i+j},P_{i+t})+d(P_{i+t},P_{i-j})+d(P_{i-j},P_i)\le 101.\stackrel{◯}{5}$$ Combine $\stackrel{◯}{3}$ and $\stackrel{◯}{4}$, we have $$N\le 1225n-101C_n^2+3\left(50t+\frac{101}{2}t(t-1)\right)=-\frac{101}{2}{t}^2+\frac{5099}{2}t.\stackrel{◯}{6}$$ The right hand side of $\stackrel{◯}{6}$ attains its maximum value when $t=25$, thus $N\le 32175$.

The number of ways to choose $50$ blue vertices such that $N$ achieves maximum is equal to the number of ways to choose $25$ diagonals from the longest $101$ diagonals such that any two diagonals do not have common vertices.

Edging $A_i$ and $A_{i+50}$, $i=1,2,\dots ,101$, we get a graph $G$. Notice that $50$ and $101$ are relatively prime, so $1+50n$ ($0\le n\le 100$) form a complete residue system modulo $101$, i.e. $G$ is a circle with $101$ edges. Therefore, the number of ways (written as $S$) to color $50$ vertices blue and $N$ achieves maximum, is equal to the number of ways to choose $25$ edges of $G$, such that any two of them do not have common vertices. Now, fix one edge $e$ of $G$. Since the number of ways to choose edges having $e$ is $C_{75}^{24}$, not having $e$ is $C_{76}^{25}$, so $S=C_{75}^{24}+C_{76}^{25}$. Similarly, the number of ways to have $50$ red vertices is also $S$, thus the number of ways to color the vertices such that the largest value of $N$ is achieved is $2S$.

In a word, the largest possible value of $N$ is $32175$, the number of ways to color is $2S=2(C_{75}^{24}+C_{76}^{25})$.