Задача №07916

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

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

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

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

1. Рассмотрим маршрут № 3 (Ростов, Ярославль), стоимость которого составляет $2050\text{ руб.}\text{.}$ Чтобы посетить все 4 города, к этому маршруту нужно добавить города Владимир и Суздаль. В таблице есть маршрут № 6 (Суздаль, Владимир) стоимостью $2750\text{ руб.}\text{.}$

Общая стоимость:

$$2050+2750=4800\text{ руб.}$$

Посещённые города: $\{\text{Ростов};\text{Ярославль};\text{Суздаль};\text{Владимир}\}\text{.}$

Данный вариант удовлетворяет условию (стоимость $4800<6000$).

2. Проверим другие варианты:

• Если выбрать маршрут № 1 (Владимир, Ростов, Ярославль) за $3900\text{ руб.}\text{,}$ то для посещения Суздаля нужно добавить маршрут № 2 ($2200\text{ руб.}$), № 4 ($2350\text{ руб.}$) или № 6 ($2750\text{ руб.}$). Минимальная стоимость составит:

$$3900+2200=6100\text{ руб.}$$

что больше $6000\text{ руб.}\text{.}$

• Если выбрать маршрут № 5 (Владимир) за $1850\text{ руб.}$ и маршрут № 2 (Суздаль, Ярославль) за $2200\text{ руб.}\text{,}$ то останется посетить Ростов. Для этого нужно добавить маршрут № 3 или № 4. Минимальная стоимость составит:

$$1850+2200+2050=6100\text{ руб.}$$

что больше $6000\text{ руб.}\text{.}$

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

Ответ: 36