Задача №07876

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

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

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

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

1. Рассмотрим маршрут № 5 (Суздаль, Ростов) стоимостью $3000$ рублей. Чтобы посетить оставшиеся города (Ярославль, Владимир), необходимо добавить к нему маршрут № 6.

2. Стоимость маршрута № 6 (Ярославль, Владимир) составляет $2100$ рублей.

3. Проверим, все ли города посещены: Суздаль, Ростов, Ярославль, Владимир. Условие выполнено.

4. Вычислим общую стоимость:

$$3000+2100=5100\text{ (руб.)}$$

Полученная сумма $5100$ рублей меньше заданного ограничения в $6000$ рублей.

Другие возможные комбинации превышают бюджет:

• Маршрут № 3 (Ростов, Ярославль, Владимир — $3950$ руб.) в паре с любым маршрутом, содержащим Суздаль (№ 1 — $2300$ руб., № 2 — $2500$ руб. или № 5 — $3000$ руб.), даст сумму более $6000$ рублей.
• Набор из маршрутов № 1, № 4 и № 6: $2300+1100+2100=6100$ руб., что также больше $6000$ рублей.

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

Ответ: 56