53

Блондинка хочет обойти все модные магазины центральной части Милана (см. План),…

23 октября 2024

Блондинка хочет обойти все модные магазины центральной части Милана (см. План), начав обход с вокзала (точка В) и закончив в своем отеле (точка О). Дляэтого ей надо пройти как можно большее число кварталов (квартал на плане представляет собой отрезок между двумя соседними перекрестками), но на каждом перекрестке она может оказаться не более одного раза, иначе она запутается и в отель не попадет (даже если дважды окажется на перекрестке, где расположен отель). Какое максимальное число кварталов сможет она пройти при условии, что рассматривать покупки она собирается в отеле?

категория: алгебра



43

По всей видимости, максимальная протяженность маршрута составит 34 улицы. Число пройденных улиц равно числу перекрестков, которые удалось посетить, минус один (поскольку начальную точку мы «посетили» изначально, не пройдя еще ни одной улицы). На один перекресток зайти так и не получится: к каждому пройденному перекрестку подходит 2 улицы, по которым надо пройти. В нашем случае непройденным остался один перекресток, и к нему нельзя подойти, не пройдя дважды по другим перекресткам. Докажем теперь, что в данном случае один перекресток останется не пройденным. Перекрестки условно можно раскрасить в шахматном порядке в белый и черный цвет. Каждая улица соединяет два перекрестка: один «черный», а другой — «белый». На нашей карте всего 36 перекрестков, по 18 каждого «цвета». Причем два перекрестка являются начальной и конечной точками пути, а остальные 34 еще надо посетить. Однако, расположение начальной и конечной точек пути таково, что обе этих точки имеют одинаковый цвет. Это означает, что среди оставшихся перекрестков будет 16 перекрестков одного цвета и 18 другого. Но ведь, чтобы пройти маршрут от О к В, надо построить такую последовательность точек, чтобы в ней чередовались цвета (черный-белый-черный и так далее). Имея в распоряжении 16 точек одного цвета и 18 другого, нельзя построить такую последовательность: из 18 точек одна останется лишней. Это и есть тот перекресток, на который не удастся зайти. И, кстати, «цвет» этого оставшегося перекрестка — не такой как у точек начала и конца, что видно на рисунке. Это будет справедливо и для любого другого маршрута с нашими начальными условиями. Пройти по улицам, зайдя на все перекрестки, можно будет лишь при таком расположении начала и конца, при котором эти точки окажутся разных «цветов». Или, что то же самое, если расстояние от начальной до конечной точки будет составлять нечетное число улиц.

Знаете ответ?


Есть интересный вопрос? Задайте его нашему сообществу, у нас наверняка найдется ответ!
Делитесь опытом и знаниями, зарабатывайте награды и репутацию, заводите новых интересных друзей!
Задавайте интересные вопросы, давайте качественные ответы и зарабатывайте деньги. Подробнее...