Задача №08228

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

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

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

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

Обозначим города: В — Владимир, Я — Ярославль, С — Суздаль, Р — Ростов.

Маршруты и их покрытие:
1. В, Р, Я — 3,900 руб.
2. С, Я — 2,200 руб.
3. Р, Я — 2,050 руб.
4. Р, С — 2,350 руб.
5. В — 1,850 руб.
6. С, В — 2,750 руб.

Нужно выбрать маршруты так, чтобы каждый город был посещён хотя бы в одном маршруте, а суммарная стоимость была менее 6,000 рублей.

Переберём возможные пары маршрутов, так как три маршрута, как правило, стоят дороже.

Рассмотрим пару маршрутов 3 и 6:
Маршрут 3 покрывает Р и Я, а маршрут 6 покрывает С и В. Таким образом, все четыре города будут посещены. Вычислим суммарную стоимость:

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

Полученная сумма $4800<6000\text{,}$ что полностью удовлетворяет условию.

Для проверки рассмотрим другие варианты. Например, пара маршрутов 1 и 2 также покрывает все города, но их стоимость:

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

Сумма $6100⩾6000\text{,}$ что не подходит под условие задачи.

Рассмотрим комбинацию из трёх маршрутов, например 5, 2 и 3:

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

Данная сумма также $6100⩾6000\text{,}$ вариант не подходит.

Следовательно, подходящий набор маршрутов — 3 и 6.

Ответ: 36