Here is my solution : We prove by induction that there are at least two black triangles, and that $b = w+2$ where $b$ (resp. $w$ ) denote the number of black (resp. white) triangles. First for $n=4$ there are two black triangles and no red and white. Thus the result holds. Now, let $n > 4$ be given, and assume the result holds for any $k$ such that $4 \leq k < n$. Let's consider a $n$-gon as colored as in the statement of the problem. Let $d$ be any diagonal (not side) which has been drawn for the triangulation. Then $d$ separates the $n$-gon into two disjoint polygons. If any of these polygons is a triangle then it is a black one in the original coloring. If none of these polygons is a triangle then use the induction hypothesis for each of the two subpolygons. They gives us at least 2 black triangles on each side of $d$. And, for each side at most one of these black triangles have $d$ as a side. Thus, in any case, there is at least one black triangle on each side of $d$, which ensures that there are a least two black triangles for the $n$-gon. Now, let $T =ABC$ be a black triangle (which does exist from above), with vertices in that order on the $n$-gon. Consider the $n-1$-gon obtained by deleting $T$ and replacing it by the edge $AC$. The coloring induced on this $(n-1)$-gon is the same as the initial one except for the triangle $T'$ having $AC$ as side. Note that since $AC$ is a diagonal of the $n$-gon, then $T'$ was red or white in the original coloring, and since it is a side of the $(n-1)$-gon it is now black or red, respectively. From the induction hypothesis, we have $b'=w'+2$ for the $(n-1)$-gon. - If $T'$ is black for the induced coloring then it was red for the initial one. Adding $T$, it leads to $b=b'-1+1=b'$ and $w=w'$. - If $T'$ is red for the induced coloring then it is white for the initial coloring. Adding $T$ leads to $b = b'+1$ and $w=w'+1$. Thus in any case, we have $b=w+2$ as desired, which ends the induction step and the proof. Pierre.

Shortlist's solution of problem 4 Solution. Denote by b, r, w the number of black, red white triangles respectively. It is easy to prove that the polygon is divided into n-2 triangles, hence b + r + w = n – 2. each side of the polygon is a side of exactly one triangle of the decomposition, and thus 2b + r = n. Subtracting the two relations yields w = b – 2, as needed.

This is a very interesting solution for pb 4, because it does not need induction to prove the result. Pierre.

pbornsztein wrote: This is a very interesting solution for pb 4, because it does not need induction to prove the result. I don't think it is really induction-free. Actually, I don't know any proof of the "easy to prove" fact that the number of triangles used in the triangulation is n - 2 but the one using induction. Darij

Yet, this is easy to do : The sum of the internal angles of the convex $n$-gon is $(n-2) \pi$, which is also the sum of the angles of the triangles of the subdivision according to the statement of the problem, hence there are $n-2$ triangles Moreover, the fact that the sum of the internal angles of the convex $n$-gon is $(n-2) \pi$ is easy to prove without induction again : Just divides the convex $n$-gon into $n-2$ triangles by all the diagonals from one arbitrary vertex, and use again that the sum of the internal angles is the sum of the angles of all these triangles. It is nice that one particular triangulation (the last above) gives the key for any triangulation. Pierre.

