Разделы 
Дополнительно
Задача по математике - 3137
2019-05-19 
На клетчатой бумаге нарисован прямоугольник $m \times n$ клеток. Какой максимальной длины несамопересекающийся путь можно провести по линиям сетки на прямоугольнике из угла прямоугольника в угол, ему противоположный?
Решение:
Без ограничения общности можно считать, что размеры клетки $1 \times 1$.
Рассмотрим произвольную несамопересекающуюся ломаную, проведенную по линиям сетки на прямоугольнике из угла А прямоугольника в противоположный угол С. Будем передвигаться по этой ломаной из точки А в точку С. Разобьем ломаную на отрезки единичной длины. Каждый такой отрезок выходит из некоторого узла сетки. Так как ломаная - несамопересекающаяся, то из каждого узла сетки выходит не более одного отрезка. Кроме этого, из точки С не выходит ни одного отрезка.
Значит, длина любой несамопересекающейся ломаной, удовлетворяющей условиям задачи, не превосходит $(m+1)(n + 1) - 1$.
Рассмотрим два случая.
I случай. Хотя бы одно из чисел $m$ и $n$ четно.
В этом случае существует ломаная, удовлетворяющая условиям задачи, длина которой $(m + 1)(n + 1) - 1$ (рис.).
II случай. Оба числа $m$ и $n$ нечетны. Ломаная, удовлетворяющая условиям задачи, пересекает любую полосу нечетное число раз. Значит, в случае II длина ломаной , есть четное число и, следовательно, не превосходит $(m-n)(n + 1)-2$.
Ломаная, удовлетворяющая условиям задачи, длина которой $(m + 1)(n+1) - 2$, в случае II существует (рис.).
На клетчатой бумаге нарисован прямоугольник $m \times n$ клеток. Какой максимальной длины несамопересекающийся путь можно провести по линиям сетки на прямоугольнике из угла прямоугольника в угол, ему противоположный?
Решение:
Без ограничения общности можно считать, что размеры клетки $1 \times 1$.
Рассмотрим произвольную несамопересекающуюся ломаную, проведенную по линиям сетки на прямоугольнике из угла А прямоугольника в противоположный угол С. Будем передвигаться по этой ломаной из точки А в точку С. Разобьем ломаную на отрезки единичной длины. Каждый такой отрезок выходит из некоторого узла сетки. Так как ломаная - несамопересекающаяся, то из каждого узла сетки выходит не более одного отрезка. Кроме этого, из точки С не выходит ни одного отрезка.
Значит, длина любой несамопересекающейся ломаной, удовлетворяющей условиям задачи, не превосходит $(m+1)(n + 1) - 1$.
Рассмотрим два случая.
I случай. Хотя бы одно из чисел $m$ и $n$ четно.
В этом случае существует ломаная, удовлетворяющая условиям задачи, длина которой $(m + 1)(n + 1) - 1$ (рис.).
II случай. Оба числа $m$ и $n$ нечетны. Ломаная, удовлетворяющая условиям задачи, пересекает любую полосу нечетное число раз. Значит, в случае II длина ломаной , есть четное число и, следовательно, не превосходит $(m-n)(n + 1)-2$.
Ломаная, удовлетворяющая условиям задачи, длина которой $(m + 1)(n+1) - 2$, в случае II существует (рис.).
