ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 97782
Темы:    [ Примеры и контрпримеры. Конструкции ]
[ Геометрия на клетчатой бумаге ]
[ Шахматные доски и шахматные фигуры ]
Сложность: 4
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Автор: Анджанс А.

Квадрат разбит на 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 – lm – 2.  Итого в ломаной не менее  l + m + (2n – l – m – 2) = 2n – 2  звеньев.


Ответ

2n – 2  звена.

Замечания

1. Фактически речь идёт об обходе ферзём шахматной доски n×n.

2. 14 баллов.

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

олимпиада
Название Турнир городов
Турнир
Дата 1981/1982
Номер 3
вариант
Вариант 9-10 класс
Задача
Номер 2

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .