$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.
Problem
Source: Iberoamerican Olympiad 1990, Problem 5
Tags: analytic geometry, combinatorics proposed, combinatorics
18.09.2007 18:39
Consider a coordinate grid such that $ A\equiv(n,0)$, $ B\equiv(0,n)$, and the other two corners of the board are $ (0,0)$ and $ (n,n)$. The conditions of the problem may be obviously restated as this: color some of the sides of the triangles such that (1) in each triangle exactly two sides are colored, and such that (2) at each vertex of the grid, an even number of colored edges meet, except for $ A$ and $ B$, where an odd number of colored edges meet. The colored edges mark the path from $ A$ to $ B$ such that in each triangle exactly two seeds are placed. Let us assume that the scenario is possible for some $ n$. Since exactly two edges meet at $ (0,0)$, because of (2) they are both colored or not colored. Then, because of (1) applied to the triangle that has $ (0,0)$ as a vertex, both these edges must be colored, while the edge joining $ (0,1)$ and $ (1,0)$ must be left uncolored. Applying (1) again to the triangle with vertices $ (0,1)$, $ (1,0)$ and $ (1,1)$, the other two sides of this triangle must be colored. Or, applying (2) to vertices $ (0,1)$ and $ (1,0)$, the edges joining these points to $ (0,2)$ and $ (2,0)$, respectively, must be left uncolored. Then, applying (1) again, edges joining $ (1,1)$ to both $ (0,2)$ and $ (2,0)$ must be colored. Considering (2) applied to vertex $ (1,1)$, either both edges joining this vertex to $ (1,2)$ and $ (2,1)$ are colored, or both are uncolored. Because of (1) once again, both are colored, while the edge joining $ (2,1)$ and $ (1,2)$ must be uncolored. Hence, because of (1) again, edges joining $ (2,2)$ to both $ (1,2)$ and $ (2,1)$ are colored. Note at this point that, if $ n = 2$ we are done and the task is accomplished, or for $ n = 2$ the scenario is possible. Let us henceforth assume that the scenario is possible for some $ n > 2$. Then, because of (1), the edge joining $ (2,0)$ and $ (2,1)$ must be left uncolored, or because of (1) again, edges joining $ (3,0)$ to both $ (2,0)$ and $ (2,1)$ must be colored. Then, because of (2), the edge joining $ (2,1)$ and $ (3,1)$ must be colored, or the edge joining $ (3,0)$ and $ (3,1)$ is uncolored. Note that this makes the scenario impossible for $ n = 3$, since then there would be an even number of colored edges meeting at $ A$. But if $ n > 3$, then because of (2), the edge joining $ (3,0)$ and $ (4,0)$ must be left uncolored. But this makes the triangle formed by these two vertices and $ (3,1)$ violate (1). Or the scenario is not possible either for $ n > 3$. So the scenario is only possible for $ n = 2$, and a possible path is $ A\equiv(2,0)\rightarrow(1,1)\rightarrow(0,1)\rightarrow(0,0)\rightarrow(1,0)\rightarrow(1,1)\rightarrow(2,1)\rightarrow(2,2)\rightarrow(1,2)\rightarrow(1,1)\rightarrow(0,2)\equiv B$.