[ Cutting into parts with special properties ] $\left[\begin{array}{cc}\text { K } & \text { Combinatorial geometry (other) }\end{array}\right]$

A convex $N$-gon is divided by diagonals into triangles (with the diagonals not intersecting inside the polygon). The triangles are colored black and white such that any two triangles sharing a side are colored differently. For each $N$, find the maximum difference between the number of white and the number of black triangles.
First, let's evaluate the value of the difference (we will provide two methods).

First method. When dividing into triangles using diagonals, we get \(N-2\) triangles (see problem 58154). Each of the \(N-3\) diagonals is adjacent to a black triangle, so there are at least \(\frac{1}{3}(N-3)\) black triangles. Therefore, the number of white triangles is no more than \(N-2 - \left(\frac{N}{3} - 1\right) = \frac{2N}{3} - 1\), and the desired difference is no more than \(\frac{2N}{3} - 1 - \left(\frac{N}{3} - 1\right) = \frac{N}{3}\).

In the case of \(N = 3k + 1\), the number of black triangles is at least \(k\) (as the integer greater than \(\frac{1}{3}(N-3) = k - \frac{2}{3}\)), and the difference, accordingly, is no more than \(N-2 - 2k = k-1\).

Second method. The number of sides of white triangles does not exceed the number of sides of black triangles by more than \(N\), since the number of sides inside the polygon is the same, and there are \(N\) sides on the boundary. Therefore, the difference in the number of white and black triangles does not exceed \(\frac{N}{3}\). In the case of \(N = 3k + 1\), note that the parity of this difference is the same as the parity of the sum, i.e., the parity of the number \(N\) (and, therefore, the difference cannot equal \(k\)).

Now, let's provide examples showing that the required values of the difference are achievable. For \(N = 3, 4, 5\), these values are 1, 0, and 1; the examples are obvious, and in each, there is a white triangle adjacent to a side of the \(N\)-gon. It remains to note that when the number of sides increases by three, the value of the difference can increase by 1, by replacing one of these adjacent white triangles with a hexagon, cut as shown in the figure:
![](https://cdn.mathpix.com/cropped/2024_05_06_7e3e695203bdf41f05f0g-17.jpg?height=422&width=972&top_left_y=1809&top_left_x=543)

## Answer

\(k\) for \(N = 3k\) and \(N = 3k + 2\), \(k-1\) for \(N = 3k + 1\).

Submit a comment