Задача №08169

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

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

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

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

1. Рассмотрим комбинацию маршрутов № 2 и № 4:

• Маршрут № 2 включает Суздаль и Ярославль.
• Маршрут № 4 включает Владимир и Ростов Великий.
• Вместе эти маршруты охватывают все искомые города: Суздаль, Ярославль, Владимир, Ростов Великий.
• Суммарная стоимость:

$$2650+2150=4800\text{ рублей.}$$

• Стоимость $4800$ рублей меньше заданного ограничения в $5000$ рублей. Данный вариант подходит.

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

• Если взять маршрут № 5 (Ярославль, Владимир, Ростов Великий) стоимостью $3950$ рублей, то для посещения четвёртого города (Суздаля) необходимо добавить маршрут № 2, № 3 или № 6. Самый дешёвый из них — № 3 ($2250$ рублей). Итоговая стоимость составит:

$$3950+2250=6200\text{ рублей,}$$

что значительно больше $5000$ рублей.

• При попытке составить комбинацию из трёх маршрутов (например, № 1, № 3 и № 6) для охвата всех городов, стоимость также превысит лимит:

$$1700+2250+2300=6250\text{ рублей.}$$

Таким образом, подходящим набором маршрутов является $2$ и $4\text{.}$

Ответ: 24