
Problem 10.3. Find all natural numbers $n$ for which a convex $n$ gon can be partitioned into triangles through its diagonals in such a way that there is an even number of diagonals from each vertex. (If there is a vertex with no digonals through it, assume that there is an even number (zero) of diagonals from this vertex).


Solution: It is easy to see by induction that if an $n$-gon is partitioned into triangles through $d$ non-intersecting diagonals then $n=d+3$. Let $n$ be a natural number and $A_{1} A_{2} \cdots A_{n}$ is a convex $n$-gon which can be partitioned into triangles through $d$ diagonals in a way that there is an even number of diagonals through each vertex. Since $n=3$ is a solution we may assume that $n \geq 4$.

It is clear that at least one side of each triangle is a diagonal of the $n$-gon. We say that a triangle is of type $t_{k},(k=1,2,3)$ if exactly $k$ of its sides are diagonals. Denote by $x_{k}$ the number of triangles of type $t_{k}$. It is easy to see that $2 x_{1}+x_{2}=n=d+3$ abd $x_{1}+2 x_{2}+3 x_{3}=2 d$. It follows now that $x_{1}=x_{3}+2$, so $x_{1}>0$. Therefore there exists a triangle two of whose sides are sides of the $n$-gon. Let that be $A_{j-1} A_{j} A_{j+1}$. Diagonal $A_{j-1} A_{j+1}$ is a side of another triangle-e. g., $A_{j-1} A_{j+1} A_{s}$. Assume that $A_{j-1} A_{s}$ or $A_{j+1} A_{s}$ is a side of the $n$-gon. If it is $A_{j-1} A_{s}$ then $s=j-2$. It follows now that there are no diagonals from $A_{j-1}$ distinct from $A_{j-1} A_{j+1}$ because such a diagonal intersects $A_{j+1} A_{s}$. This contradicts the premise that there is an even
number of diagonals from each vertex. Therefore both $A_{j-1} A_{s}$ and $A_{j+1} A_{s}$ are diagonals so $A_{j-1} A_{j+1} A_{s}$ is of type $t_{3}$. Hence there is a triangle of type $t_{3}$ adjacent to each triangle of type $t_{1}$. If distinct triangles of type $t_{1}$ are adjacent to distinct triangles of type $t_{3}$ then $x_{1} \leq x_{3}=x_{1}-2<x_{1}$, a contradiction. Therefore there are at least two triangles of type $t_{1}$ adjacent to one and the same triangle of type $t_{3}$. Without loss of generality assume these are the triangles $A_{1} A_{n} A_{n-1}$ and $A_{n-1} A_{n-2} A_{n-3}$. Consider the polygon $A_{1} A_{2} \cdots A_{n-3}$. Obviously the diagonals partition this polygon into triangles and there is an even number of diagonals through each vertex.

Conversely, if the polygon $A_{1} A_{2} \cdots A_{n-3}$ can be partitioned in the required way, then adding the vertices $A_{n-2}, A_{n-1}, A_{n}$ and diagonals $A_{n-3} A_{n-1}$ and $A_{1} A_{n-1}$ shows that the same is true for the polygon $A_{1} A_{2} \cdots A_{n}$.

Therefore a natural number $n \geq 6$ is a solution if and only if $n-3$ is a solution. It is easy to see that $n=3$ is a solution, whereas $n=4$ and $n=5$ are not. Thus all natural numbers satisfying the conditions of the problem are $n=3 k, k=1,2, \ldots$.
