
C6

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?


## Solution

Let $P Q=1$. Consider a convex 101 -gon such that one of its vertices is at $P$ and the remaining 100 vertices are within $\varepsilon$ of $Q$ where $\varepsilon$ is an arbitrarily small positive real. Let $k+l$ equal the total number $\frac{101 \cdot 98}{2}=4949$ of diagonals. When $k \leq 4851$. the sum of the $k$ shortest diagonals is arbitrarily small. When $k \geq 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 \leq 49$ and $k \geq 4900$.

We proceed to show that $k=4900$ works. To this end, colour all $l=49$ remaining diagonals green. To each green diagonal $A B$, apart from, possibly, the last one, we will assign two red diagonals $A C$ and $C B$ 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 \leq i \leq 48$ green diagonals (thus forming $i$ redred-green triangles) and let $A B$ be up next. Let $D$ be the set of all diagonals emanating from $A$ or $B$ and distinct from $A B$ : 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-yetuncoloured diagonals in $D$ contains at least $194-2 i$ elements.

When $i \leq 47,194-2 i \geq 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 $A C$ and $C B$ to $A B$. 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 \neq 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.

![](https://cdn.mathpix.com/cropped/2024_06_04_7ba2ee0958b01972332bg-48.jpg?height=651&width=590&top_left_y=2100&top_left_x=1567)

# Union of Mathematicians of Macedonia 

Sponsored by

![](https://cdn.mathpix.com/cropped/2024_06_04_7ba2ee0958b01972332bg-48.jpg?height=393&width=802&top_left_y=4463&top_left_x=1471)

