Задача 4. Тысяча звеньев

Оценка через направления

Считаем только внутренние пересечения звеньев, не общие концы соседних звеньев. Если есть только два перпендикулярных направления, все вершины лежат в квадратной решётке с шагом, равным длине звена. Внутренних пересечений тогда нет: единичные стороны решётки так не пересекаются. В остальных случаях при положительном $k$ должны присутствовать хотя бы две различные пары перпендикулярных направлений.

Почему больше 250 нельзя

Если в каком-то направлении есть звено, ему нужны не меньше $k$ звеньев перпендикулярного направления. Верно и обратно. Две различные пары дают четыре различных направления, в каждом не меньше $k$ звеньев. Следовательно, $4k\le1000$, то есть $k\le250$. Наличие дополнительных направлений только усиливает ограничение.

Строим замкнутую ломаную

Возьмём квадрат со стороной 125 и разделим каждую сторону на 125 отрезков длины 1. Каждый такой отрезок заменим двумя боковыми сторонами равнобедренного треугольника высоты 125, обращённого внутрь квадрата. Идём по этим зигзагам последовательно вокруг четырёх сторон. Получается замкнутая ломаная с $4\cdot125\cdot2=1000$ звеньями. Длина каждого равна $\sqrt{125^2+(1/2)^2}$.

Проверяем число прямоугольных пересечений

Рассмотрим почти вертикальное звено и прямоугольный треугольник его приращений: по горизонтали это $1/2$, по вертикали $125$. У соответствующего почти горизонтального звена приращения по величине меняются местами: $125$ и $1/2$, а наклон направлен в другую сторону. Эти прямоугольные треугольники равны по катетам, поэтому их малые углы равны. Почти вертикальное звено отклонено от вертикали на этот малый угол в одну сторону, а почти горизонтальное — от горизонтали на тот же угол в другую. Между ними ровно $90^\circ$.

Таких перпендикулярных звеньев 125 на левом зигзаге и 125 на правом. Каждое проходит между левой и правой сторонами квадрата, а выбранное — между нижней и верхней; их концы на границе чередуются, поэтому отрезки обязательно пересекаются. Концы не совпадают, следовательно, пересечение внутреннее. Всего 250; для любого другого звена работает поворот того же рисунка.

Проверяем запреты на вершины

Вершины исходных оснований стоят в целых точках границы квадрата, а новые вершины — в полуцелых точках противоположной стороны. Они не совпадают, кроме общего конца соседних звеньев при обходе. Каждое звено внутри квадрата имеет только внутренние точки, а все вершины ломаной находятся на его границе, поэтому вершина не может лежать внутри другого звена. Таким образом, конструкция допустима и достигает оценки 250.