Problem 2133

Consider an arbitrary set of diagonals satisfying the conditions. Label the sides of the $n$-gon with number 1. The diagonals partition the $n$-gon into triangles; let $\Delta$ be a triangle that contains the centroid of the $n$-gon. Let $s, t, u$ be the labels of the sides of $\Delta$ (Fig. 26). The triangle $\Delta$ divides the interior of the $n$-gon outside $\Delta$ into three regions each bounded by one side of $\Delta$ and the respective sides of the $n$-gon (if a side of the $n$-gon coincides with a side of $\Delta$ then the respective region contains 0 triangles).

Fig. 26

As all triangles that are cut out are on the same side of the centroid of the polygon, the label of the longest side of each triangle equals the sum of labels on the two shorter sides. Cutting out a triangle removes two sides from the boundary of the region and introduces a new side labeled with the sum of the removed sides. Therefore, the sum of the labels on the boundary of the region is constant during the process. Let $m_i$ be the greatest number on the boundary of the region after $i$ triangles have been removed. As the boundary is initially labeled with $s$ ones and in every step the number of sides is reduced by one then after $i$ steps there are $s-i$ sides remaining. Therefore $s \ge m_i + (s-i-1)$ from which $m_i \le i+1$. On the other hand, the label of the diagonal $d_i$ along which the cut is made on the $i$-th step satisfies $d_i \le m_i$. Hence the sum of all labels of the diagonals in this region (including the side of $\Delta$ labeled with $s$) is not greater than $2+3+...+s$.
As the same is valid for the remaining two regions, the total sum of labels does not exceed $(2+3+...+s) + (2+3+...+t) + (2+3+...+u)$. We know $s+t+u=n$; w.l.o.g., $\frac{n}{2} \ge s \ge t \ge u \ge 1$. If $u>1$ then $t < \lfloor \frac{n}{2} \rfloor$, whence a new triple $(s', t', u')$ with $u' = u-1$ also satisfies conditions: Replace $t$ with $t+1$ and change the order of $s$ and $t+1$ if needed. The total sum increases since $t+1 > u$. In the case of $u=1$, the only possibility is $s=t=\frac{n-1}{2}$ if $n$ is odd and $s=\frac{n}{2}, t=\frac{n}{2}-1$ if $n$ is even. Hence the total sum of labels does not exceed $2 \cdot \left(2+3+...+\frac{n-1}{2}\right) = \frac{n^2-9}{4}$ for odd $n$ and $\left(2+3+...+\left(\frac{n}{2}-1\right)\right) + \left(2+3+...+\frac{n}{2}\right) = \frac{n^2-8}{4}$ for even $n$. These sums can be achieved by drawing all diagonals connecting a fixed vertex with all non-neighboring vertices.

Solution 2:

Call the minimal number of sides of the $n$-gon between the endpoints of a given diagonal its length. The parts of the $n$-gon that a diagonal divides it into are called short flank and long flank (if the parts contain the same number of sides then both may be called short and long flank).

For every positive integer $k$, let $a_k$ be the number of drawn diagonals whose length is at least $k$. Note that the sum of lengths of all drawn diagonals is $a_1 + a_2 + \dots + a_{\lfloor \frac{n}{2} \rfloor}$. Indeed, represent all lengths of diagonals in the form $1+1+\dots+1$; aligning the sums left, the $k$th column from the left contains exactly $a_k$ ones and there are $\lfloor \frac{n}{2} \rfloor$ non-empty columns in total.
We prove that, for every $k \ge 2$, $a_k \le n - 2k + 1$. The claim holds for $k = \frac{n}{2}$ since all diagonals of length $\frac{n}{2}$ intersect in the centroid of the $n$-gon. Assume in the rest that $k < \frac{n}{2}$. Let $M$ be an arbitrary set of non-intersecting diagonals with length at least $k$ which cannot be extended by any other such diagonal without introducing an intersection. Let $d$ be the longest diagonal in $M$. Clearly $M$ contains a diagonal of length $k$ in the long flank of $d$, otherwise one could add a new diagonal of length $k$ to the short flank of the shortest diagonal in the long flank of $d$. If the length of $d$ is greater than $k$ then $M$ contains a diagonal of length $k$ also in the short flank of $d$. Hence $M$ contains at least 2 diagonals of length $k$. In the short flanks of these diagonals, there are $2(k-1)$ vertices not connected by any diagonals of $M$. The remaining $n - 2k + 2$ vertices can be joined by at most $n - 2k + 1$ non-intersecting diagonals, implying $a_k \le n - 2k + 1$.
As $a_1 = n - 3 = (n - 1) - 2$, the sum of the lengths of all drawn diagonals is at most $((n - 1) + (n - 3) + \dots + (n - 2 \lfloor \frac{n}{2} \rfloor + 1)) - 2$. This simplifies to $\frac{n^2-8}{4}$ in the case of even $n$ and to $\frac{n^2-9}{4}$ in the case of odd $n$. If one draws all diagonals from a fixed vertex to the non-neighboring vertices then $a_k = n - 2k + 1$ for every $k = 2, 3, \dots, \lfloor \frac{n}{2} \rfloor$. Hence the bounds found above are achieved.

Solution 3:

Define the notions length, short flank and long flank as in Solution 2. We show by induction that the sum of lengths of any diagonal $d$ and all diagonals in the short flank of $d$ does not exceed $2+3+\dots+s$, where $s$ is the length of $d$. The claim holds for $s=2$ since there are no diagonals in the short flank of a diagonal of length 2. Assume now that the claim holds for diagonals shorter than $d$. Let $d'$ of length $s'$ be the longest diagonal drawn in the short flank of $d$. By the induction hypothesis, the sum of lengths of the diagonal $d'$ and all diagonals in the short flank of $d'$ does not exceed $2+3+\dots+s'$. As there are exactly $s-2$ diagonals drawn in the short flank of $d$ and exactly $s'-2$ of them are in the short flank of $d'$, the number of diagonals that lie in the short flank of $d$ and also in the long flank of $d'$ must be $s-s'-1$. By the choice of $d'$, the sum of lengths of these diagonals is at most $s'(s-s'-1)$ which does not exceed $(s'+1)+\dots+(s-1)$ (the equality holds in the case $s'=s-1$). Consequently, the sum of lengths of diagonal $d$ and all diagonals in the short side of $d$ does not exceed $2+3+\dots+s$. This completes the proof of the claim.
Now let $d$ of length $s$ be the longest drawn diagonal. Let $d'$ of length $s'$ be the longest diagonal in the long flank of $d$. By the claim proven above, the sum of lengths of the diagonal $d$ and all diagonals in the short flank of $d$ does not exceed $2+3+...+s$ and the sum of lengths of the diagonal $d'$ and all diagonals in the short flank of $d'$ does not exceed $2+3+...+s'$. The total number of these diagonals is $(s-1)+(s'-1)$. As $n-3$ diagonals are drawn, the number of diagonals lying in the long flank of both $d$ and $d'$ is $n-s-s'-1$. By the choice of $d$ and $d'$, the sum of lengths of these diagonals is at most $s'(n-s-s'-1)$ that does not exceed $((s+1)+...+\lfloor\frac{n}{2}\rfloor)+((s'+1)+...+\lfloor\frac{n-1}{2}\rfloor)$. Thus the sum of lengths of all drawn diagonals is $(2+3+...+\lfloor\frac{n}{2}\rfloor)+(2+3+...+\lfloor\frac{n-1}{2}\rfloor)$ which simplifies to $\frac{n^2-8}{4}$ in the case of even $n$ and $\frac{n^2-9}{4}$ in the case of odd $n$. These bounds are achieved as the sum of lengths of diagonals drawn from a fixed vertex to all non-neighboring vertices equals $(2+3+...+\lfloor\frac{n}{2}\rfloor)+(2+3+...+\lfloor\frac{n-1}{2}\rfloor)$.