And here is my solution: At first we will show a rather simple lemma: Lemma. Let $n\geq 4$ be an integer. Every triangulation of a convex $n$-gon contains at least $2$ black triangles. Proof. The proof will use induction after $n$: Induction base: The case $n = 4$ is not what most of you would call difficult... Induction step: Now assume that we have proved our lemma for all $n\leq k$, where $k$ is a certain number with $k\geq 4$, and now we are going to prove it for $n = k + 1$. In fact, consider a triangulated convex $\left(k + 1\right)$-gon $P$. Assume that it doesn't contain $2$ black triangles. Every side of $P$ belongs either to a black triangle or to a red triangle. Since $k\geq 4$, we have $k+1\geq 5$, and our $\left(k + 1\right)$-gon $P$ has, at least, $5$ sides. Only $2$ of these sides can belong to black triangles (else, we would have at least $2$ black triangles, contradicting our assumption!). Hence, we will always find, at least, one side of $P$ which belongs to a red triangle $T$. If we remove this red triangle, we are left with two triangulated convex polygons $Q$ and $Q^{\prime}$ having one common vertex (namely the third vertex of the removed red triangle). Each of these two polygons $Q$ and $Q^{\prime}$ has $\leq k$ vertices. Now, by our induction assumption, each of these two polygons must have at least two black triangles. Hence we have four black triangles altogether. Now, if we put in the removed red triangle $T$ again, then at most two of these black triangles may possibly become red triangles (in fact, every of our two polygons $Q$ and $Q^{\prime}$ had a side bordering with the removed red triangle $T$; now, if such a side belongs to a black triangle in $Q$ or in $Q^{\prime}$, then, after putting in the red triangle $T$ again, this black triangle becomes a red triangle). But at least $4 - 2 = 2$ black triangles remain. Hence, we have found $2$ black triangles in our $\left(k + 1\right)$-gon $P$, contradicting our assumption. Hence, our $\left(k + 1\right)$-gon $P$ must have $2$ black triangles (at least). This completes the induction step, and the Lemma is proven. Now to the solution of the problem: By the niveau of a triangle in our triangulation, we will mean the number defined according to the following rule: If the triangle is white, then its niveau is -1; if the triangle is red, then its niveau is 0; if the triangle is black, then its niveau is 1. The summary niveau of a triangulated polygon will denote the sum of the niveaus of all triangles involved in the triangulation. Equivalently, it is the number of the black triangles minus the number of the white triangles. Now we will prove that the summary niveau is always equal to $2$ (when $n\geq 4$). This will be obviously enough to solve the problem. I will prove my assertion by induction. For $n = 4$, it is more than trivial. Now we assume that it holds for a certain $n\geq 4$ (i. e. it holds for all $n$-gons), and we have to show that it holds for $n + 1$ (i. e. for all $\left(n + 1\right)$-gons). Consider a triangulated $\left(n + 1\right)$-gon $P$. Clearly, $n\geq 4$ yields $n+1\geq 5$. On the other hand, after the Lemma, the triangulated $\left(n + 1\right)$-gon $P$ contains at least two black triangles. Let $D$ be one of them. Now remove this black triangle $D$. What you then get is a triangulated $n$-gon $P^{\prime}$. All black, white, red triangles in the triangulation of $P$ preserve their color in $P^{\prime}$, except for the initial black triangle $D$, which disappears, and the triangle $D^{\prime}$ directly bordering with $D$. In fact, if $D^{\prime}$ was a red triangle for $P$, then it becomes a black triangle for $P^{\prime}$, and if $D^{\prime}$ was a white triangle for $P$, then it becomes a red triangle for $P^{\prime}$. (You can easily figure out that $D^{\prime}$ could not have been a black triangle for $P$; since otherwise, all three sides of $D^{\prime}$ would be sides of $P^{\prime}$, and thus, the polygon $P^{\prime}$ would be a triangle, and $P$ would be a quadrilateral, contradicting $n+1\geq 5$.) Now, we see that the triangulated polygons $P$ and $P^{\prime}$ have the same summary niveau. This is because when we remove the black triangle $D$, then on one hand, we lose a niveau of $1$ (since $D$ had a niveau of $1$), but on the other hand, we gain a niveau of $1$ again (in fact, if $D^{\prime}$ was a red triangle for $P$, then it becomes a black triangle for $P^{\prime}$, so that the niveau changes from $0$ to $1$, and if $D^{\prime}$ was a white triangle for $P$, then it becomes a red triangle for $P^{\prime}$, so that the niveau changes from $-1$ to $0$). Hence, the sum of the niveaus of all triangles remains constant, i. e., the summary niveaus of the triangulated polygons $P$ and $P^{\prime}$ are equal. But since $P^{\prime}$ has $n$ edges, then by our induction assumption, its summary niveau is $2$, and hence the summary niveau of $P$ is also $2$. Proof complete. Darij

