Условие
В городе 10 улиц, параллельных друг другу, и 10 улиц, пересекающих
их под прямым углом. Какое наименьшее число поворотов может иметь
замкнутый автобусный маршрут, проходящий через все перекрестки?
Решение
Замкнутый маршрут, проходящий через все перекрестки, может иметь 20
поворотов (рис.). Остается доказать, что меньше 20 поворотов
такой маршрут иметь не может. После каждого поворота происходит
переход с горизонтальной улицы на вертикальную или с вертикальной
на горизонтальную. Поэтому число горизонтальных звеньев замкнутого
маршрута равно числу вертикальных звеньев и равно половине числа
поворотов. Предположим, что замкнутый маршрут имеет меньше 20
поворотов. Тогда найдутся улицы обоих направлений, по которым
маршрут не проходит. Поэтому маршрут не проходит через перекресток
этих улиц.
Источники и прецеденты использования