Solution 4:

Define the notions length, short flank and long flank as in Solution 2. Consider any set of diagonals with the maximal sum of lengths.
Suppose initially that, in the partition of the $n$-gon into triangles, there exists a triangle $ABC$ whose all sides are diagonals of the $n$-gon; let the lengths of $BC$, $CA$ and $AB$ be $a, b, c$, respectively. W.l.o.g., $a \le b \le c$. Then $AB$ and $AC$ lie in the long flank of $BC$ (otherwise $a = b+c$). Let $BCD$ be the triangle of the partition in the short flank of $BC$ (Fig. 27) and let the length of $AD$ be $d$. Among the diagonals $AB$ and $AC$, the one that lies in the short side of $AD$ is shorter than $AD$, implying that $d > b$ or $d > c$. In either

Fig. 27

case, $d > a$. Thus replacing $BC$ with $AD$ in the partition leads to a larger sum of lengths. This contradicts the assumption.
Consequently, each triangle of the partition has at least one side that is a side of the $n$-gon. This means that, starting from any drawn diagonal $d_1$ of length 2, we can find a diagonal $d_2$ with a common endpoint with $d_1$, then a new diagonal $d_3$ with a common endpoint with $d_2$ etc., in such a way that the lengths of the diagonals increase with step 1 until $\lfloor\frac{n}{2}\rfloor$ and after that decrease with step 1. Hence the sum of lengths of all diagonals is at most $2 \cdot (2+3+...+\frac{n-1}{2}) = \frac{n^2-9}{4}$ for odd $n$ and at most $2 \cdot (2+3+...+(\frac{n}{2}-1)) + \frac{n}{2} = \frac{n^2-8}{4}$ for even $n$. The proof immediately gives a construction that achieves the bounds.

Solution 5:

Label each side of the $n$-gon with number 1. If the polygon with at least 5 sides is partitioned into triangles using non-intersecting diagonals then at least two triangles have two sides on the boundary of the polygon. After removing two such triangles, we can repeat the procedure in the remaining polygon. After repeating the procedure $k$ times, the remaining polygon has exactly $n-2k$ sides since at each step a new side appears instead of two sides at two places. The sum of labels of the sides of the remaining polygon is $n$ or less since every cut replaces two sides with a diagonal with label not greater than the sum of the labels of the two sides.
Consider arbitrary 4 sides in the polygon remaining after $k$ steps. As the sum of labels of the other $n-2k-4$ sides is at least $n-2k-4$, the sum of labels of the chosen 4 sides is at most $2k+4$. Hence the labels of the diagonals along which the two cuts are made in the next step sum up to at most $2k+4 = 2(k+2)$. Using this argument for $k=0,1,\dots, \frac{n-1}{2}-2$ in the case of odd $n$, we conclude that the sum of labels of the drawn diagonals, for odd $n$, does not exceed $2 \cdot (2+3+\dots+\frac{n-1}{2}) = \frac{n^2-9}{4}$. Similarly for even $n$, the sum of labels of $n-4$ drawn diagonals does not exceed $2 \cdot (2+3+\dots+(\frac{n}{2}-1)) = \frac{n^2}{4} - \frac{n}{2} - 2$. As the label of the last diagonal is at most $\frac{n}{2}$, the total sum of labels is at most $\frac{n^2-8}{4}$. The sums are achieved by drawing diagonals from a fixed vertex to all non-neighboring vertices.