Путешественник из Москвы хочет посетить 4 города Золотого кольца России: Владимир, Ярославль, Суздаль и Ростов Великий. Турагентство предлагает маршруты с посещением некоторых городов Золотого кольца. Сведения о стоимости билетов и маршрутах представлены в таблице. | Номер маршрута | Посещаемые города | Стоимость (руб.) | | :--- | :--- | :--- | | 1 | Ярославль, Владимир | 3000 | | 2 | Владимир, Ростов, Суздаль | 3950 | | 3 | Ростов, Суздаль | 2150 | | 4 | Ростов, Ярославль | 2350 | | 5 | Владимир | 1750 | | 6 | Ярославль, Суздаль | 2200 | Какие маршруты должен выбрать путешественник, чтобы побывать во всех четырёх городах и затратить менее 6000 рублей? В ответе укажите какой-нибудь один набор номеров маршрутов без пробелов, запятых и других дополнительных символов.
1. Выпишем список городов, которые необходимо посетить: Владимир (В), Ярославль (Я), Суздаль (С) и Ростов Великий (Р). 2. Проанализируем предложенные маршруты и их стоимость: - Маршрут 1: Ярославль, Владимир — 3000 руб. - Маршрут 2: Владимир, Ростов, Суздаль — 3950 руб. - Маршрут 3: Ростов, Суздаль — 2150 руб. - Маршрут 4: Ростов, Ярославль — 2350 руб. - Маршрут 5: Владимир — 1750 руб. - Маршрут 6: Ярославль, Суздаль — 2200 руб. 3. Попробуем составить комбинации маршрутов, охватывающие все четыре города, так, чтобы их общая стоимость была меньше 6000 рублей. Рассмотрим комбинацию маршрутов 1 и 3: Города: Ярославль, Владимир (из №1) + Ростов, Суздаль (из №3). Все 4 города посещены. Стоимость: 3000 + 2150 = 5150 руб. Условие выполняется: 5150 < 6000 . Проверка других пар: - 1 и 2: 3000 + 3950 = 6950 руб. (больше 6000 ). - 2 и 4: 3950 + 2350 = 6300 руб. (больше 6000 ). - 2 и 6: 3950 + 2200 = 6150 руб. (больше 6000 ). - Остальные пары (например, 1 и 4, 3 и 6) не охватывают все 4 города. Проверка комбинаций из трёх маршрутов: Самый дешёвый вариант из трёх маршрутов, не включающий дорогие маршруты 1 и 2: - 5, 3 и 6: 1750 + 2150 + 2200 = 6100 руб. (больше 6000 ). 4. Единственным набором маршрутов, удовлетворяющим всем условиям, является 1 и 3. Ответ: 13.
13