Условие
Внутри квадрата со стороной 1 расположено n2
точек. Докажите, что существует ломаная, содержащая все эти точки,
длина которой не превосходит 2n.
Решение
Разобьем квадрат на n вертикальных полосок, содержащих
по n точек каждая. Точки внутри каждой полосы соединим сверху
вниз и получим n ломаных. Эти ломаные можно соединить в одну
ломаную двумя способами (рис., а и б).
Рассмотрим отрезки, соединяющие разные полосы. Объединение
всех таких отрезков, полученных обоими способами,
представляет собой пару ломаных, причем сумма длин
горизонтальных проекций звеньев каждой из них не
превосходит 1. Поэтому сумма длин горизонтальных проекций
соединяющих отрезков для одного из способов не
превосходит 1. Рассмотрим именно это соединение. Сумма
длин
горизонтальных проекций для соединяющих звеньев не
превосходит 1, а для всех остальных звеньев не
превосходит
(n - 1)(h1 + ... + hn), где hi —
ширина i-й полосы. Ясно, что
h1 + ... + hn = 1. Сумма
вертикальных проекций всех звеньев ломаной не
превосходит n. В итоге получаем, что сумма вертикальных и
горизонтальных проекций всех звеньев не
превосходит
1 + (n - 1) + n = 2n, поэтому и длина ломаной не
превосходит 2n.
Источники и прецеденты использования
