6. Путешественник из Москвы хочет посетить четыре города Золотого кольца России: Ростов Великий, Владимир, Суздаль и Плёс. Турагентство предлагает маршруты с посещением некоторых городов Золотого кольца. Сведения о стоимости билетов и маршрутах представлены в таблице. | Номер маршрута | Посещаемые города | Стоимость (руб.) | |---|---|---| | 1 | Владимир, Суздаль | 16 500 | | 2 | Владимир | 7000 | | 3 | Ростов Великий, Суздаль | 16 500 | | 4 | Суздаль, Плёс | 15 900 | | 5 | Владимир, Ростов Великий, Плёс | 23 750 | | 6 | Ростов Великий, Плёс | 14 600 | Какие маршруты должен выбрать путешественник, чтобы побывать во всех четырёх городах и потратить меньше 31 500 рублей? В ответе запишите какой-нибудь один набор номеров маршрутов без пробелов, запятых и других дополнительных символов. Ответ:

Цель: Посетить все четыре города (Ростов Великий, Владимир, Суздаль, Плёс) и потратить менее 31 500 рублей.

Анализ маршрутов:

• Ростов Великий: присутствует в маршрутах 3, 5, 6.
• Владимир: присутствует в маршрутах 1, 2, 5.
• Суздаль: присутствует в маршрутах 1, 3, 4.
• Плёс: присутствует в маршрутах 4, 5, 6.

Поиск комбинаций:

Нам нужно найти набор маршрутов, которые в сумме охватывают все четыре города.

Вариант 1:

• Маршрут 2 (Владимир) - 7000 руб.
• Маршрут 4 (Суздаль, Плёс) - 15 900 руб.
• Маршрут 6 (Ростов Великий, Плёс) - 14 600 руб.

Сумма: 7000 + 15 900 + 14 600 = 37 500 руб. (Не подходит, т.к. больше 31 500 руб.)

Вариант 2:

• Маршрут 2 (Владимир) - 7000 руб.
• Маршрут 3 (Ростов Великий, Суздаль) - 16 500 руб.
• Маршрут 4 (Суздаль, Плёс) - 15 900 руб.

Сумма: 7000 + 16 500 + 15 900 = 39 400 руб. (Не подходит)

Вариант 3:

• Маршрут 2 (Владимир) - 7000 руб.
• Маршрут 1 (Владимир, Суздаль) - 16 500 руб.
• Маршрут 3 (Ростов Великий, Суздаль) - 16 500 руб.
• Маршрут 6 (Ростов Великий, Плёс) - 14 600 руб.

Этот вариант слишком дорогой и не оптимальный.

Вариант 4:

• Маршрут 2 (Владимир) - 7000 руб.
• Маршрут 4 (Суздаль, Плёс) - 15 900 руб.
• Маршрут 3 (Ростов Великий, Суздаль) - 16 500 руб.

Сумма: 7000 + 15 900 + 16 500 = 39 400 руб. (Не подходит)

Вариант 5:

• Маршрут 2 (Владимир) - 7000 руб.
• Маршрут 4 (Суздаль, Плёс) - 15 900 руб.
• Маршрут 5 (Владимир, Ростов Великий, Плёс) - 23 750 руб.

Сумма: 7000 + 15 900 + 23 750 = 46 650 руб. (Не подходит)

Вариант 6:

• Маршрут 1 (Владимир, Суздаль) - 16 500 руб.
• Маршрут 6 (Ростов Великий, Плёс) - 14 600 руб.

Сумма: 16 500 + 14 600 = 31 100 руб.

Посещённые города: Владимир, Суздаль, Ростов Великий, Плёс. Все четыре города охвачены.

Стоимость: 31 100 руб., что меньше 31 500 руб.

Ответ: 16