Baltic Way 2010 · Problem 10

$\lfloor \frac{n-1}{3} \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) \le \lfloor \frac{n-1}{3} \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 $\lfloor \frac{n-1}{3} \rfloor$ black triangles. We can then color the 5-gon compatibly with only one black triangle so $f(n+3) \le \lfloor \frac{n-1}{3} \rfloor + 1 = \lfloor \frac{n+3-1}{3} \rfloor$.

Now we prove by induction that $f(n) \ge \lfloor \frac{n-1}{3} \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) &\ge f(a+1) + f(b+1) + f(c+1) + 1 \\ &\ge \lfloor \frac{a}{3} \rfloor + \lfloor \frac{b}{3} \rfloor + \lfloor \frac{c}{3} \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-(r_a+r_b+r_c)}{3} \\ &= \lfloor \frac{n+3-1}{3} \rfloor + \frac{4+r_n-(r_a+r_b+r_c)}{3}. \end{aligned}$$

Since $0 \le r_n, r_a, r_b, r_c \le 2$, we have that $4+r_n-(r_a+r_b+r_c) \ge 4+0-6 = -2$. But since this number is divisible by 3, it is in fact $\ge 0$. This completes the induction.

Call two triangles neighbours if they have a common side. Let the dissections of convex $n$-gons together with appropriate colourings be called n-colourings.

Observe that all triangles of an arbitrary $n$-colouring can be listed, starting with an arbitrary triangle and always continuing the list by a triangle that is a neighbour to some triangle already in the list. Indeed, suppose that some triangle $\Delta$ is missing from the list. Choose a point $A$ inside a triangle in the list, as well as a point $D$ inside $\Delta$. By convexity, the line segment $AD$ is entirely inside the polygon. As the vertices of the triangles are vertices of the polygon, $AD$ crosses the sides of the triangles only outside their vertices. Hence any consecutive triangles that $AD$ passes through are neighbours. The first triangle that ray $AD$ visits and that is not in the list is one that the list can be continued with.

Consider such a list of all triangles that starts with a white triangle. Each triangle has at most three neighbours and each black triangle has at least one neighbour occurring in the list before it. Thus at most two neighbours of any black triangle are following it in the list. Each white triangle except for the first one is a neighbour of some triangle preceding it in the list, and according to the construction, that triangle is black. Hence among all triangles except for the first one, there are at most twice as many white triangles as there are black triangles. Altogether, this means $w \le 2b+1$ where $b$ and $w$ are the numbers of black and white triangles in the construction, respectively. Observe that this formula holds also if there are no white triangles.

Hence there are at most $3b + 1$ triangles altogether, i.e., $n - 2 \le 3b + 1$. In integers, this implies $b \ge \lfloor \frac{n}{3} \rfloor - 1$ which is equivalent to $b \ge \lfloor \frac{n-1}{3} \rfloor$.

This number of black triangles can be achieved as follows. Number all vertices of the polygon by 0 through $n-1$.

If $n = 3k, k \in \mathbb{Z}^+$, then draw diagonals $(0, 3i - 1)$, $(3i - 1, 3i + 1)$, $(3i + 1, 0)$ for all $i = 1, \dots, k - 1$. Colour black every triangle whose vertices are $0, 3i - 1$ and $3i + 1$ for some $i = 1, \dots, k - 1$.

If $n = 3k - 1$ or $n = 3k - 2$ then take a described $3k$-colouring and cut out 1 or 2 white triangles, respectively (e.g., triangles with vertices 0, 1, 2 and 0, $n-1$, $n-2$).