Find all positive integer $k$ such that one can find a number of triangles in the Cartesian plane, the centroid of each triangle is a lattice point, the union of these triangles is a square of side length $k$ (the sides of the square are not necessarily parallel to the axis, the vertices of the square are not necessarily lattice points), and the intersection of any two triangles is an empty-set, a common point or a common edge.
Problem
Source: 2022 China TST, Test 3 P4
Tags: combinatorics, geometry, combinatorial geometry, lattice points
01.05.2022 01:21
Claim: the only such numbers are the multiples of $3$. If $k=3t$ pick an axis and grid aligned $k\times k$ square divided in $t\times t$ square each of side $3\times 3$, and divide these in two triangles. In this way it is straight forward enough to see that the barycenters must have integer coordinates. Lemma: given triangles with integer centroids (calls such triangles good) $ABC$ and $A'BC$, the vertices $A$ and $A'$ differ by three times an integer vector Proof: $A'-A=3(\frac{A'+B+C}{3}-\frac{A+B+C}{3})$. Since the two centroids have integer coordinates, their differences is an integer vector, so we are done. Now, using the lemma, divide the vertices of the triangulation in ($\leq$) $3$ equivalence classes where the equivalence relation is differing by three times an integer vector [from any vertex we can reach a vertex of a fixed triangle, by multiple steps of the form $A\to A'$ if there is a segment $BC$ such that $ABC,A'BC$ both belong to the triangulation]. Since the square has $4>3$ vertices, at least two will be in the same of the three equivalence classes. Let $\Delta x$ be the difference between the $x$ coordinates of these two vertices, and $\Delta y$ that of $y$ coordinates. If the two vertices are opposite wrt the square we have $\Delta x^2+\Delta y^2=2k^2$. Since the two vertices are equivalent, $3|\Delta x,\Delta y\implies 3|\Delta x^2+\Delta y^2=2k^2\implies 3|k$. Similarly if the two vertices are adjacent wrt the square, $3|\Delta x^2+\Delta y^2=k^2\implies 3|k$. In both cases, $k$ is divisible by $3$, so we are done.