На рисунке – схема дорог, связывающих пункты , , , , , , , , , , , .
Сколько существует различных путей из пункта в пункт , не проходящих через пункт ?
Показать разбор и ответ
Указание:
Разбейте путь на части – из в и из в , при этом удалив вершину и все пути, соединяющие её с другими вершинами.
Решение:
Схема устроена так, что путь обязательно пройдёт через город , поэтому его можно разделить на две части: из в , из в .
Пусть – количество допустимых путей из пункта в пункт . Оно равно сумме количества путей из в каждый из пунктов, откуда есть прямая дорога в . Тогда получаем (пункт и связанные с ним дороги не рассматриваем):
(единственный способ попасть из в – остаться на месте)
Всего получается путей из в .
Из в можно пройти тремя путями: , , .
На каждом из участков маршрута можно выбрать путь независимо от других участков, поэтому всего получается пути.
Ответ: 33
Это задание составили эксперты «СтатГрада» для Яндекса
Это задание решали 7 тыс. раз. С ним справились 60% пользователей.