Problem

Source: Romania TST for BMO 1989 P5

Tags: rotation, combinatorics proposed, combinatorics



A laticial cycle of length $n$ is a sequence of lattice points $(x_k, y_k)$, $k = 0, 1,\cdots, n$, such that $(x_0, y_0) = (x_n, y_n) = (0, 0)$ and $|x_{k+1} -x_{k}|+|y_{k+1} - y_{k}| = 1$ for each $k$. Prove that for all $n$, the number of latticial cycles of length $n$ is a perfect square.