Задача
Сторона клетки клетчатой бумаги равна 1. По линиям сетки построен прямоугольник со сторонами m и n. Можно ли в прямоугольнике провести по линиям сетки замкнутую ломаную, которая ровно один раз проходила бы через каждый узел сетки, расположенный внутри или на границе прямоугольника? Если можно, то какова её длина?
Решение
Заметим, что из каждого узла сетки, расположенного внутри или на границе прямоугольника n×m, выходит ровно одно звено пути, иначе в этом узле либо ни разу не побывали, либо побывали более одного раза. Всего узлов внутри или на границе прямоугольника (n + 1)(m + 1), а значит, длина ломаной равна (n + 1)(m + 1). Длина такой ломаной чётна (см. задачу 130932). Поэтому хотя бы одно из чисел m, n нечётно.
Если одно из них равно 1, то обход по периметру удовлетворяет условию. Когда одно из них нечётно и больше 1, возможен обход, показанный на рисунке.
Ответ
Если n и m чётны, то такой ломаной не существует; если хотя бы одно из чисел n и m нечётно, то такая ломаная существует и её длина равна (n + 1)(m + 1).
Чтобы оставлять комментарии, войдите или зарегистрируйтесь