Question 41
$A$ and $B$ are opposite corners of an $n \times n$ board, divided into $n^{2}$ squares by lines parallel to the sides. In each square the diagonal parallel to $AB$ is drawn, so that the board is divided into $2 n^{2}$ small triangles. The board has $(n+1)^{2}$ nodes and a large number of line segments, each of length $1$ or $\sqrt{2}$. A piece moves from $A$ to $B$ along the line segments. It never moves along the same segment twice and its path includes exactly two sides of every small triangle on the board. For which $n$ is this possible?