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