China-TST-2025A

It is well-known that the area of a triangle with vertices $(x_1,y_1)$, $(x_2,y_2)$, $(x_3,y_3)$ is given by $$\frac{1}{2}|(y_2-y_1)(x_3-x_1)-(y_3-y_1)(x_2-x_1)|$$ (This equals zero if and only if the three points are collinear). Therefore, the condition that $(x_1,y_1)$, $(x_2,y_2)$, $(x_3,y_3)$ are non-collinear and twice the area of their triangle is not divisible by $p$ is equivalent to $(y_2-y_1)(x_3-x_1)$ and $(y_3-y_1)(x_2-x_1)$ being incongruent modulo $p$.

First, we show that $n=p+2$ is impossible. Let $A_i(x_i,y_i)$ ($i=1,\dots ,p+2$). If any three $x$-coordinates are congruent modulo $p$, then the corresponding three points form a triangle whose twice area is divisible by $p$. Otherwise, since $p+2$ is odd, there exists one $x$-coordinate distinct modulo $p$ from all others. Without loss of generality, assume $x_1$ is distinct modulo $p$ from all other $x_i$. Consider the values $\frac{y_i-y_1}{x_i-x_1}$ modulo $p$ ($i=2,\dots ,p+2$). Since there are only $p$ possible residues, by the pigeonhole principle, two must be equal. If $\frac{y_i-y_1}{x_i-x_1}=\frac{y_j-y_1}{x_j-x_1}$ ($2\le i<j\le p+2$), then $p$ divides $2S_{△A_1{A}_i{A}_j}$.

Next, we construct an example with $n=p+1$. Let $t$ be a quadratic non-residue modulo $p$. Consider pairs $(x,y)$ with $x,y\in \{0,1,\dots ,p-1\}$ satisfying $y^2-t{x}^2\equiv C(\mathrm{mod}p)$ for some fixed $C\ne 0$. There are exactly $p+1$ such pairs (including $(0,0)$ when $C=0$, but we exclude this case).

We verify that these $p+1$ points satisfy the condition. For any three points $A_i,A_j,A_k$: If two have the same $x$-coordinate, their distance isn't divisible by $p$, and the height from the third point is a positive integer less than $p$, so twice the area isn't divisible by $p$. If all $x$-coordinates are distinct, we show $\frac{y_j-y_i}{x_j-x_i}\ne \frac{y_k-y_i}{x_k-x_i}(\mathrm{mod}p)$. If they were equal to some $m$, then $y\equiv mx+r(\mathrm{mod}p)$ would hold for three distinct $x$-values, implying $(mx+r{)}^2-t{x}^2\equiv C(\mathrm{mod}p)$ has three solutions. This contradicts Lagrange's theorem since $m^2\ne t(\mathrm{mod}p)$ (as $t$ is a non-residue).

Therefore, the maximal $n$ is $p+1$. □