Решение: Пути через город Ж
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Ж?
Схема дорог между городами. Саму картинку ещё готовим — у остальных задач темы она на месте.
Решение по шагам
4 шагаКаждый путь из А в М, проходящий через Ж, однозначно разбивается на путь из А в Ж и путь из Ж в М.
Для каждой вершины схемы последовательно подсчитываем число путей из А, используя правило: число путей в вершину равно сумме чисел путей во все непосредственно предшествующие вершины.
Отдельно подсчитываем число путей из Ж в М по той же схеме. Перемножение полученных количеств даёт число путей, проходящих через Ж.
По данной схеме результат подсчёта равен 51.
$$N_{А\to М\ через\ Ж}=N_{А\to Ж}\cdot N_{Ж\to М}=51$$Где здесь ошибаются
Подсчитывают все пути из А в М, не проверяя прохождение через Ж.
Складывают вместо перемножения количество путей до Ж и после Ж.
Учитывают дороги, направленные против стрелок.