2022 China Team Selection Test for IMO

The desired positive integers $k$ are those divisible by $3$.

First assume that $k=3t$ for $t\in \mathbb{N}$. Consider the square with vertices $(0,0)$, $(3t,3t)$, $(3t,0)$, and $(0,3t)$. Divide it into $t^2$ different smaller squares with the same side length $3$ along the lines $x=3i$ ($i=1,\dots ,t$) and $y=3j$ ($j=1,\dots ,t$). After this, each square can be divided into $2$ isosceles right triangles along the diagonal, and the center of mass of each triangle is an integral point. This gives the needed triangulation.

Conversely, suppose that a square with side length $k$ has a triangulation such that the center of mass of each small triangle is an integral point. Let $V$ denote the set of all vertices of the triangulation. Define a binary relation $A{\sim }_{0}B$ in $V$ if two triangles of the triangulation are of the form $△ACD$, $△BCD$. The equivalence relation $\sim$ on $V$ is generated by ${\sim }_0$, i.e. $A{\sim }_{0}B$ if and only if there exist $A_1,\dots ,A_r$ such that $A{\sim }_0{A}_1{\sim }_0\cdots {\sim }_0{A}_r{\sim }_{0}B$. Denote the horizontal and vertical coordinates of a point $P$ by $x_P$ and $y_P$, respectively. We have

(i) If $A{\sim }_{0}B$, then $3\mid x_A-x_B$ and $3\mid y_A-y_B$. This is because: by transitivity, one may assume that $A{\sim }_{0}B$, i.e., there are two triangles in the triangulation of the form $△ACD$, $△BCD$, whose centers of mass are both integral points. Therefore, $3\mid x_A+x_C+x_D$ and $3\mid x_B+x_C+x_D$; thus $3\mid x_A-x_B$. We may deduce similarly $3\mid y_A-y_B$.

(ii) The set $V$ has at most $3$ equivalent classes with respect to $\sim$. This is because after fixing a triangle $T_0$, for each point $A$ in $V$, there is always a sequence of triangles $T_0,\dots ,T_r$ such that $T_{i-1}$ and $T_i$ shares a same side for all $i=1,\dots ,r$, and that $A$ is a vertex of $T_r$. By definition of $\sim$, all three vertices of $T_{i-1}$ are respectively equivalent to three vertices of $T_i$. Hence by induction, $A$ is equivalent to one of the vertices of $T_0$.

By (ii) together with the pigeonhole principle, two of the four vertices of a square must be equivalent. Then from (i), we know that $3\mid k^2$ or $3\mid 2k^2$, which implies $3\mid k$.