Let $T$ be a triangulation of a $100$-gon.We construct $P(T)$ by copying the same $100$-gon and drawing a diagonal if it was not drawn in $T$ an there is a quadrilateral with this diagonal and two other vertices so that all the sides and diagonals(Except the one we are going to draw) are present in $T$.Let $f(T)$ be the number of intersections of diagonals in $P(T)$.Find the minimum and maximum of $f(T)$.
Problem
Source: Iranian third round 2019 finals Combinatorics exam problem 2
Tags: combinatorics
22.09.2019 00:28
The following solution assumes that the $100-$gon is convex. The maximum and minimum of $f(T)$ are $144$ and $96$ respectively. Before attacking the problem, we will devise a way to count the number of intersections. Consider the graph $G$ on $98$ vertices, with each vertex corresponding to one of the triangles in the triangulation and an edge connecting two vertices if and only if the corresponding triangles share an edge. Observe that $G$ is a tree. Claim. There exists a bijection between pairs of edges in the graph which share a common vertex and intersection points as defined in the problem. Proof. First we will establish the forward direction. Given any two pairs of edges in the graph which share a vertex, let $t_1, t_2, t_3$ be triangles so that $d_1$ corresponds to the pair of triangles $(t_1, t_2)$ and $d_2$ to $(t_2, t_3).$ Then, we have that a diagonal is drawn between a vertex of $t_1$ and a vertex of $t_2$, and a diagonal is drawn between a vertex of $t_2$ and a vertex of $t_3$. Both diagonals are cevians of $t_2$ from distinct vertices of $t_2$, and hence they intersect. On the other hand, consider now two drawn diagonals in $P(T)$ which intersect. If the two diagonals drawn do not correspond to two pairs of triangles which share one triangle, then they are contained in disjoint quadrilaterals. This is absurd. Hence, the other direction is established as well. $\blacksquare$ If we let $d_1, d_2, \cdots, d_{98}$ be the degrees of the vertices of $G$ (where $1 \le d_i \le 3$ for all $1 \le i \le 98$), then the number of pairs of edges sharing a vertex is: $$\sum_{i = 1}^{98} \binom{d_i}{2}.$$ By Jensen, this is minimized when all the $d_i$'s are $1$ and $2$, and maximized when all the $d_i$'s are $1$ and $3$. These imply our desired upper and lower bounds. As for the construction, for the minimum, simply draw all diagonals emanating from one vertex. For the maximum, simply cut off $50$ "ears" and then triangulate the resulting $50-$gon arbitrarily. $\square$