Задача №07984

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

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

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

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

1. Рассмотрим маршруты 1 (Ростов, Владимир) и 5 (Суздаль, Ярославль). В этом наборе присутствуют все четыре города. Вычислим суммарную стоимость:

$$1950+2900=4850$$

рублей. Полученная сумма меньше $6000$ рублей, следовательно, набор маршрутов 1 и 5 подходит.

2. Проверим другие возможные комбинации:

• Маршруты 2 (Ярославль, Ростов, Владимир) и 3 (Ростов, Суздаль): охватывают все города, но стоимость составляет $3900+2350=6250$ рублей, что превышает $6000\text{.}$
• Маршруты 2 (Ярославль, Ростов, Владимир) и 4 (Суздаль, Владимир): охватывают все города, стоимость составляет $3900+2400=6300$ рублей.
• Набор из маршрутов 6 (Ярославль), 1 (Ростов, Владимир) и 3 (Ростов, Суздаль): охватывает все города, однако стоимость составляет $1700+1950+2350=6000$ рублей. Поскольку в условии указано, что стоимость должна быть строго менее $6000$ рублей, этот вариант не подходит.

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

Ответ: 15