Let $n$ be an integer with $n \geq 3$. Consider all dissections of a convex $n$-gon into triangles by $n-3$ non-intersecting diagonals, and all colourings of the triangles with black and white so that triangles with a common side are always of a different colour. Find the least possible number of black triangles.
. The answer is $\left\lfloor\frac{n-1}{3}\right\rfloor$.

Let $f(n)$ denote the minimum number of black triangles in an $n$-gon. It is clear that $f(3)=0$ and that $f(n)$ is at least 1 for $n=4,5,6$. It is easy to see that for $n=4,5,6$ there is a coloring with only one black triangle, so $f(n)=1$ for $n=4,5,6$.

First we prove by induction that $f(n) \leq\left\lfloor\frac{n-1}{3}\right\rfloor$. The case for $n=3,4,5$ has already been established. Given an $(n+3)$-gon, draw a diagonal that splits it into an $n$-gon and a 5-gon. Color the $n$-gon with at most $\left\lfloor\frac{n-1}{3}\right\rfloor$ black triangles. We can then color the 5-gon compatibly with only one black triangle so $f(n+3) \leq\left\lfloor\frac{n-1}{3}\right\rfloor+1=\left\lfloor\frac{n+3-1}{3}\right\rfloor$.

Now we prove by induction that $f(n) \geq\left\lfloor\frac{n-1}{3}\right\rfloor$. The case for $n=3,4,5$ has already been established. Given an $(n+3)$-gon, we color it with $f(n+3)$ black triangles and pick one of the black triangles. It separates three polygons from the $(n+3)$-gon, say an $(a+1)$-gon, $(b+1)$-gon and a $(c+1)$-gon such that $n+3=a+b+c$. We write $r_{m}$ for the remainder of the integer $m$ when divided by 3. Then

$$
\begin{aligned}
f(n+3) & \geq f(a+1)+f(b+1)+f(c+1)+1 \\
& \geq\left\lfloor\frac{a}{3}\right\rfloor+\left\lfloor\frac{b}{3}\right\rfloor+\left\lfloor\frac{c}{3}\right\rfloor+1 \\
& =\frac{a-r_{a}}{3}+\frac{b-r_{b}}{3}+\frac{c-r_{c}}{3}+1 \\
& =\frac{n+3-1-r_{n}}{3}+\frac{4+r_{n}-\left(r_{a}+r_{b}+r_{c}\right)}{3} \\
& =\left\lfloor\frac{n+3-1}{3}\right\rfloor+\frac{4+r_{n}-\left(r_{a}+r_{b}+r_{c}\right)}{3} .
\end{aligned}
$$

Since $0 \leq r_{n}, r_{a}, r_{b}, r_{c} \leq 2$, we have that $4+r_{n}-\left(r_{a}+r_{b}+r_{c}\right) \geq 4+0-6=-2$. But since this number is divisible by 3, it is in fact $\geq 0$. This completes the induction.