What is the least positive integer $k$ such that, in every convex $101$-gon, the sum of any $k$ diagonals is greater than or equal to the sum of the remaining diagonals?
Problem
Source: Balkan BMO Shortlist 2017 C6
Tags: combinatorics, combinatorial geometry, diagonals, minimum, Balkan MO Shortlist
27.09.2019 17:55
Bump....
27.09.2019 22:04
The answer is $k=4900$. In the convex $101$-gon, there are $49*101$ diagonals. Consider this problem with respect to how many diagonals we 'leave'. I claim that $49$ is the most diagonals we can leave. Suppose we were able to leave 50 diagonals. Consider the polygon with one vertex very far, and the remaining $100$ very 'close' to each other, so their distance is practically neglegible. Take all diagonals except for $50$ of the 'long' diagonals, ones which go from the far vertex to the other points. One can see this as a counterexample for $k=4899$. Now we will show that $k=4900$ suffices. Consider the longest diagonal $AB$, and let $AB$ have length $m$. Thus, we choose all except $49$ diagonals. The total length of the remaining diagonals combined, say $r$, satisfies $r \leq 49m$ by our assumption. Consider all the diagonals. Let the other $99$ points be $c_1,c_2,...c_{99}$ and assume that $c_1, c_2$ are the neighbours of $A$ on the convex polygon and similarly $B$, has neighborhood $c_{98},c_{99}$, assuming the worst case when none of the neighbours coincidence. So we can see by triangle inequality that $Ac_i+c_iB \geq AB$ and $Ac_i, c_iB$ are diagonals for all $3 \leq i \leq 97$. Assume that $c_1, c_{98}$ are on one side of AB, and the remaining two $c_2, c_{99}$, we can do so WLOG. Note that, due to convexity, $c_{98}A+Bc_1 \geq AB$ and also $Ac_{99}+Bc_2 \geq AB$, all this comes by triangle inequality. So upon adding the lengths of all the diagnosis, we can see that the sum is at least $(95+2+1)m=98m$ and leaving any $49$ of them reduces the sum by at most $49m$, so the sum of the remaining diagonals is always greater than or equal to $49$, so $k=4900$ is the answer.