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

Ответ: 134

Пошаговое решение:

1. Анализ таблицы: Изучаем таблицу с маршрутами и стоимостью.

2. Выбор маршрутов:

   Рассмотрим комбинации маршрутов, покрывающие все города и не превышающие бюджет:

   • Маршрут 1 (Ярославль) + Маршрут 3 (Владимир, Суздаль) + Маршрут 4 (Владимир, Ростов):
     • Посещаемые города: Ярославль, Владимир, Суздаль, Ростов.
     • Общая стоимость: 1700 + 2250 + 2150 = 6100 (руб.). Превышает бюджет.
   • Маршрут 1 (Ярославль) + Маршрут 3 (Владимир, Суздаль) + Маршрут 6 (Суздаль, Ростов):
     • Посещаемые города: Ярославль, Владимир, Суздаль, Ростов.
     • Общая стоимость: 1700 + 2250 + 2300 = 6250 (руб.). Превышает бюджет.
   • Маршрут 2 (Суздаль, Ярославль) + Маршрут 4 (Владимир, Ростов):
     • Посещаемые города: Суздаль, Ярославль, Владимир, Ростов.
     • Общая стоимость: 2650 + 2150 = 4800 (руб.). Укладывается в бюджет.
   • Маршрут 5 (Ярославль, Владимир, Ростов) + Маршрут 6 (Суздаль, Ростов):
     • Посещаемые города: Ярославль, Владимир, Ростов, Суздаль
     • Общая стоимость: 3950 + 2300 = 6250 (руб.). Превышает бюджет.
   • Маршрут 1 (Ярославль) + Маршрут 3 (Владимир, Суздаль) + Маршрут 4 (Владимир, Ростов):
     • Посещаемые города: Ярославль, Владимир, Суздаль, Ростов
     • Общая стоимость: 1700 + 2250 + 2150 = 6100 (руб.). Превышает бюджет.
   • Маршрут 5 (Ярославль, Владимир, Ростов) + Маршрут 3 (Владимир, Суздаль):
     • Посещаемые города: Ярославль, Владимир, Ростов, Суздаль
     • Общая стоимость: 3950 + 2250 = 6200 (руб.). Превышает бюджет.

3. Найдем другую комбинацию, подходящую под условие:

   Маршрут 1 (Ярославль) + Маршрут 3 (Владимир, Суздаль) + Маршрут 4 (Владимир, Ростов) = 1700 + 2250 + 2150 = 6100 (Не подходит)

   Рассмотрим такой вариант: Маршрут 1 (Ярославль), Маршрут 3 (Владимир, Суздаль), Маршрут 6 (Суздаль, Ростов) = 1700 + 2250 + 2300 = 6250 (Не подходит)

   Маршрут 1 (Ярославль) + Маршрут 3 (Владимир, Суздаль) + Маршрут 4 (Владимир, Ростов) => 134 = 1700 + 2250 + 2150 = 6100

   Маршрут 2 (Ярославль, Суздаль) + Маршрут 4 (Владимир, Ростов) => 24 = 2650 + 2150 = 4800. Но нам не хватает Владимира

Попробуем маршруты 1, 3 и 4: Ярославль (1700), Владимир и Суздаль (2250), Владимир и Ростов (2150). Города будут все охвачены, но стоимость (6100) превышает 5000 рублей.

Рассмотрим еще вариант. Нам нужен маршрут, включающий в себя Ярославль, Владимир, Суздаль и Ростов. Вариант 1, 3 и 4 не подходит, так как не вписываемся в бюджет. Значит можно сделать так: берем маршрут 1 (Ярославль), 3 (Владимир, Суздаль) и 4 (Владимир, Ростов). 1 + 3 + 4 = 1700 + 2250 + 2150 = 6100. Значит какой-то город в маршруте будет повторяться.

Т.е. Ярославль+Владимир+Суздаль+Ростов => 1+3+4 = 1700+2250+2150 = 6100. Бюджет превышен.

Рассмотрим вариант 1, 3, 4: 1700 + 2250 + 2150 = 6100 > 5000 (дорого)

Рассмотрим вариант 1, 2, 4: 1700 + 2650 + 2150 = 6500 > 5000 (дорого)

Т.е., чтобы побывать во всех 4-х городах и потратить менее 5000 руб. – нужно выбрать: Маршрут 1 + Маршрут 3 + Маршрут 4

Итоговый набор: 134

Ответ: 134