|
|
 |
Условие
Квадрат разбит на n² равных квадратиков. Про некоторую ломаную известно, что она проходит через центры всех квадратиков (ломаная может пересекать сама себя). Каково минимальное число звеньев у этой ломаной?
Решение
На рисунке показан пример такой восьмизвенной ломаной для n = 5. Она состоит из известного обхода девяти точек четырёхзвенной ломаной и раскручивающейся спирали.
Очевидно, что продолжая раскрутку спирали, мы получим пример (2n–2)-звенной ломаной для любого n.
Докажем, что меньшим числом звеньев не обойтись. Пусть через центры квадратиков проходят l горизонтальных и m вертикальных звеньев.
Если l ≥ n, то (так как горизонтальные звенья не могут быть соседними) число звеньев не меньше чем n + (n – 1) = 2n – 1.
Если l = n – 1, то оcтался горизонтальный ряд из n точек, не лежащих на горизонтальных звеньях. Нужно не менее n негоризонтальных звеньев, чтобы "покрыть" эти точки, и число звеньев снова не меньше 2n – 1.
Наконец, пусть l, m ≤ n – 2. Удалим все точки (центры квадратиков), лежащие на прямых, проходящих через горизонтальные и вертикальные звенья. Остался "прямоугольник" из (n – l)(n – m) точек. На его "границе" лежит 2(n – l – 1) + 2(n – m – 1) точек. Любое наклонное звено ломаной содержит не более двух "граничных" точек, то есть таких звеньев не меньше 2n – l – m – 2. Итого в ломаной не менее l + m + (2n – l – m – 2) = 2n – 2 звеньев.
Ответ
2n – 2 звена.
Замечания
1. Фактически речь идёт об обходе ферзём шахматной доски n×n.
2. 14 баллов.
