3. Путешественник из Москвы хочет посетить четыре города Золотого кольца России: Владимир, Ярославль, Суздаль и Ростов. Тур агентство предлагает маршруты с посещением некоторых городов Золотого кольца. Сведения о стоимости билетов и составе маршрутов представлены в таблице. Какие маршруты должен выбрать путешественник, чтобы побывать во всех четырёх городах и затратить на все поездки менее 5000 рублей? В ответе укажите номера выбранных маршрутов и затраты на все поездки.

Подберём маршруты так, чтобы вместе они включали все четыре города, а стоимость была меньше 5000 рублей.

1. Маршруты 1 и 6: вместе охватывают Суздаль, Ярославль, Владимир и Ростов. Стоимость: 3900 + 2350 = 6250 рублей, что больше 5000.
2. Маршруты 2, 4 и 6: маршрут 2 включает Ростов и Владимир, маршрут 4 — Суздаль, маршрут 6 — Ярославль и Ростов. Вместе посещаются все четыре города. Стоимость: 2400 + 1650 + 2350 = 6400 рублей.
3. Маршруты 3, 4 и 6: маршрут 3 включает Ярославль и Владимир, маршрут 4 — Суздаль, маршрут 6 — Ярославль и Ростов. Вместе посещаются все четыре города. Стоимость: 2100 + 1650 + 2350 = 6100 рублей.
4. Маршруты 2, 3 и 4: маршрут 2 включает Ростов и Владимир, маршрут 3 — Ярославль и Владимир, маршрут 4 — Суздаль. Вместе посещаются все четыре города. Стоимость: 2400 + 2100 + 1650 = 6150 рублей.

Проверим, существует ли комбинация дешевле 5000 рублей. Самые дешёвые маршруты, покрывающие все четыре города, стоят 6100 рублей; следовательно, условие о затратах менее 5000 рублей выполнить нельзя.

Ответ: по таблице нет подходящего набора маршрутов. Минимальные затраты для посещения всех четырёх городов — 6100 рублей (маршруты 3, 4 и 6).