Задание олимпиады: минимальное число звеньев в ломаной (Анджанс А.)

  На рисунке показан пример такой восьмизвенной ломаной для  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  звеньев.