9.9. On a board, a convex $n$-gon ($n \geqslant 4$) is drawn. Each of its vertices must be painted either black or white. A diagonal is called bicolored if its ends are painted in different colors. A coloring of the vertices is called good if the $n$-gon can be divided into triangles by bicolored diagonals that do not have common points (except vertices). Find the number of good colorings.

(S. Berlov)
Answer: $n^{2}-n$.

Solution. Immediately note that coloring all vertices in one color is not a good coloring; such colorings are not considered in the further solution.

Let's call a side of the polygon bicolored if its ends are colored in different colors (i.e., extend the definition of bicolored to sides). We will call a coloring of vertices ordered if all black vertices on the boundary of the polygon are consecutive (in other words, the polygon has exactly two bicolored sides).

Lemma. A coloring of the vertices of an $n$-gon (for $n \geqslant 3$) is good if and only if it is ordered.

Proof. Induction on $n$. For $n=3$, there is nothing to prove (recall that we do not consider monochromatic colorings). Now let's prove the inductive step. Suppose the statement is proven for all $m$ such that $3 \leqslant m < n$, where $n \geqslant 4$.

Assume the coloring is good. Divide the polygon into triangles using non-intersecting bicolored diagonals; consider one of these diagonals $AB$. It divides the $n$-gon into two polygons $P_{1}$ and $P_{2}$ with fewer sides, and each of them is colored well—hence, by the inductive hypothesis, they are also ordered. Let $A$ be the black end of the diagonal, and $B$ be the white end. All black vertices in $P_{1}$ are several consecutive vertices starting from $A$ (but not including $B$). Similarly for the black vertices in $P_{2}$. Then these two blocks of black vertices, when combined, form one connected block in the original polygon, meaning the coloring of the vertices of the $n$-gon is also ordered.

Now assume the coloring is ordered. It is easy to see that then there is a bicolored diagonal in the polygon. This diagonal divides the polygon into two smaller ones, and each of them is clearly colored in an ordered manner. By the inductive hypothesis, each of them is colored well, and thus the original $n$-gon is also colored well.

Given the lemma, it remains to count the number of ordered colorings of the $n$-gon. For each possible number of black vertices (from 1 to $n-1$), there are $n$ ways to choose the placement of their block among all $n$ vertices, so the number of ways is $n(n-1)$.

Comment. Only the answer - 0 points.

The lemma is formulated in the solution (from above) - 1 point.

The lemma is fully proven - 4 points are added.

Only one of the two halves of the lemma statement is proven (i.e., either that any good coloring is ordered, or vice versa) - 2 points are added instead of 4.

The number of ordered colorings is calculated - 2 points are added (these points can only be added if the lemma is formulated, with or without proof).

There are minor errors in this calculation (for example, leading to an answer that is half the correct one) - 1 point is added instead of 2.

In the inductive proof of the lemma (formulated for all $n \geqslant 4$), there may be a problem, especially for small values of $n$: a bicolored diagonal may cut off a triangle to which the inductive hypothesis is not applicable. If this occurs in the work - 1 point is deducted.