China-TST-2025A

The maximal integer $k$ is $\frac{\sigma (n)+\tau (n)-n-1}{2}$. (Note that from this formula, $\sigma (n)$ and $\tau (n)$ have the same parity.)

Label the vertices of $V$ as $A_0,A_1,\cdots ,A_{n-1}$, with indices considered modulo $n$.

We say a coloring is perfect if there exists $i$ such that $A_i$ is red, and for any $1\le k\le \frac{n-1}{2}$, $A_{i-k}$ and $A_{i+k}$ are colored with different colors (one red and one blue).

First, we show that for a perfect coloring, the number of good polygons is $\frac{\sigma (n)+\tau (n)-n-1}{2}$. Without loss of generality, assume $i=0$.

For each divisor $d\ne n$ of $n$, there are $d+1$ regular $\frac{n}{d}$-gons in $\mathcal{P}$ of two types:

1) $A_0{A}_d{A}_{2d}\cdots A_{n-d}$

2) $A_b{A}_{b+d}\cdots A_{n-d+b}$ where $b\in \{1,\cdots ,d-1\}$.

The regular $\frac{n}{d}$-gon $A_0{A}_d\cdots A_{n-d}$ is always good because $A_0$ is red, while for $s=1,\cdots ,\frac{n}{d}-1$, $A_{sd}$ and $A_{-sd}$ have different colors.

For $b\in \{1,\cdots ,d-1\}$, the polygons $A_b{A}_{d+b}\cdots A_{n-d+b}$ and $A_{d-b}{A}_{2d-b}\cdots A_{n-b}$ have corresponding vertices $A_{sd+b}$ and $A_{-sd-b}$ with different colors, so exactly one of these two polygons must be good.

Therefore, the number of good polygons in a perfect coloring is: $$\sum _{\begin{array}{c}d|n\\ d\ne n\end{array}}\frac{d+1}{2}=\frac{\sigma (n)+\tau (n)-n-1}{2}.$$

Now we show Alice can guarantee at least $\frac{\sigma (n)+\tau (n)-n-1}{2}$ good polygons by ensuring a perfect coloring. Alice first colors $A_0$ red. Then, whenever Bob colors $A_a$ ($1\le a\le n-1$) blue, Alice colors $A_{-a}$ red. Since $n$ is odd, this strategy can be executed.

Conversely, Bob can ensure at most $\frac{\sigma (n)+\tau (n)-n+1}{2}$ good polygons by also enforcing a perfect coloring. After Alice colors her first point red (wlog assume it's $A_0$), Bob pairs $A_a$ with $A_{-a}$ for $1\le a\le n-1$.

Bob starts by coloring any unpaired point blue. Subsequently, after Alice's move: - If Alice colors a point whose paired point is uncolored, Bob colors its pair blue. - Otherwise, Bob colors any remaining uncolored point blue.

This ensures a perfect coloring, limiting good polygons to $\frac{\sigma (n)+\tau (n)-n+1}{2}$.

Combining both strategies, the maximal integer $k$ is $\frac{\sigma (n)+\tau (n)-n-1}{2}$. $\square$