Problem

Source: Iberoamerican Olympiad 1990, Problem 5

Tags: analytic geometry, combinatorics proposed, combinatorics



$A$ and $B$ are two opposite vertices of an $n \times n$ board. Within each small square of the board, the diagonal parallel to $AB$ is drawn, so that the board is divided in $2n^{2}$ equal triangles. A coin moves from $A$ to $B$ along the grid, and for every segment of the grid that it visits, a seed is put in each triangle that contains the segment as a side. The path followed by the coin is such that no segment is visited more than once, and after the coins arrives at $B$, there are exactly two seeds in each of the $2n^{2}$ triangles of the board. Determine all the values of $n$ for which such scenario is possible.