Главное меню

Как решить: Как инспектор может проверить как можно большее число улиц?

Автор Wol, Март 14, 2024, 00:40

« назад - далее »

Wol

На рисунке приведена карта города Многодорожный, состоящего из площадей (круги на рисунке) и соединяющих их улиц (отрезки на рисунке). Инспектор хочет проехать по улицам и проверить состояние дорог на них. В целях экономии времени инспектор не проезжает по улице, которую уже проверил.
Начать свой маршрут инспектор может с любой площади города и закончить может на любой площади.
А) покажи, как инспектор может проверить, как можно большее число улиц;
Б) попробуй объяснить, почему большее число дорог проверить не удастся

Kantua

Не знаю, на какой класс рассчитана такая задача по математике. Она скорее на логику даже.
Логично предположить, что свой путь инспектор начнёт с центральной площади (точки) и пойдёт по периметру. Но по условию путь инспектора не должен пересекаться. То есть, каждая точка должна быть пройдена единожды.
У меня получились такие маршруты:
И действительно, большая половина дорог не проинспектирована при каждом из предложенных маршрутов.
Я посчитала логичным начать маршрут инспектора с крайней точки (любой! Но я выбрала крайнюю левую)
И вот такие маршруты построила:
Здесь уже большая половина дорог проинспектирована (в первом из двух вариантов).
Но оптимальным решением я считаю следующее:
Здесь из 25 дорог мы проинспектировали 14.

Tiobyn

Нам сказано, что инспектор не должен проезжать повторно по одной и той же улице, но нет задачи не пересекать повторно одни и те же площади. Поэтому мы можем построить такой маршрут, при котором инспектор сможет проверить 19 дорог из 25:
Цифрами я обозначила площади, которые он посетит. Получается такой маршрут. Из первой площади через вторую на третью, потом вверх на четвёртую, влево на пятую, вниз опять через вторую на шестую, далее вправо на седьмую, вверх снова на третью, вправо через восьмую на девятую, вниз на десятую, вправо на одиннадцатую, вверх через двенадцатую на тринадцатую, влево через четырнадцатую на пятнадцатую, вниз через восьмую на шестнадцатую и влево - заканчиваем на седьмой площади. Думаю, больше дорог обойти не получится.