Balkan Mathematical Olympiad Shortlist

By a lattice hexagon we will mean a regular hexagon whose sides run along edges of the lattice. Given any regular hexagon $H$, we construct a lattice hexagon whose edges pass through the vertices of $H$, as shown in the figure, which we will call the enveloping lattice hexagon of $H$. Given a lattice hexagon $G$ of side length $m$, the number of regular hexagons whose enveloping lattice hexagon is $G$ is exactly $m$. Yet also there are precisely $3(n-m)(n-m+1)+1$ lattice hexagons of side length $m$ in our lattice: they are those with centres lying at most $n-m$ steps from the centre of the lattice. In particular, the total number of regular hexagons equals $$N=\sum _{m=1}^n(3(n-m)(n-m+1)+1)m=(3n^2+3n)\sum _{m=1}^{n}m-3(2m+1)\sum _{m=1}^n{m}^2+3\sum _{m=1}^n{m}^3.$$ Since ${\sum }_{m=1}^{n}m=\frac{n(n+1)}{2}$, ${\sum }_{m=1}^n{m}^2=\frac{n(n+1)(2n+1)}{6}$ and ${\sum }_{m=1}^n{m}^3={\left(\frac{n(n+1)}{2}\right)}^2$ it is easily checked that $N={\left(\frac{n(n+1)}{2}\right)}^2$.