Problem 2166

Solution:

For $n=3$ the answer is $6$. Suppose $n \geqslant 4$. It is obvious that in each triangulation there are at least two triangles that share two sides with the polygon. We will prove that it is always best for Mary to choose a triangulation for which there is no more than two triangles of this kind.

We call a triangle in a triangulation bad if all of its sides are diagonals of the polygon. First we prove that Mary can choose an optimal triangulation that contains no bad triangles. Assume on the contrary that every optimal triangulation contains a bad triangle. For an optimal triangulation $\mathcal{T}$ let $d(\mathcal{T})$ be the length of the smallest side of all bad triangles in $\mathcal{T}$. Among all optimal triangulations with minimal number of bad triangles let $\mathcal{T}_0$ be such that $d\left(\mathcal{T}_0\right)$ is minimal.

Consider a bad triangle $ABC$ in $\mathcal{T}_0$ such that $|AB|=d\left(\mathcal{T}_0\right)$. Let $ABD$ be the other triangle of $\mathcal{T}_0$ that contains $\overline{AB}$ as one of its sides. Since $D$ lies on the arc $\text{AB}$ of the circumcircle of $ABC$ that does not contain $C$ and $\angle ACB$ is acute, we have $|AD|<|AB|$ and $|BD|<|AB|$.

Let $\mathcal{T}_1$ be the triangulation obtained from $\mathcal{T}_0$ by replacing $\overline{AB}$ with $\overline{CD}$. If the sides $\overline{AD}$ and $\overline{BD}$ have labels $a$ and $b$ respectively, then
$$S\left(\mathcal{T}_1\right)-S\left(\mathcal{T}_0\right)=a+b-ab-1=-(a-1)(b-1) \leqslant 0$$
Because $\mathcal{T}_0$ is optimal triangulation, we conclude that $\mathcal{T}_1$ is also optimal. Since $\mathcal{T}_0$ has the minimal number of bad triangles at least one of the segments $\overline{AD}$ and $\overline{BD}$ should be a diagonal, but then $d\left(\mathcal{T}_1\right)$ is less than $d\left(\mathcal{T}_0\right)$ what is a contradiction.

Now that we know that Mary can choose an optimal triangulation that contains no bad triangles, we easily conclude that in such a triangulation there are exactly two triangles that share two sides with the polygon. If we denote by $x_1$ (respectively $x_2$) the number of triangles that have exactly one (respectively two) of their sides being the sides of the polygon, then $x_1+x_2=n-2$ and $x_1+2x_2=n$, so $x_2=2$.

Mary's strategy is to choose these two triangles so that the side of the polygon labeled with $1$ is contained in one of these triangles and the side labeled with $2$ is contained in the other.

By this strategy Mary makes sure that
$$\text{S n(n+1) 2 -(1+2+n+n-1)+1 n+2 (n-1), n(n+1) 2 -(1+2+n+n-1)+1 (n-1)+2 n = n 2+3n-6 2}$$

On the other hand, John can force Mary to achieve exactly this bound by labeling the sides of the polygon in the following order
$$1, n-1, 4, n-3, 5, \ldots, n-2, 3, n, 2$$

Thus, the answer to our problem is $S=\frac{n^2+3n-6}{2}$, for each $n \geqslant 3$.