Задача 57366

Тема:    [ Ломаные внутри квадрата ]

Сложность: 5 Классы: 8,9

Условие

Внутри квадрата со стороной 1 расположено n² точек. Докажите, что существует ломаная, содержащая все эти точки, длина которой не превосходит 2n.

Решение

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

Источники и прецеденты использования

книга
Автор	Прасолов В.В.
Год издания	2001
Название	Задачи по планиметрии
Издательство	МЦНМО
Издание	4*
глава
Номер	9
Название	Геометрические неравенства
Тема	Геометрические неравенства
параграф
Номер	8
Название	Ломаные внутри квадрата
Тема	Ломаные внутри квадрата
задача
Номер	09.060