Zakorko P.

Karabas-Barabas has a large plot of land in the shape of a convex $\$ 12 \$$-sided polygon, with lanterns at each vertex. Karabas-Barabas needs to place a finite number of lanterns inside the plot, divide it into triangular plots with vertices at the lanterns, and distribute these plots to the actors of the theater. Each internal lantern must illuminate at least six triangular plots (the lanterns have a short range, illuminating only the plots where they are at the vertices). What is the maximum number of triangular plots that Karabas-Barabas can distribute to the actors?
It is not difficult to provide an example in which there are $\$ 24 \$$ such plots:

![](https://cdn.mathpix.com/cropped/2024_05_06_f68ab0b4ba9161e79ed2g-03.jpg?height=632&width=640&top_left_y=1622&top_left_x=709)

Let's try to prove that it is not possible to have more than $\$ 24 \$$ plots. First, consider a more general situation: let there be an $\$ n \$$-sided polygon with lanterns at the vertices, which is divided into triangular plots, and from each internal vertex (if they exist) at least $\$ 6 \$$ segments emanate.

We will paint the vertices of the polygon blue, and all internal vertices - red. We will also paint blue all triangles that have at least one blue vertex (an example of such coloring is shown in the figure below).

![](https://cdn.mathpix.com/cropped/2024_05_06_f68ab0b4ba9161e79ed2g-04.jpg?height=766&width=1026&top_left_y=0&top_left_x=516)

**Claim 1.** The number of blue triangles is no more than $\$ 2 n-6 \$$.

At each internal (red) vertex, the sum of at least $\$ 6 \$$ angles is $\$ 360^\circ \$$, which means that on average an angle with a red vertex is less than $\$ 60^\circ \$$, since the average value of all angles of triangles is $\$ 180^\circ / 3 = 60^\circ \$$, so an angle with a blue vertex is on average greater than $\$ 60^\circ \$$.

Since the sum of the angles with blue vertices is equal to the sum of the angles of the $\$ n \$$-sided polygon, which is $\$ 180^\circ (n-2) \$$, the number of blue angles is no more than $\$ 180^\circ (n-2) / 60^\circ = 3(n-2) \$$.

Each side of the polygon is a side of two angles; we will strike out from these angles those that are later in the clockwise direction (on the figure, such angles are marked in red).

![](https://cdn.mathpix.com/cropped/2024_05_06_f68ab0b4ba9161e79ed2g-04.jpg?height=475&width=389&top_left_y=1169&top_left_x=846)

After this, in each blue triangle, at least one blue angle will remain unstruck, but the total number of blue angles will not exceed $\$ 3(n-2) - n = 2n - 6 \$$.

Thus, the number of blue triangles is no more than $\$ 2n - 6 \$$.

**Claim 2.** If there is at least one red vertex inside the $\$ n \$$-sided polygon, then there are at least $\$ n \$$ triangles that have at least two blue vertices.

Consider the triangles adjacent to the sides of the $\$ n \$$-sided polygon (each of which has at least two blue vertices, which are the endpoints of this side). If a separate triangle is adjacent to each side, then there are exactly $\$ n \$$ such triangles (and possibly there are other triangles with two blue vertices) - the claim is proved. Otherwise, there is a triangle that contains exactly two sides of the polygon (it cannot contain three sides: this would mean that the polygon itself is a triangle with no red points inside). Cut off this triangle; the remaining part is an $\$ (n-1) \$$-sided polygon with blue vertices, which still has at least one red vertex inside, and all triangles with at least one blue vertex are painted blue.
![](https://cdn.mathpix.com/cropped/2024_05_06_f68ab0b4ba9161e79ed2g-04.jpg?height=474&width=942&top_left_y=2224&top_left_x=382)

In the $\$ (n-1) \$$-sided polygon, either a separate triangle is adjacent to each side, or there is a triangle whose two sides are sides of the polygon. In the first case, we have found $\$ n-1 \$$ suitable triangles, and one more triangle was cut off in the previous step - so in the original $\$ n \$$-sided polygon, there were at least $\$ n \$$ triangles with two blue vertices. In the second case, we cut off this triangle again and continue the same process, obtaining an $\$ n-k \$$-sided polygon and $\$ k \$$ cut-off triangles on each new step. The process will eventually stop because the number of sides decreases; in total, with the cut-off triangles, we will get $\$ n \$$ triangles with at least two blue vertices. Thus, Claim 2 is proved.

Now consider the part of the polygon that is not painted blue (it can consist of one or several polygons).

**Claim 3.** The total number of sides of the unpainted parts does not exceed $\$ n-6 \$$.

Note that a side of an unpainted part is a segment with endpoints at red vertices, which is also a side of a blue triangle (exactly one). In a blue triangle with such a side, exactly one vertex is blue. According to Claim 1, there are no more than $\$ 2n-6 \$$ blue triangles, and according to Claim 2, at least $\$ n \$$ of them have two (or all three) blue vertices. Therefore, the number of sides of the unpainted part, as well as the number of blue triangles with one blue vertex, does not exceed $\$ 2n-6-n=n-6 \$$.

Now consider the $\$ 12 \$$-sided polygon from the problem. In it, according to Claim 1, there are no more than $\$ 12 \cdot 2 - 6 = 18 \$$ blue triangles. The remaining, unpainted, part (or parts) has a total of no more than $\$ 12-6=6 \$$ sides. Discard the blue triangles and consider the unpainted part separately: again paint blue all vertices on its boundary (or boundaries), as well as paint blue triangles that now have at least one blue vertex. Since $\$ 6-6=0 \$$, all triangles will be painted. According to Claim 1, the number of blue triangles is no more than $\$ 2 \cdot 6 - 6 = 6 \$$.

Thus, the total number of triangles in the partition of the $\$ 12 \$$-sided polygon can be no more than $\$ 18+6=24 \$$.

## Answer

24.