Условие
Какое наибольшее число клеток может пересечь прямая, проведённая на листе
клетчатой бумаги размером
m×
n клеток?
Решение
Пусть
— какая-то ``первая'' из клеток, пересечённых нашим
отрезком
l. Так как на листке бумаги имеется
m - 1 горизонтальных линий
(края листка мы не считаем) и
n - 1 вертикальных (или наоборот; листок мы
считаем положенным перед собой, как обычно, что позволяет употреблять
термины ``горизонтальный'' и ``вертикальный''), то отрезок
l
может пересечь не более чем
(
m - 1) + (
n - 1) =
m +
n - 2 линий (ибо каждую
вертикальную и каждую горизонтальную линию он пересекает не более одного
раза), и, значит, максимум
m +
n - 2 раза может перейти из одной клетки в
другую. Присоединяя сюда и ``начальную'' клетку
, мы заключим,
что
l может пересечь не более чем m + n - 1 клеток. С другой стороны,
m +
n - 1
клеток отрезок пересечь может: для этого необходимо (и
достаточно), чтобы он пересекал листок ``по диагонали'', встречая на
своем пути все горизонтальные и все вертикальные линии.
Замечание.
Если
m и
n
не взаимно просты, то диагональ прямоугольного листка пройдёт через ряд
узлов имеющейся на листке сети линий, пересекая в этих случаях
горизонтальную и вертикальную линии одновременно, что уменьшит число
пересеченных клеток; однако в этом случае мы можем сместить слегка конец
отрезка
l, оставляя его в той же угловой клетке
, что и раньше,
с тем, чтобы сдвинутый отрезок
l' по-прежнему пересекал все имеющиеся
на листке линии, но ни разу не проходил через узел сети линий. Для этого,
например, достаточно, чтобы отрезок
l' начинался в точке, имеющей в
системе координат, оси которой параллельны сторонам квадратов сетки, а
единица длины равна стороне квадратов, рациональные координаты, а кончался
в точке с иррациональными координатами (докажите это!).
(Решение из книги [#!gn!#].)
Источники и прецеденты использования
