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