Iranian Mathematical Olympiad

By considering centers of the hexagons, we get the following equivalent problem: "Two vertices $\alpha$ and $\beta$ of the triangular lattice are called equivalent if $\alpha -\beta$ is equal to sum of finitely many vectors from the set: $$A=\{\pm (n\vec{i}-m\vec{j}),\pm (n\vec{k}+m\vec{i}),\pm (n\vec{j}+m\vec{k})\}$$ Where $\vec{i}=(1,0)$, $\vec{j}=(-\frac{1}{2},\frac{\sqrt{3}}{2})$ and $\vec{k}=(\frac{1}{2},\frac{\sqrt{3}}{2})$ according to the normal Cartesian coordinates.

What is the maximum number of nonequivalent vertices? Note that $\vec{k}=\vec{i}+\vec{j}$, thus we can determine vectors of set $A$ using only $\vec{i}$ and $\vec{j}$: $$A=\{\pm (n\vec{i}-m\vec{j}),\pm ((n+m)\vec{i}+n\vec{j}),\pm (m\vec{i}+(m+n)\vec{j})\}.$$ Since the first vector $n\vec{i}-m\vec{j}$ is the difference of the two others, two vertices $\alpha$ and $\beta$ are equivalent iff their difference $\alpha -\beta$ can be written as a linear combination of vectors $(n+m)\vec{i}+n\vec{j}$ and $m\vec{i}+(m+n)\vec{j}$ with integer coefficients. Note that for integers $a,b,x$ and $y$ the space generated by the vectors $\{a\vec{i}+b\vec{j},x\vec{i}+y\vec{j}\}$ (using integer coefficients) equals the space generated by vectors $\{(a-x)\vec{i}+(b-y)\vec{j},x\vec{i}+y\vec{j}\}$. Therefore, we can change former vectors to get simpler vectors to work with. Note that in this change the value of $ay-bx$ (determinant of the matrix formed by vectors $(a,b)$ and $(x,y)$ as rows) is invariant, because $ay-bx=(a-x)y-(b-y)x$. Now, in a similar way to Euclidean Algorithm, if $a\ge x$ we change $\{a\vec{i}+b\vec{j},x\vec{i}+y\vec{j}\}$ by $\{(a-x)\vec{i}+(b-y)\vec{j},x\vec{i}+y\vec{j}\}$. Repeating this process several times leads to vectors of the form $s\vec{i}+r\vec{j}$ and $0\vec{i}+t\vec{j}$. It means that we can suppose the coefficient of $\vec{i}$ for one of them is zero. hence, if we want to go from one vertex to another, the difference of the coefficients of $\vec{i}$ must be a multiple of $s$, since $t\vec{j}$ does not affect the coefficient of $\vec{i}$. As a result, for two equivalent vertices, we can first use vector $s\vec{i}+r\vec{j}$ several times to match their first coordinate. Then, we must use $t\vec{j}$ to match the second coordinate. Hence we have $st$ nonequivalent vertices. But $$st=\det \left[\begin{array}{cc}s& r\\ 0& t\end{array}\right]$$ which is invariant during the process. $$\det \left[\begin{array}{cc}s& r\\ 0& t\end{array}\right]=\det \left[\begin{array}{cc}m+n& m\\ n& m+n\end{array}\right]=m^2+mn+n^2$$ So the maximum number of nonequivalent vertices is $m^2+mn+n^2$.