Задача №08267

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

Какие маршруты должен выбрать путешественник, чтобы побывать во всех четырёх городах и затратить менее $6000$ рублей?

В ответе укажите какой-нибудь один набор номеров маршрутов без пробелов, запятых и других дополнительных символов.

Для того чтобы посетить все 4 города (Владимир, Ярославль, Суздаль и Ростов Великий) и затратить менее $6000$ рублей, проанализируем возможные варианты комбинаций маршрутов из таблицы.

1. Проверим комбинацию маршрутов № 1 (Ростов, Владимир) и № 4 (Ярославль, Суздаль):

• Посещаемые города: Ростов, Владимир, Ярославль, Суздаль (все необходимые города).
• Суммарная стоимость:

$$2150+2700=4850\text{ рублей.}$$

• Условие по стоимости (менее $6000$ рублей) выполняется:

$$4850<6000.$$

2. Проверим комбинации с маршрутом № 6 (Суздаль, Ростов, Владимир), который охватывает сразу три города и стоит $3800$ рублей. Чтобы посетить Ярославль, нужно добавить к нему маршрут № 2 (Ярославль, Владимир), № 3 (Ростов, Ярославль) или № 4 (Ярославль, Суздаль):

• Вариант 6 + 2: $3800+2500=6300$ рублей (больше $6000$);
• Вариант 6 + 3: $3800+2250=6050$ рублей (больше $6000$);
• Вариант 6 + 4: $3800+2700=6500$ рублей (больше $6000$).

3. Проверим другие комбинации, включающие три маршрута, например, с маршрутом № 5 (Суздаль, $1700$ руб.):

• Чтобы посетить Ростов, Владимир и Ярославль, можно взять маршруты № 1 и № 2: $1700+2150+2500=6350$ рублей (больше $6000$);
• Или маршруты № 1 и № 3: $1700+2150+2250=6100$ рублей (больше $6000$).

Таким образом, подходящим набором маршрутов является 1 и 4.

Ответ: 14