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

Решение:

Задача состоит в том, чтобы выбрать комбинацию маршрутов, которая позволит посетить все четыре города (Владимир, Ярославль, Суздаль, Ростов) и при этом потратить сумму менее 5000 рублей.

Анализ маршрутов:

• Маршрут 1: Суздаль, Ярославль, Владимир (3 города) - 3000 руб.
• Маршрут 2: Ростов, Владимир (2 города) - 2400 руб.
• Маршрут 3: Ярославль, Владимир (2 города) - 2100 руб.
• Маршрут 4: Суздаль (1 город) - 1650 руб.
• Маршрут 5: Ростов, Суздаль (2 города) - 2700 руб.
• Маршрут 6: Ярославль, Ростов (2 города) - 2350 руб.

Поиск комбинации:

Нам нужно посетить 4 города. Рассмотрим различные комбинации маршрутов:

1. Маршрут 1 (3 города) + Маршрут 2 (1 недостающий город: Ростов): Маршрут 1 включает Суздаль, Ярославль, Владимир. Маршрут 2 включает Ростов, Владимир. Вместе они покрывают все 4 города. Общая стоимость: 3000 + 2400 = 5400 руб. Это больше 5000 руб.
2. Маршрут 1 (3 города) + Маршрут 5 (1 недостающий город: Ярославль): Маршрут 1 включает Суздаль, Ярославль, Владимир. Маршрут 5 включает Ростов, Суздаль. Вместе они покрывают все 4 города. Общая стоимость: 3000 + 2700 = 5700 руб. Это больше 5000 руб.
3. Маршрут 1 (3 города) + Маршрут 6 (1 недостающий город: Ростов): Маршрут 1 включает Суздаль, Ярославль, Владимир. Маршрут 6 включает Ярославль, Ростов. Вместе они покрывают все 4 города. Общая стоимость: 3000 + 2350 = 5350 руб. Это больше 5000 руб.
4. Маршрут 4 (1 город: Суздаль) + Маршрут 6 (2 города: Ярославль, Ростов) + Маршрут 2 (1 недостающий город: Владимир): Маршрут 4 (Суздаль), Маршрут 6 (Ярославль, Ростов), Маршрут 2 (Ростов, Владимир). Вместе покрывают Суздаль, Ярославль, Ростов, Владимир. Стоимость: 1650 + 2350 + 2400 = 6400 руб. Это больше 5000 руб.
5. Маршрут 4 (1 город: Суздаль) + Маршрут 2 (2 города: Ростов, Владимир) + Маршрут 6 (1 недостающий город: Ярославль): Маршрут 4 (Суздаль), Маршрут 2 (Ростов, Владимир), Маршрут 6 (Ярославль, Ростов). Вместе покрывают Суздаль, Ростов, Владимир, Ярославль. Стоимость: 1650 + 2400 + 2350 = 6400 руб. Это больше 5000 руб.
6. Маршрут 4 (1 город: Суздаль) + Маршрут 3 (2 города: Ярославль, Владимир) + Маршрут 5 (1 недостающий город: Ростов): Маршрут 4 (Суздаль), Маршрут 3 (Ярославль, Владимир), Маршрут 5 (Ростов, Суздаль). Вместе покрывают Суздаль, Ярославль, Владимир, Ростов. Стоимость: 1650 + 2100 + 2700 = 6450 руб. Это больше 5000 руб.
7. Маршрут 4 (1 город: Суздаль) + Маршрут 5 (2 города: Ростов, Суздаль) + Маршрут 3 (1 недостающий город: Ярославль, Владимир): Маршрут 4 (Суздаль), Маршрут 5 (Ростов, Суздаль), Маршрут 3 (Ярославль, Владимир). Вместе покрывают Суздаль, Ростов, Ярославль, Владимир. Стоимость: 1650 + 2700 + 2100 = 6450 руб. Это больше 5000 руб.
8. Маршрут 4 (1 город: Суздаль) + Маршрут 2 (2 города: Ростов, Владимир) + Маршрут 6 (1 недостающий город: Ярославль): Маршрут 4 (Суздаль), Маршрут 2 (Ростов, Владимир), Маршрут 6 (Ярославль, Ростов). Вместе покрывают Суздаль, Ростов, Владимир, Ярославль. Стоимость: 1650 + 2400 + 2350 = 6400 руб. Это больше 5000 руб.
9. Рассмотрим комбинацию из двух маршрутов, покрывающих все 4 города:
   • Маршрут 4 (Суздаль) + Маршрут 3 (Ярославль, Владимир) + Маршрут 2 (Ростов, Владимир). Общая стоимость: 1650 + 2100 + 2400 = 6150 руб. (больше 5000).
   • Маршрут 4 (Суздаль) + Маршрут 5 (Ростов, Суздаль) + Маршрут 3 (Ярославль, Владимир). Общая стоимость: 1650 + 2700 + 2100 = 6450 руб. (больше 5000).
   • Маршрут 4 (Суздаль) + Маршрут 6 (Ярославль, Ростов) + Маршрут 2 (Ростов, Владимир). Общая стоимость: 1650 + 2350 + 2400 = 6400 руб. (больше 5000).
   • Маршрут 5 (Ростов, Суздаль) + Маршрут 3 (Ярославль, Владимир). Это комбинация из двух маршрутов, которые вместе покрывают все 4 города. Стоимость: 2700 + 2100 = 4800 руб. Эта сумма меньше 5000 руб.
   • Маршрут 6 (Ярославль, Ростов) + Маршрут 4 (Суздаль) + Маршрут 2 (Ростов, Владимир). Суммарно: 2350 + 1650 + 2400 = 6400 руб. (больше 5000).
   • Маршрут 6 (Ярославль, Ростов) + Маршрут 4 (Суздаль) + Маршрут 3 (Ярославль, Владимир). Суммарно: 2350 + 1650 + 2100 = 6100 руб. (больше 5000).

   Комбинация маршрутов 5 и 3 покрывает все 4 города (Суздаль, Ростов из маршрута 5; Ярославль, Владимир из маршрута 3) и стоит 2700 + 2100 = 4800 рублей, что меньше 5000 рублей.

   Другой возможный вариант: маршруты 6 и 4 (Ярославль, Ростов + Суздаль) не покрывают Владимир. Необходимо добавить маршрут, включающий Владимир. Если добавить маршрут 3 (Ярославль, Владимир) к маршруту 4 (Суздаль) и 6 (Ярославль, Ростов), то получаем 1650 (4) + 2350 (6) + 2100 (3) = 6100 руб. (слишком дорого).

   Проверим комбинацию маршрутов 4 (Суздаль) + 2 (Ростов, Владимир) + 6 (Ярославль, Ростов): 1650 + 2400 + 2350 = 6400 руб. (слишком дорого).

   Проверим комбинацию маршрутов 4 (Суздаль) + 2 (Ростов, Владимир) + 3 (Ярославль, Владимир): 1650 + 2400 + 2100 = 6150 руб. (слишком дорого).

   Итак, единственная найденная комбинация, удовлетворяющая условиям: маршруты 5 и 3.

   Ответ: 53