Задача №07938

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

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

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

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

Проверим комбинацию маршрутов $4$ и $6\text{:}$
1. Маршрут $4\text{:}$ Суздаль, Владимир (стоимость $2000$ руб.).
2. Маршрут $6\text{:}$ Ростов, Ярославль (стоимость $2650$ руб.).

Вместе эти маршруты покрывают все четыре города. Вычислим суммарную стоимость:

$$2000+2650=4650.$$

Сумма $4650$ меньше $6000$ рублей.

Проверим другие варианты. Рассмотрим тройки маршрутов. Например, любая тройка, покрывающая все города, обойдётся дороже. Рассмотрим маршруты $1\text{,}$ $2$ и $4\text{:}$

$$2300+1750+2000=6050.$$

Сумма $6050$ рублей превышает $6000$ рублей. Следовательно, комбинация маршрутов $4$ и $6$ является подходящей.

Ответ: 46