Луиза играет на поле, на котором отмечено несколько точек (см. рисунок). Она должна пройти через все отмеченные точки, двигаясь только по прямым отрезкам. Разрешается повернуть не более 7 раз. Начать свой путь Луиза может в любом месте поля и двигаться сначала в любом направлении. Как Луизе пройти через все отмеченные точки?
Посчитаем количество точек на сетке. Точки расположены в узлах клетчатой бумаги в форме параллелограмма (наклонной сетки):
- верхняя строка:
точки; - следующая строка:
точки; - следующая:
точки; - следующая:
точки; - нижняя строка:
точки.
Всего на поле расположеноточек: они образуют сетку размера (или ромб/параллелограмм), ориентированный диагонально.
Заметим, что точки лежат на параллельных прямых (горизонтальных, вертикальных или диагональных).
Путь состоит из последовательных звеньев ломаной. Не более
Посмотрим на расположение точек по диагоналям сетки (направления под углом
- Диагонали, идущие в одном направлении (например, параллельные направлению «вниз-вправо»), покрывают все точки за несколько параллельных линий. Точки лежат на
таких диагоналях. Если соединять их «змейкой», выходя за пределы поля для поворота, потребуется ровно отрезков и поворотов.
Построим путь:
- Зададим координаты точек в узлах сетки (примем шаг сетки за
):
- строка
( ): - строка
( ): - строка
( ): - строка
( ): - строка
( ):
Все точки можно покрыть
-й отрезок: по линии через точки ( поворот при переходе на следующую строку); - Всего
горизонтальных прямых покрывают все точки. Соединяя их концы последовательно, получим ломаную из горизонтальных звеньев и наклонных связующих звеньев (всего отрезков, поворотов — много).
Однако, если двигаться по наклонным прямым сетки:
Точки лежат на прямых вида
: ( точка); : (или сдвинуто);
Проще всего покрыть точки параллельными прямыми с наклоном под
Заметим, что точки ложатся на
Пройти все точки можно непрерывной ломаной «змейкой»:
- Отрезок
: проходит через крайний ряд точек. - Отрезок
(после -го поворота): проходит через следующий параллельный ряд в обратном направлении. - Отрезок
(после -го поворота): через третий ряд. - Отрезок
(после -го поворота): через четвёртый ряд. - Отрезок
(после -го поворота): через пятый ряд. - Отрезок
(после -го поворота): через шестой ряд.
Все
Поскольку путь не обязан оставаться строго внутри границ фигуры, образованной точками, и может начинаться в любом месте, все точки можно обойти непрерывной ломаной линией («змейкой»), двигаясь вдоль параллельных рядов (по диагоналям или горизонталям). Соединяя соседние ряды отрезками, мы получаем ломаную, число поворотов в которой не превышает
Луизе нужно пройти через точки «змейкой» вдоль параллельных рядов, соединяя концы соседних рядов прямыми отрезками. Для этого достаточно ломаной из
