Решение: Пути через город Ж
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Ж?
Решение по шагам
3 шагаДля каждого города на схеме подсчитываем количество путей из А, используя сумму количеств путей из городов, из которых в него ведут дороги.
Определяем количество путей из А в Ж и количество продолжений из Ж в М.
Так как каждый путь через Ж однозначно состоит из пути А—Ж и пути Ж—М, перемножаем полученные количества.
Где здесь ошибаются
Считают только пути из А в М и не проверяют прохождение через Ж.
Складывают, а не перемножают число путей до Ж и число путей от Ж до М.
Учитывают дороги, направленные противоположно стрелкам.