We use strong induction on $n$. Consider a white triangle in the middle of the polygon. It then divides the problem into three separate subpolygons. Lemma: In each of the subpolygons, $B = W + 1$. This is easy to see, because red triangles are counted as black and white polygons are counted as red. Then we apply the induction hypothesis. Therefore, summing over the subpolygons, $B = W + 3$. But we must include the white triangle in the center, so $B = W +2$, as desired.

First we shall state a $lemma$: $Lemma$: A convex polygon with $n$ sides can be arbitrarily decomposed into exactly $n-2$ triangles having all the vertices among the vertices of the polygon, such that no two of the triangles have interior points in common. $Proof of Lemma$: Sum of internal angles of a convex polygon with $n$ sides is $(n-2) \pi$. Since triangles are using all of the vertices of the polygon, the aggregate sum of angles of all the triangles must equal the sum of internal angles of a convex polygon = $(n-2) \pi$. Thus, number of triangles = $(n-2) \pi / \pi = n-2$. $Proof of problem$: Let there be a total of $x Black$ triangles in $n$ sided convex polygon $P1$. Now consider the polygon $P2$ formed after removing all the $x$ black triangles from polygon $P1$. It's not hard to see that $P2$ has exactly $(n - x)$ sides. Now, in polygon $P2$, we are left with exactly $(n - x) - x = n - 2x$ sides which are still part of the original Polygon $P1$. No two adjacent sides of these $(n - 2x)$ can be joined to form another $Black$ triangle (since we have assumed a total of $x Black$ triangles exist). So that leaves us with $(n - 2x)$ $Red$ triangles in total. So, now all the triangles that remain must be $White$ triangles. From lemma, $P2$ has exactly $(n - x - 2)$ triangles satisfying the conditions of the problem, so the number of $White$ triangles = $(n - x - 2) - (n - 2x) = x - 2$ Thus total number of $White$ triangles = $x - 2$ which is $2$ less than total number of $Black$ triangles.

We induct on $n$, with trivial base cases $n=4$ and $n=5$. We also note that 0 white triangles imply 2 black triangles and the rest are red. Hence we assume the existence of at least 1 white triangle, which we draw in. The remainder of the polygon is split into 3 smaller polygons, from which we claim the following: Claim: In each of these polygons, we have $B-W=1$. Obvious if the polygon is a triangle. Otherwise, we utilize our inductive hypothesis, which says $B-W=2$ with respect to the sides of our smaller polygon. However, we must consider the triangle with one side on our main white triangle. If the triangle is black in our smaller polygon, it is red in our original polygon, and if it is red in our smaller polygon, it is white in our original polygon. Thus the difference $B-W$ decreases by 1. ${\color{blue} \Box}$ Thus we conclude by summing over the 3 new polygons and adding back our white triangle. $\blacksquare$

In any triangulation of the polygon, we will be left with $n-2$ triangles. Hence, if there are no white triangles, it is clear we must have exactly $2$ black triangles. Then, suppose that there exists at least one white triangle, denoted as $W$. Removing $W$ from the polygon will split the original into three more polygons: If any of them are a triangle, then it is obvious that it is a black triangle. Otherwise, the inductive hypothesis with respect to the smaller polygon states that there are two more black triangles than white ones. However, we need to consider the triangle that shares a side with $W$. If this triangle is black in our smaller polygon, then it is red in our original polygon, and if the triangle is red in our smaller polygon, it is white in our original polygon. Either way, the difference between black triangles and white triangles with respect to the original polygon becomes $1$. The combined difference between black triangles and white triangles is $3$ over all of the smaller polygons, which becomes $2$ when adding back $W$. $\blacksquare$