37th Iranian Mathematical Olympiad

Call two triangles in $T$ adjacent if they share an edge. First note that for any diagonal $d$ drawn in $P(T)$, there are two adjacent triangles of $T$ such that $d$ is drawn in $P(T)$, because of the quadrilateral formed by these triangles. We call them $d$'s triangles. Assume that two diagonals $d_1,d_2$ intersect in $P(T)$. Because the diagonals of the triangulation do not intersect, we can easily find three triangles $t_1,t_2,t_3$ of $T$ such that $t_1,t_2$ are $d_1$'s triangles and $t_2,t_3$ are $d_2$'s triangles. On the other hand, for any three triangles $t_1,t_2,t_3$ of $T$ that $t_2$ is adjacent to $t_1,t_3$, we can find a pair of intersecting diagonals in $P(T)$.

Now construct a graph $G$ of 98 vertices with each vertex corresponding to one of the triangles in $T$ and an edge connecting two vertices if and only if the corresponding triangles are adjacent. Clearly, there are 97 edges in $G$ (equal to the number of diagonals in $T$). So if we let $d_1,d_2,\dots ,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 in the graph sharing a vertex is: $$\sum _{i=1}^{98}\left(\genfrac{}{}{0ex}{}{d_i}{2}\right)$$ Let $r,s,t$ be the number of vertices with degree 1, 2, 3, respectively. Obviously $r+s+t=98$. Also we have ${\sum }_{i=1}^{98}{d}_i=2\times 97=r+2s+3t$. Note that ${\sum }_{i=1}^{98}\left(\genfrac{}{}{0ex}{}{d_i}{2}\right)=s+3t$. So we can conclude that $$f(T)=\sum _{i=1}^{98}\left(\genfrac{}{}{0ex}{}{d_i}{2}\right)=r+4\times 97-3\times 98=r+94.$$ Any vertex of degree 1 in $G$, corresponds to a triangle of the triangulation that shares 2 edges with the 100-gon. So $r\le 50$. On the other hand, we can easily prove by induction that $2\le r$. So $96\le r+94\le 144$. As for the construction, for the minimum, simply draw all diagonals going from one vertex. For the maximum, simply cut off 50 triangles sharing 2 edges with the 100-gon and then triangulate the resulting 50-gon arbitrarily.