Условие
Какое наибольшее число клеток может пересечь прямая, проведённая на листе
клетчатой бумаги размером 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!#].)
Источники и прецеденты использования