Наименьшее натуральное $k$ в $1001$-угольнике: задача

Пусть $AB = 1$. Рассмотрим выпуклый $1001$-угольник, одна из вершин которого совпадает с $A$, а остальные $1000$ вершин лежат на расстоянии, меньшем $\varepsilon$ от $B$, где $\varepsilon$ достаточно мало. Обозначим через $k + \ell$ общее число диагоналей, равное $\frac{1001 \cdot 998}{2}=499499$. При $k\ge 498501$ сумма длин кратчайших $k$ диагоналей примерно равна $k-498501=998-\ell$, а сумма остальных диагоналей примерно равна $\ell$. Следовательно, $\ell\le 499$ и $k\ge 499000$.

Покажем теперь, что $k = 499000$ удовлетворяет условию. Раскрасим произвольные $\ell=499$ зеленым. Для каждой зеленой диагонали $AB$, кроме, возможно, последней, построим красные диагонали $AC$ и $CB$ так, чтобы ни одна зеленая диагональ не была перекрашена в красный цвет и ни одна диагональ не была покрашена красным дважды.

Пусть для $0 \le i \le 498$ зеленых диагоналей соответствующие красно-зеленые треугольники построены. Рассмотрим очередную зеленую диагональ $AB$. Пусть $D$ – множество всех диагоналей с концами $A$ и $B$, отличных от $AB$; тогда $|D|=2\cdot 997=1994$. Каждый красно-зеленый треугольник имеет не больше двух сторон в $D$. Значит подмножество $E$ непокрашенных диагоналей из $D$ содержит не меньше $1994-2i$ элемента.

При $i\le 497$ имеем $1994-2i\ge 1000$. Общее число вершин, отличных от $A$ и $B$, равно $999$. Следовательно найдутся две диагонали из $E$ с общим концом $C$ и мы можем покрасить красным диагонали $AC$ и $CB$.

Осталось рассмотреть случай $i = 498$. Предположим, что никакие две диагонали из $E$ не имеют общих концов, отличных от $A$ и $B$. Тогда найдутся две диагонали из $E$, которые пересекаются. Действительно, в противном случае одна (назовем ее $a$) из двух соседних с $A$ вершин отделена от $B$ диагоналями, выходящими из $A$, и одна (назовем ее $b$) из двух соседних с $B$ вершин отделена от $A$ диагоналями, выходящими из $B$ (при этом $a \neq b$). Тогда у нас есть не больше $997$ подходящих вершин и не меньше $998$ диагоналей из $E$ – противоречие.

Для завершения доказательства осталось воспользоваться неравенством треугольника.