33rd Hellenic Mathematical Olympiad

Drawing from the vertices of the rhombus parallel lines to the sides of the lattice, we find the least rectangle in which the rhombus is inscribed. Since the rhombus is symmetric with respect to its center, this rectangle will have sides with even length. Therefore it is enough to count the rectangles with even sides $2s\times 2t$, for which $s\ne t$. It is equivalent to count first all rectangles $2s\times 2t$ and then subtract all squares $2s\times 2t$.



Let $n=2k$

We count all vertical lines of the lattice from left to right by $1,2,3,\dots ,2k+1$ and all horizontal lines from bottom to top by $1,2,3,\dots ,2k+1$. A rectangle $2s\times 2t$ is determined from two vertical lines and two horizontal lines having even distance. Two lines have even distance when their numbers are of the same parity. We can select two vertical lines with even numbers and even distance in $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ ways, while to select two vertical lines with odd numbers and even distance we have $\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)$ ways. Therefore, the total number of ways to select two vertical lines with even distance is $\left(\genfrac{}{}{0ex}{}{k}{2}\right)+\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)=k^2$. Similarly, we have $k^2$ possible selections for the horizontal lines. In total, we have $k^2\cdot k^2=k^4$ rectangles of the type $2s\times 2t$.

It remains to subtract all squares $2s\times 2s$. The $2\times 2$ squares are totally $(n-2+1{)}^2=(2k-2+1{)}^2$. The $4\times 4$ squares are totally $(n-4+1{)}^2=(2k-4+1{)}^2$. In general, the $2s\times 2s$ squares are totally $(n-2s+1{)}^2=(2k-2s+1{)}^2$. Hence we have $$\begin{gathered} \sum _{s=1}^k(2k-2s+1{)}^2=\sum _{s=1}^k(2k+1{)}^2-4s(2k+1)+4s^2= \\ k(2k+1{)}^2-2(2k+1)k(k+1)+4\frac{k(k+1)(2k+1)}{6}=\frac{k(2k-1)(2k+1)}{3} \end{gathered}$$ Therefore all rhombuses in the even case are: $$k^4-\frac{k(2k-1)(2k+1)}{3}=\frac{k(k-1)(3k^2-k-1)}{3}$$

Let $n=2k+1$. Then, similarly, we have $\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)+\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)=k(k+1)$ possible selections for the two vertical lines and $k(k+1)$ possible selections for the horizontal lines. Totally we have $(k(k+1){)}^2$ rectangles $2s\times 2t$. We have to subtract the squares $2s\times 2s$ which totally are $$(n-2s+1{)}^2=(2k+1-2s+1{)}^2=(2k+2-2s{)}^2$$ Hence we have $$\begin{gathered} \sum _{s=1}^k(2k+2-2s{)}^2=\sum _{s=1}^k(2k+2{)}^2-4(2k+2)s+4s^2 \\ =k(2k+2{)}^2-2(2k+2)k(k+1)+4\frac{k(k+1)(2k+1)}{6}=\frac{2k(k+1)(2k+1)}{3} \end{gathered}$$ Hence in the odd case the rhombuses are totally $$(k(k+1){)}^2-\frac{2k(k+1)(2k+1)}{3}=\frac{k(k+1)(3k^2-k-2)}{3}$$