BMO 2017

Let $PQ=1$. Consider a convex $101$-gon such that one of its vertices is at $P$ and the remaining $100$ vertices are within $\epsilon$ of $Q$ where $\epsilon$ is an arbitrarily small positive real. Let $k+l$ equal the total number $\frac{101\cdot 98}{2}=4949$ of diagonals. When $k\le 4851$, the sum of the $k$ shortest diagonals is arbitrarily small. When $k\ge 4851$, the sum of the $k$ shortest diagonals is arbitrarily close to $k-4851=98-l$ and the sum of the remaining diagonals is arbitrarily close to $l$. Therefore, we need to have $l\le 49$ and $k\ge 4900$.

We proceed to show that $k=4900$ works. To this end, colour all $l=49$ remaining diagonals green. To each green diagonal $AB$, apart from, possibly, the last one, we will assign two red diagonals $AC$ and $CB$ so that no green diagonal is ever coloured red and no diagonal is coloured red twice.

Suppose that we have already done this for $0\le i\le 48$ green diagonals (thus forming $i$ red-red-green triangles) and let $AB$ be up next. Let $D$ be the set of all diagonals emanating from $A$ or $B$ and distinct from $AB$: we have $|D|=2\cdot 97=194$. Every red-red-green triangle formed thus far has at most two sides in $D$. Therefore, the subset $E$ of all as-of-yet-uncoloured diagonals in $D$ contains at least $194-2i$ elements.

When $i\le 47$, $194-2i\ge 100$. The total number of endpoints distinct from $A$ and $B$ of diagonals in $D$, however, is $99$. Therefore, two diagonals in $E$ have a common endpoint $C$ and we can assign $AC$ and $CB$ to $AB$, as needed.

The case $i=48$ is slightly more tricky: this time, it is possible that no two diagonals in $E$ have a common endpoint other than $A$ and $B$, but, if so, then there are two diagonals in $E$ that intersect in a point interior to both. Otherwise, at least one (say, $a$) of the two vertices adjacent to $A$ is cut off from $B$ by the diagonals emanating from $A$ and at least one (say, $b$) of the two vertices adjacent to $B$ is cut off from $A$ by the diagonals emanating from $B$ (and $a\ne b$). This leaves us with at most $97$ suitable endpoints and at least $98$ diagonals in $E$, a contradiction.

By the triangle inequality, this completes the solution.